2.空间复杂度
知识点：
空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。 空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。
细节：
函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时申请的额外空间来算（即函数的参数一般不用算到该函数的空间复杂度中去）
一般直接数变量个数即可，除非开辟申请了额外的空间（malloc(n * sizeof(int) )
练习：
例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(N ^ 2) : n - 1 + n - 2 + ... + 1 = n(a1+an)/2 = n ^ 2 //空间复杂度是：O(1): 总共就3个变量
例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; } //空间复杂度是：O(N) : malloc 开辟了一个新的空间 大约是N个 （这里并不关心byte）
例3：
long long Fac(size_t N) { if(N == 0) return 1; return Fac(N-1)*N; } //因为递归，每个递归建立的栈帧都要创建变量，所以 //空间复杂度是： O (N)
例4:
long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }
其空间复杂度是：O(N)、时间复杂度是：O(2^N)
因为：
知识点：当栈帧空间归还给操作系统后，下一次开辟栈帧可能会占用同一片区域。
本章完。预知后事如何，暂听下回分解。
