浙江省建设注册管理中心网站,福州最好的网站建设公司,crm登录系统,做阿里巴巴怎么进公司网站 #x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;数据结构 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录1.算法效率1.1 如何衡… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接数据结构 长路漫漫浩浩万事皆有期待 文章目录1.算法效率1.1 如何衡量一个算法的好坏1.2 算法的复杂度2.时间复杂度2.1 什么是时间复杂度2.2 大O渐进表示法 (估算)2.3 常见的时间复杂度计算举例2.3.1 实例1:2.3.2 实例2:2.3.3 实例3:2.3.4 实例42.3.5 实例5:2.3.6 实例6:2.3.7 实例7:2.3.8 实例82.4 常见的复杂度对比3.根据对时间复杂度的要求编写代码3.1 消失的数字3.2 轮转数组4.空间复杂度4.1 什么是空间复杂度4.2 常见的空间复杂度计算举例4.2.1 实例1:4.2.2 实例2:4.2.3 实例3:4.2.4 实例4:5.根据对空间复杂度的要求编写代码5.1 移除元素6.总结学习顺序 插入排序-选择排序-交换排序-归并排序-非比较排序-文件排序 1.算法效率
1.1 如何衡量一个算法的好坏
递归代码 ———— 斐波那契数列的代码量十分简洁所以这个算法是很好的但其实使用递归是不太好计算第40位斐波那契数时要很长时间原因是内部产生大量重复的计算。那该如何去衡量算法的优劣呢
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
int Fib(int n)
{if(n 2)return Fib(n - 1) Fib(n - 2);elsereturn 1;
}
int main()
{int n 0;scanf(%d, n);int ret Fib(n);printf(第%d个斐波那契数是%d\n, n, ret);return 0;
}
1.2 算法的复杂度
算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源。 衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期计算机的存储容量很小。 所以对空间复杂度比较在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注算法的空间复杂度。
2.时间复杂度
2.1 什么是时间复杂度
算法的时间复杂度是一个函数它描述了该算法的运行时间。 一个算法所花费的时间与其中语句的执行次数成正比所以算法中的基本操作的执行次数为算法的时间复杂度。即找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度。
//计算fun1中count语句总共执行了多少次
void Func1(int N)
{int count 0;for (int i 0; i N ; i) {for (int j 0; j N ; j){count;}}for (int k 0; k 2 * N ; k){count; }int M 10;while (M--) {count; }printf(%d\n, count);
}分析 从上述代码中可以看出Func1的时间复杂度函数为F(N) N * N 2 * N 10 ▶ N 10 F(N) 130 ▶ N 100 F(N) 10210 ▶ N 1000 F(N) 1002010 从上述就可以看出N越大对结果的影响就越小。实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法 (估算)
2.2 大O渐进表示法 (估算)
大O符号 (Big O notation)用于描述函数渐近行为的数学符号 推导大O阶的方法 1.用常数取代运行时间中的所有加法常数 2.在修改后的运行次数函数中只保留最高项3. 如果最高阶项存在且系数不是则去除与这个项相乘的系数得到的结果就是大O阶 另外有些算法的时间复杂度存在最好平均和最坏情况,例如在一个长度为N的数组中查找一个数据X最好的情况1次就找到平均的情况N/2就找到最坏的情况N次才找到
最坏情况:任意输入规模的最大运行次数(上界)平均情况:任意输入规模的期望运行次数最好情况:任意输入规模的最小运行次数(下界) 对于上面的Func1函数使用大O的渐近表示法后时间复杂度为O(N^2) ▶ N 10 F(N) 100 ▶ N 100 F(N) 10000 ▶ N 1000 F(N) 1000000 在实际中一般情况关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为O(N)
2.3 常见的时间复杂度计算举例
2.3.1 实例1:
void Func2(int N)
{int count 0;for (int k 0; k 2 * N ; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
}分析 Func2的时间复杂度函数为F(N) (2N 10) 使用大O渐近表示法保留影响最大的一项、去掉系数则为O(N)
2.3.2 实例2:
void Func3(int N, int M)
{int count 0;for (int k 0; k M; k){count;}for (int k 0; k N ; k){count;}printf(%d\n, count);
}分析 Func3的时间复杂度函数为F(N) (M N) 使用大O渐近表示法不一定只有一个未知数所以这里可以写O(M N) 也可以写成如下 ▶ O(ax(M, N))取M和N的较大值 ▶ O(M)如果能说明M远大于N ▶ O(N)如果能说明N远大于M ▶ O(N)/O(M)如果能说明M和N差不多大
2.3.3 实例3:
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);}分析 Func4的时间复杂度函数为F(N) (100) 使用大O渐近表示法使用代表常数所以O(1)
2.3.4 实例4
void BubbleSort(int* a, int n)
{assert(a);for (size_t end n; end 0; --end){int exchange 0;for (size_t i 1; i end; i){if (a[i-1] a[i]){Swap(a[i-1], a[i]);exchange 1;}}if (exchange 0)break;}
} 分析 这是冒泡排序的一个优化版本在一趟排序的过程中如果没有交换数据的话它就会跳出循环 BubbleSort的时间复杂度函数为F(N) ((n - 1) (n - 2) … 2 1) 发现这是一个等差数列利用公式整合得F(N) n * n / 2 - F(N) N^2 / 2 使用大O渐近表示法 (最坏情况)O(N^2) -N^2的数量级 (平均情况)O(N^2) - N^2 / 2 (最好情况)O(N)-只是比较了N-1次本身就有序的时候
2.3.5 实例5:
//二分查找折半查找数组有序
int BinarySearch(int* a, int n, int x)
{assert(a);int begin 0;int end n-1;while (begin end){int mid begin ((end-begin)1);if (a[mid] x)begin mid1;else if (a[mid] x)end mid;elsereturn mid;}return -1;
}分析 BinarySearch依然存在最好、平均、最坏的情况 BinarySearch的时间复杂度函数为F(N) N / 2 / 2 / 2 … /2 1 使用大O渐近表示法O(log₂N)或O(logN) - 因为底数不好打出来有时候一般也这样写 xN / 2^x 1 - N 2^x - log₂N x (最坏情况)O(logN) -找了一遍 (最好情况)O(1)-在中间位置
2.3.6 实例6:
long long Fac(size_t N)
{if(0 N)return 1;//0!1 阶乘return Fac(N-1)*N;
}每个里面是常数次总共递归了n1次 分析 Fac的时间复杂度为F(N) (N1) 使用大O渐近表示法O(N)
2.3.7 实例7:
long long Fib(size_t N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
}分析 2^0 2^1 2^2 2^3 … 2^(N-3) 2^(N-2) 2^(N-1)等比数列-缺少常数 使用大O渐近表示法O(2^N)
2.3.8 实例8
//计算strchr的时间复杂度
const char*strchr(const char*str,int character)while(*str)
{if(*strcharacter)return str;str;
}时间复杂度为O(N)
2.4 常见的复杂度对比 3.根据对时间复杂度的要求编写代码
3.1 消失的数字
17.04. 消失的数字 题述数组nums包含从0到n的所有整数但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗 示例 1 ---------- 示例 2 输入[3,0,1] ----- 输入[9,6,4,2,3,5,7,0,1] 输出2 ----------- 输出8
核心思想 方法一先排序再依次判断第个数和之后的数相加是否等于第个数若不等则它们的和就是缺失的数————冒泡排序时间复杂度O(N²)快速排序时间复杂度O(N*log₂N) 方法二求和如果有n个数则…最后整体再减去数组中的值的累加就是缺失的数————时间复杂度O(N) 方法三异或使用跟—之间的数异或再跟数值中的值异或异或的结果就是缺失的数 方法二 IO型
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
int FindNum1(int arr[], int n)
{int i 0;//把n1个数加起来放在sum里int sum 0;for (i 0; i n 1; i){sum i;}//再减去数组里的数结果就是缺失的数for (i 0; i n; i){sum - arr[i];}return sum;
}
int main()
{int arr[20] { 0 };//规定输入有n个数int n 3;int i 0;for (i 0; i n; i){scanf(%d, arr[i]);}int ret FindNum1(arr, n);printf(%d\n, ret);return 0;
}方法三 IO型
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
int FindNum2(int arr[], int n)
{int i 0;//把n1个数异或后放在sum里int val 0;for (i 0; i n 1; i){val ^ i;}//再和数组里的异或剩下的就是缺失的数for (i 0; i n; i){val ^ arr[i];}return val;
}
int main()
{int arr[20] { 0 };//n个数int n 3;int i 0;for (i 0; i n; i){scanf(%d, arr[i]);}int ret FindNum2(arr, n);printf(%d\n, ret);return 0;
}接口型
int missingNumber(int* nums, int numsSize)
{int x0;for(int i0;inumsSize;i){x^nums[i];}for(int j0;jnumsSize1;j){x^j;}return x;
}3.2 轮转数组
189. 轮转数组 题述给定一个数组将数组中的元素向右移动 k 个位置其中 k 是非负数。要求时间复杂度O(N) 示例 1: 输入: nums [1,2,3,4,5,6,7], k 3 输出: [5,6,7,1,2,3,4] 核心思想 方法一这是个字符的旋转拷贝一份最右值数组中的值都向右挪劫次再把拷贝的内容放在开头在外面套一层循环就可以旋转k个字符了————时间复杂度O(N²) 分析O(k*N)最坏情况下 k为N-1或N-1的倍数-O(N²) 方法二空间换时间————时间复杂度O(N)空间复杂度O(N) 方法三三步翻转法————时间复杂度O(N),空间复杂度O(N)–调用一个栈帧
方法二 IO型
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includestring.h
#includeassert.h
char* Rotate1(const char* arr, int len, int k, char* temp)
{assert(arr temp);//拷贝一份新空间的首地址用于返回char* tem temp;//我们当前写的这个代码是不适用于旋转的字符k大于目标数组的arr所以如果k大于arr时我们需要看看k有几个arr,并把它排除掉k % len;int i 0;//先拷贝后半部分的字符for (i len - k; i len; i){*temp *(arr i);temp;}//再拷贝前半部分的字符for (i 0; i len - k; i){*temp *(arr i);temp;}return tem;
}
int main()
{//temp为新的空间char temp[20] { 0 };//arr存储要旋转的字符串char arr[20] { 0 };gets(arr);//旋转k个字符int k 0;scanf(%d, k);char* ret Rotate1(arr, strlen(arr), k, temp);printf(%s\n, ret);return 0;
}接口型
void rotate(int* nums, int numsSize, int k)
{if(knumsSize)k%numsSize;int *tmp(int*)malloc(sizeof(int)*numsSize);memcpy(tmp,numsnumsSize-k,sizeof(int)*k);memcpy(tmpk,nums,sizeof(int)*(numsSize-k));memcpy(nums,tmp,sizeof(int)*(numsSize));free(tmp);tmpNULL;
}方法三 IO型
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includeassert.h
#includestring.h
void reverse(char* left, char* right)
{assert(left right);while (left right){char temp *left;*left *right;*right temp;left;right--;}
}
void string_right_rotation(char* str, int k)
{assert(str);int len strlen(str);//我们当前写的这个代码是不适用于旋转的字符k大于目标数组的arr所以如果k大于arr时我们需要看看k有几个arr,并把它排除掉k % len;reverse(str, str (len - k - 1));//第一部分reverse(str (len - k), str len - 1);//第二部分reverse(str, str len - 1);//整体
}
int main()
{//arr存储要旋转的字符串char arr[20] { 0 };gets(arr);//旋转k个字符int k 0;scanf(%d, k);string_right_rotation(arr, k);printf(%s\n, arr);return 0;
}接口型
void reverse(int*nums,int begin, int end)
{while(beginend){int tmpnums[begin];nums[begin]nums[end];nums[end]tmp;begin;--end;}
}void rotate(int* nums, int numsSize, int k)
{if(knumsSize)k%numsSize;reverse(nums,0,numsSize-k-1);reverse(nums,numsSize-k,numsSize-1);reverse(nums,0,numsSize-1);
}4.空间复杂度
4.1 什么是空间复杂度
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度。 空间复杂度不是程序占用了多少bytes的空间因为没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似也使用大O渐进表示法。 注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
4.2 常见的空间复杂度计算举例
4.2.1 实例1:
void BubbleSort(int* a, int n)
{assert(a);for (size_t end n; end 0; --end){int exchange 0;for (size_t i 1; i end; i){if (a[i-1] a[i]){Swap(a[i-1], a[i]);exchange 1;}}if (exchange 0)break;}
} 分析 相比时间复杂度来说时间是累计的但空间不是累计的(可以重复利用)//end、exchange、i 额外的空间 BubbleSort的空间复杂度为F(N) () 使用大O渐近表示法O()
4.2.2 实例2:
long long* Fibonacci(size_t n)
{if(n0)return NULL;long long * fibArray (long long *)malloc((n1) * sizeof(long long));fibArray[0] 0;fibArray[1] 1;for (int i 2; i n ; i){fibArray[i] fibArray[i - 1] fibArray[i - 2];}return fibArray;}分析malloc((n1) 使用大O渐近表示法O(N)
4.2.3 实例3:
long long Fac(size_t N)
{if(N 1)return 1;return Fac(N-1)*N;
}分析Fac(N)-Fac(N-1)-.……-Fac(1)建立N个栈帧 使用大O渐近表示法O(N)
4.2.4 实例4:
long long Fib(size_t N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
}//VS2019-窗口-调用堆栈-双击看内存的变量 分析栈帧销毁了可重复利用所以递归算法的空间复杂度取决于每次调用的空间复杂度和最大递归深度Fib(N)-Fib(N-1)-.……-Fib(1) 使用大O渐近表示法O(N)
5.根据对空间复杂度的要求编写代码
5.1 移除元素
27. 移除元素 题述给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。 不要使用额外的数组空间必须仅使用O(1) 额外空间并 原地 修改输入数组。
示例 1 输入nums [3,2,2,3], val 3 输出2, nums [2,2] 示例 2 输入nums [0,1,2,2,3,0,4,2], val 2 输出5, nums [0,1,4,0,3]
提示 0 nums.length 100 0 nums[i] 50 0 val 100
接口型
int removeElement(int* nums, int numsSize, int val)
{int dest0,src0;while(srcnumsSize){if(nums[src]!val){nums[dest]nums[src];dest;}src;}return dest;
}6.总结
今天我们认识并学习了时间复杂度和空间复杂度的相关概念通过实例进行了分析和一些OJ题举例。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
