例6.二分算法的时间复杂度
1. // 计算BinarySearch的时间复杂度？ 2. int BinarySearch(int* a, int n, int x) 3. { 4. assert(a); 5. int begin = 0; 6. int end = n-1; 7. // [begin, end]：begin和end是左闭右闭区间，因此有=号 8. while (begin <= end) 9. { 10. int mid = begin + ((end-begin)>>1); 11. if (a[mid] < x) 12. begin = mid+1; 13. else if (a[mid] > x) 14. end = mid-1; 15. else 16. return mid; 17. } 18. return -1; 19. }
最好情况：
第一次就找到了，所以时间复杂度：O(1)
最坏情况：
找到就剩最后一个数才找到
设数组中有N个数，一共找了X次
所以
N/(2*2*2*2.....*2)=1
一共X个2，即：2^X=N -> X=logN(注意这是一个简写，真正的意思是以2为底的N的对数）
所以取最坏情况 ，时间复杂度：O(logN)
例7.阶乘递归Fac的时间复杂度
1. long long Fac(size_t N) 2. { 3. if(0 == N) 4. return 1; 5. return Fac(N-1)*N; 6. }
不难看出一共会递归N次，所以时间复杂度为：O(N)
例8.斐波那契递归的时间复杂度
1. // 计算斐波那契递归Fib的时间复杂度？ 2. long long Fib(size_t N) 3. { 4. if(N < 3) 5. return 1; 6. return Fib(N-1) + Fib(N-2); 7. }
对于这种较复杂的时间复杂度的计算可以通过画图来观察；
三角形那一块是缺失的部分;
通过上图我们发现，一共会执行F(N)=2^N-X(这个X是一个常数）
所以时间复杂度：O(2^N)
四.常见时间复杂度对比
一般算法常见的复杂度如下：
五.空间复杂度
概念
1.空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度；
2.空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数；
3.空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法；
注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
例1
1. // 计算BubbleSort的空间复杂度？ 2. void BubbleSort(int* a, int n) 3. { 4. assert(a); 5. for (size_t end = n; end > 0; --end) 6. { 7. int exchange = 0; 8. for (size_t i = 1; i < end; ++i) 9. { 10. if (a[i-1] > a[i]) 11. { 12. Swap(&a[i-1], &a[i]); 13. exchange = 1; 14. } 15. } 16. if (exchange == 0) 17. break; 18. } 19. }
显然上面的代码带上形参共有5个变量，根据大O渐进法的规则，空间复杂度：O(1);
例2
1. // 计算Fibonacci的空间复杂度？ 2. // 返回斐波那契数列的前n项 3. long long* Fibonacci(size_t n) 4. { 5. if(n==0) 6. return NULL; 7. long long * fibArray = (long long *)malloc((n+1) * sizeof(long long)); 8. fibArray[0] = 0; 9. fibArray[1] = 1; 10. for (int i = 2; i <= n ; ++i) 11. { 12. fibArray[i] = fibArray[i - 1] + fibArray [i - 2]; 13. } 14. return fibArray; 15. }
上述代码除了5个变量外，还有malloc函数开辟的n+1个空间，F(N)=n+6，
即空间复杂度：O(n)
例3
1. // 计算阶乘递归Fac的空间复杂度？ 2. long long Fac(size_t N) 3. { 4. if(N == 0) 5. return 1; 6. return Fac(N-1)*N; 7. }
这是一个递归，每次进入递归时都会再次创建变量，建立栈帧，返回时销毁变量，上述代码啊一共会递归N次，所以会创建N个变量，
即空间复杂度：O(N)
😸😼到此本篇文章就结束了，这是数据结构的第一篇文章，往后也会继续更新的；🤖👻
🥰😍若本篇文章有错误或是有建议，欢迎小伙伴们提出哦；😄🤩
😃😁希望各位大佬们多多支持博主~🤩😍
🦖🐲谢谢你的阅读。🐯🦁
