时间与空间复杂度（详解）（上）：https://developer.aliyun.com/article/1624366
实例6
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);//防溢出 //int mid=(bigin+end)/2; if (a[mid] < x) begin = mid+1; else if (a[mid] > x) end = mid-1; else return mid; } return -1; }
基本操作执行最好 1 次，最坏 O(logN) 次，时间复杂度为 O(logN)
N/2/2/2/2/.../2=1
假设查找x次->2^x=N->x=log2N
ps ： logN 在算法分析中表示是底 数为2 ，对数为 N 。有些地方会写成 lgN 。
实例 7
long long Fac(size_t N) { if(0 == N) return 1; return Fac(N-1)*N; }
Fac(N)->Fac(N-1)->Fac(N-2)->...->Fac(0)
计算分析发现基本操作递归了N+1次，时间复杂度为O(N)。
递归时间复杂度：所有递归调用次数累加
实例 8
long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }
通过计算分析发现基本操作递归了2^N次，时间复杂度为O(2^N)。
累计调用：2^0+2^1+...2^(N-2) =2^(N-1)-1
改进：
long long Fib(size_t n){ long long f1=1; long long f2=1; long long f3=0; for(size_t i=3;i<=N;i++){ f3=f1+f2; f1=f2; f2=f3; } }
时间复杂度：O(N)
若数字太大,也不行，毕竟long long 存储数据有限,可以考虑字符串。
3.空间复杂度
空间复杂度也是一个数学表达式，是对一个算法在运行过程中 临时占用存储空间大小的量度 。
空间复杂度不是程序占用了多少 bytes 的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似，也使用 大 O 渐进表示法 。
注意： 函数运行时所需要的栈空间 ( 存储参数、局部变量、一些寄存器信息等 ) 在编译期间已经确定好了，因 此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
实例 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; } }
使用了常数个额外空间，所以空间复杂度为 O(1)
实例2
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; }
动态开辟了N个空间，空间复杂度为 O(N)
实例3
long long Fac(size_t N) { if(N == 0) return 1; return Fac(N-1)*N; }
递归调用了 N 次，开辟了 N 个栈帧，每个栈帧使用了常数个空间。空间复杂度为 O(N)
4. 常见复杂度对比
一般算法常见的复杂度如下：
