时间复杂度练习及解析：
实例1:
// 计算Func2的时间复杂度 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); }
答案是O(N)，2N+10
实例2:
// 计算Func3的时间复杂度？ 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); }
实例3:
// 计算Func4的时间复杂度 void Func4(int N) { int count = 0; for (int k = 0; k < 100; ++ k) { ++count; } printf("%d\n", count); }
实例4:
/ 计算strchr的时间复杂度 const char * strchr ( const char * str, int character );
实例5:
// 计算BubbleSort的时间复杂度 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; } }
实例6:
// 计算BinarySearch的时间复杂度 int BinarySearch(int* a, int n, int x) { assert(a); int begin = 0; int end = n-1; // [begin, end]：begin和end是左闭右闭区间，因此有=号 while (begin <= end) { int mid = begin + ((end-begin)>>1); if (a[mid] < x) begin = mid+1; else if (a[mid] > x) end = mid-1; else return mid; } return -1; }
实例7:
// 计算阶乘递归Fac的时间复杂度 long long Fac(size_t N) { if(0 == N) return 1; return Fac(N-1)*N; }
实例8：
// 计算斐波那契递归Fib的时间复杂度？ long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }
实例答案及分析：
- 实例1基本操作执行了2N+10次，通过推导大O阶方法去掉常量，系数，时间复杂度为 O(N)
- 实例2基本操作执行了M+N次，有两个未知数M和N，时间复杂度为 O(N+M)
- 实例3基本操作执行了10次，通过推导大O阶方法将常量改为1，时间复杂度为 O(1)
- 实例4，strchr函数相当于
while(*str) { if(*str == character) return str; else str++; }
- 实际上就是查找字符串元素并返回该位置的指针，但是我们并不知道字符串的大小，所以基本操作执行最好1次，最坏N次，时间复杂度一般看最坏，时间复杂度为 O(N)
- 实例5冒泡排序，
第一趟需要比n-1次，第二趟比较n-2次，n-1 + n-2 +……+2+1
基本操作执行最好N次，最坏执行次数为（首项+末项）*项数/2，即(N*(N-1)/2次，通过推导大O阶方法+时间复杂度一般看最坏，时间复杂度为 O(N2) - 实例6 二分查找
基本操作执行最好1次，最坏的情况是只剩一个元素，O(logN)次，时间复杂度为 O(logN)
logN在算法分析中表示是底数为2，对数为N。 - 实例7通过计算分析发现基本操作递归了N次，每次调用了常数次，所以时间复杂度为O(N)。
- 实例8斐波那契数列
根据大O复杂度表示法通过计算分析发现基本操作递归了2N 次，时间复杂度为O(2N)。
空间复杂组练习及解析：
实例1：
// 计算BubbleSort的空间复杂度？ 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; } }
实例2：
// 计算Fibonacci的空间复杂度？ // 返回斐波那契数列的前n项 long long* Fibonacci(size_t n) { if(n==0) return NULL; long long * fibArray = (long long *)malloc((n+1) * 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; }
实例3：
// 计算阶乘递归Fac的空间复杂度 long long Fac(size_t N) { if(N == 0) return 1; return Fac(N-1)*N; }
实例4：
// 计算斐波那契递归Fib的空间复杂度？ long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }
实例答案及分析：
- 实例1使用了常数个额外空间，所以空间复杂度为 O(1)。
- 实例2动态开辟了N个空间，空间复杂度为 O(N)。
- 实例3递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)。
- 可以参考时间复杂度的图来理解，空间是可以重复利用的Fib(N-1)和Fib(N-2)实际上是调用同一块空间，可以理解为每一层建立一个函数栈帧，所以空间复杂度为O(N)。
这里我们可以通过对下面两个函数调用来理解，下面是函数栈帧开辟空间的演示
如图程序运行后，输出的第一次调用和第二次调用的两个变量的地址是一样的，
调用这两个函数时开辟的空间在同一个位置，斐波那契数中Fib(N-1)和Fib(N-2)的调用与之类似。
复杂度的oj练习
这里我们就会有很多思路:
思路1：求和相减
（n+1)*n/2 - (数组中所有相加)
时间复杂度：O(N)
空间复杂度：O(1)
思路2： qsort排序/ 冒泡排序
时间复杂度：O(logN*N) O(N2)
空间复杂度：O(logN) O(1)
思路3：异或（不开辟新数组）
//思路1 int missingNumber(int* nums, int numsSize) { int N = numsSize; int ret = N*(N+1)/2; for(int i = 0;i < numsSize;++i) { ret -= nums[i]; } return ret; } //思路3 int missingNumber(int* nums, int numsSize) { int N = numsSize; int x = 0; for(size_t i = 0;i < numsSize; ++i) { x ^= nums[i]; } for(size_t j = 0;j < N+1;++j) { x ^= j; } return x; }
2、旋转数组OJ链接
代码：
第一种思路，效率太低，这里不作讲解，只给出参考
思路二：
void rotate(int* nums, int numsSize, int k) { k %=numsSize;//为避免k>numSize //numsSize是变长数组 int tmp[numsSize]; //后k个拷贝前面 int j = 0; for(int i = numsSize-k;i<numsSize;++i) { tmp[j] = nums[i]; ++j; } //前n-k个拷贝到后面 for(int i = 0;i<numsSize-k;++i) { tmp[j] = nums[i]; ++j; } //拷贝回去 for(int i = 0;i<numsSize;++i) { nums[i] = tmp[i]; } }
思路三:
void reverse(int *a, int begin, int end)//交换函数封装 { while(begin < end) { int tmp = a[begin]; a[begin] = a[end]; a[end] = tmp; ++begin; --end; } } void rotate(int*nums,int numsSize,int k) { k %=numsSize; reverse(nums,0,numsSize-k-1);//调用函数 reverse(nums,numsSize-k,numsSize-1);//调用函数 reverse(nums,0,numsSize-1);//调用函数 }
结语：
这里我们关于【数据结构复杂度】的内容就介绍完了，文章中某些内容我们之前有介绍，所以只是一笔带过，还请谅解。
希望以上内容对大家有所帮助👀，如有不足望指出🙏
前路漫漫！努力变强💪💪 吧！！
