数据结构与算法①(第一章复杂度知识点)(大O渐进表示法)（上）：https://developer.aliyun.com/article/1513299
实例6：计算递归版斐波那契数 Fib 的时间复杂度
递归算法：递归次数 * 每次递归调用次数
long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }
答案：O(2^N)
解析：通过计算分析发现基本操作递归了2^N次，时间复杂度为O(2^N) 。
使用大O渐进法表示结果如下：
2.3空间复杂度的概念
空间复杂度的定义：空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度。 空间复杂度并不是程序占用了多少bytes的空间，前面在介绍算法复杂度的时候就提到了如今我们已经不再关注 "空间" ，所以关注程序占用多少byte的空间是没有太大意义的。空间复杂度算的是变量的个数！ 此外，空间复杂度的计算规则基本和时间复杂度没有什么区别，同样也使用 大O渐进表示法。
注意事项：函数运行时所需要的栈空间（即存储参数、局部变量和一些寄存器信息等）在编译期间就已经确定好了，因此空间复杂度主要是通过函数在运行的时候显式申请的额外空间来决定。
实例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; } } }
解析：使用了常数个额外空间，所以空间复杂度为 O(1) 。
实例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; }
解析：malloc 动态开辟了N个空间，空间复杂度为 O(N)
实例3：计算递归版阶乘 Fac 的空间复杂度
long long Fac(size_t N) { if (0 == N) return 1; return Fac(N - 1) * N; }
答案：O(N)
解析：递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N) 。
2.4常见复杂度对比
大O对比图：
3.笔试选择题
（答案放最后）
3.1下列有关大O表示法的说法错误的是
A.大O表示法只是对程序执行时间的一个估算
B.大O表示法只保留最高阶项
C.大O表示法会保留一个系数来更准确的表示复杂度
D.大O表示法一般表示的是算法最差的运行时间
3.2分析以下函数的时间复杂度
void fun(int n) { int i=l; while(i<=n) i=i*2; }
A.O(n)
B.O(n^2)
C.O(nlogn)
D.O(logn)
3.3分析以下程序的时间复杂度
for(int i=0;i<n;i++) for(int j=0;j<n;j++) a[i][j]=i*j;
A.O(n)
B.O(n^2)
C.O(nlogn)
D.O(logn)
3.4下面算法的时间复杂度是（ ）
int f ( unsigned int n ) { if (n == 0 || n==1) return 1; else return n * f(n-1); }
A.O(n)
B.O(n^2)
C.O(nlogn)
D.O(logn)
3.5给定一个整数sum，从有N个有序元素的数组中寻找元素a，b，使得a+b的结果最接近sum，最快的平均时间复杂度是（ ）
A.O(n)
B.O(n^2)
C.O(nlogn)
D.O(logn)
3.6分析以下函数的空间复杂度（ ）
int** fun(int n) { int** s = (int**)malloc(n * sizeof(int*)); while (n--) s[n] = (int*)malloc(n * sizeof(int)); return s; }
A.O(n)
B.O(n^2)
C.O( 1 )
D.O(nlogn)
3.7如果一个函数的内部中只定义了一个二维数组a[3][6]，请问这个函数的空间复杂度为（ ）
A.O(n)
B.O(n^2)
C.O( 1 )
D.O(m*n)
3.8设某算法的递推公式是T(n)=T(n-1)+n，T(0)=1，则求该算法中第n项的时间复杂度为（）
A.O(n)
B.O(n^2)
C.O(nlogn)
D.O(logn)
3.9（答案）
1答案：C
解析：大O是一个渐进表示法，不会去表示精确的次数，cpu的运算速度很快，估计精确的没有意义。
2答案：D
解析: 此函数有一个循环，但是循环没有被执行n次，i每次都是2倍进行递增，所以循环只会被执行log2(n)次。
3答案：B
解析：程序有两次循环，每个循环都有n次操作，所以时间复杂度为n^2
4答案：A
解析：此函数会被递归调用n - 1次，每次操作都是一次，所以时间复杂度为n
5答案：A
解析：此题目中，数组元素有序，所以a,b两个数可以分别从开始和结尾处开始搜，
根据首尾元素的和是否大于sum,决定搜索的移动，整个数组被搜索一遍，就可以得到结果，所以最好时间复杂度为n
6答案：B
解析：此处开辟的是一个二维数组，数组有n行，每行分别有1,2,3,...n列，所以是n(n + 1)/2个元素空间，空间复杂度为n^2
7答案：C
解析：函数内部数组的大小是固定的，不论函数运行多少次，所需空间都是固定大小的，因此空间复杂度为O(1)
8答案: A
解析：
T(n)
=T(n-1)+n
=T(n-2)+(n-1)+n
=T(n-3)+(n-2)+(n-1)+n
...
=T(0)+1+2+...+(n-2)+(n-1)+n
=1+1+2+...+(n-2)+(n-1)+n
从递推公式中可以看到，第n项的值需要从n-1开始递归，一直递归到0次结束，共递归了n-1次
所以时间复杂度为n
本篇完。(附下篇对应OJ链接)
下一篇更新这一篇的相关力扣OJ。
