1.空间复杂度
空间复杂度也是一个数学表达式，
是对一个算法在运行过程中临时占用存储空间大小的量度。
他也是用大O渐进表示法。
1.1 例子
例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; }
这里用malloc开辟了n个以上的空间，
所以它的空间复杂度是O(N)。
例3：
阶乘递归：
long long Fac(size_t N) { if (N == 0) return 1; return Fac(N - 1) * N; }
这段代码，
因为函数递归，建立函数栈帧，
而函数栈帧里有常数个（空间）变量开辟，
而这段代码，建立了N+1个函数栈帧，
所以它的空间复杂度是O(N)。
1.2 空间的特殊性质
例4：
long long Fib(int N) { if (N < 3) return 1; return Fib(N - 1) + Fib(N - 2); }
这段代码的时间复杂度是O(2的N次方)。
但是，它的空间复杂度呢？
实际上，他的空间复杂度是O(N)，而不是O(2的N次方)。
为什么呢？
因为函数递归的过程中会建立栈帧，而这段代码在进行递归的时候，
并不会一直递归到最后才返回，
当它递归到一定程度是，会有函数提前返回，
导致栈帧销毁，当新的栈帧建立的时候，
空间就会被重复使用，
例：
#include void f1() { int b = 0; printf("%p\n", &b); } void f2() { int a = 0; printf("%p\n", &a); } int main() { f1(); f2(); return 0; }
输出：
我们发现，当f1函数的栈帧销毁后，
f2函数栈帧建立，创建的变量地址与f1中创建的变量地址相同，
这就是空间重复利用的特性。
例：
#include void f1() { int b = 0; printf("%p\n", &b); } void f2() { int a = 0; printf("%p\n", &a); f1(); } int main() { f2(); return 0; }
输出：
当f1函数的栈帧没有销毁，
f2函数的变量自然用不了f1函数的空间，
所以他们的地址当然不同了。
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
