在前一讲（不复杂的时间复杂度）中，我们介绍了「时间复杂度」。
和（渐进）时间复杂度一样，「空间复杂度」（space complexity）也不是去计算程序具体占用了多少的空间，而是反映算法运行过程中大约会临时占用多少存储空间的一个趋势。我们同样更关心的是所需空间是如何随着输入数据的增长而增长的。
大O表示法 \(O(f(n))\) 在数学上的定义是上限趋近于 \(f(n)\) 函数的合集。它可以被用于表示时间复杂度，同样也可以被用于表示空间复杂度。
我们将空间复杂度定义为 \(S(n)\)，通过大O表示法 \(O(f(n))\) 来表示，记为\(S(n) = O(f(n))\)。
空间复杂度\(O(1)\)
int sum(int x, int y, int z) {
int r = x + y + z;
return r;
}
该算法无论怎样都是分配3个存储单元给参数，1个存储单元给本地变量，所以该算法的空间复杂度为\(O(1)\)，标记为\(S(n) = O(1)\)。
空间复杂度\(O(n)\)
int sum(int a[], int n) {
int r = 0;
for (int i = 0; i < n; ++i) {
r += a[i];
}
return r;
}
该算法需要分配n个存储单元给数组\(a\)，还有3个存储单元给变量\(n\)，\(r\)，\(i\)，但它们不随数据规模的增长而改变，n才是主导性因素，所以该算法的空间复杂度为\(O(n)\)。
其他情况
如果一个函数\(A\)需要M个存储单元（包括本地变量和参数），并且它调用了一次函数B。函数B需要N个存储单元。那么函数A就总共需要M+N个存储空间。如果它调用了三次函数B，也仍然只需要M+N的存储空间。原因是因为B在调用时会将其压入栈中(push)，在一次调用结束时会将其推出栈(pop)，等到新一次的调用时再将其重新压入栈，所以这份空间一直在被重复利用，所以不会需要更多存储空间。
那如果函数\(A\)是个递归函数，它反复调用自身n次呢？那它就需要\(M \times N\)个存储空间，即空间复杂度为\(O(n^2)\)。这是因为只有当函数调用到最后一层时才会结束一层调用，而之前的调用由于没有结束，所以会被一直压入栈中，如下图所示，空间无法得以重复利用，所以空间复杂度为\(O(n^2)\)。
此外，如果传递的是指针或引用，由于它们都会指向原本的内存空间，因此不需要分配新的存储单元。
后记（摘选自此文）
如今硬件的存储量级都比较大，一般不会为了稍微减少一点儿空间复杂度而大动干戈，更多的是去想怎么优化算法的时间复杂度。因此衍生出了用「空间换时间」的做法，并且成为常态。
比如我们在求解斐波那契数列的时候我们可以直接用公式去递归求，用哪个求哪个，同样也可以先把很多结果都算出来保存起来，然后用到哪个直接调用，这就是典型的用空间换时间的做法，但是你说这两种具体哪个好，伟大的马克思告诉我们「具体问题具体分析」。
总结
本讲介绍了衡量算法在空间维度上的指标——空间复杂度。常见的空间复杂度量级有\(O(1)\)和\(O(n)\)。本讲还介绍了当函数调用其他函数和调用自身函数这两种情形下的空间占用情况。由于如今硬件的存储量级都较大，空间换时间的做法成为常态。
参考
- https://courses.cs.northwestern.edu/311/html/space-complexity.html
- https://www.sohu.com/a/271774788_115128
创作不易，点个赞再走叭～