空间复杂度

空间复杂度是时间复杂度的内存孪生：当输入变大时，算法需要多少额外内存？就像我们为时间数步骤一样，这里我们数存储——多少个单元、多深的待返回调用栈、多大的辅助数组——把它写成输入规模 n 的函数，并用大 O 描述它的增长。时间告诉你能不能跑完；空间告诉你能不能装得下。一个跑得快、却要求比机器内存还多的程序，会干脆崩掉，所以两种代价都要紧。

我们通常指的是辅助空间：算法在它拿到的输入之外所用的额外内存。把一串数字求和，无论列表多长都只要一个累加值，所以是 O(1) 额外空间。归并排序在合并时会建临时数组，需要 O(n) 额外空间。递归算法也悄悄占内存：每个未返回的调用都压在调用栈上，所以一个深入 n 层的递归要花 O(n) 栈空间，深入 log n 层的则花 O(log n)——这是初学者常常忘掉的一笔真实开销。

认得空间复杂度，会揭示出整个编程里最常见的一种取舍：时间换空间。你常常可以靠「记住更多」来让程序更快（一个哈希表或一份记忆化缓存，能把反复的 O(n) 扫描变成 O(1) 查找，代价是内存），或者靠「重新算」来省内存（省下空间，花掉时间）。同时知道两种复杂度，能让你诚实地把你的算法放到那条取舍线上，而不是日后才被它吓一跳。