【算法图解】空间复杂度：内存也是钱
时间复杂度大家都知道，但空间复杂度同样重要。小明带你理解算法对内存的消耗，以及如何在时间和空间之间做权衡。
7 分钟阅读
小明
【算法图解】空间复杂度：内存也是钱
在之前的时间复杂度文章里，我们讨论的是算法"跑多快"的问题。但一个算法的好坏，不仅看它跑得快不快，还要看它占多大地方。
想象一下，你写了一个超快的算法，但它需要 100GB 的内存。结果你的服务器只有 16GB。这时候，再快也没用——程序直接 Out of Memory 崩掉了。
今天，小明就来聊聊算法的另一半故事：空间复杂度（Space Complexity）。
一、什么是空间复杂度？
空间复杂度描述的是：算法在运行过程中，临时占用的额外存储空间与输入规模 n 之间的关系。
注意关键词：额外和临时。
- 输入数据本身占用的空间，通常不算在内（那是你逃不掉的）。
- 我们关心的是算法运行时额外申请的空间。
二、常见的空间复杂度
| 复杂度 | 含义 | 例子 |
|---|---|---|
| O(1) | 常数空间 | 不管数据多大，只需要几个固定的变量 |
| O(n) | 线性空间 | 需要一个和输入同等规模的数组 |
| O(n²) | 平方空间 | 需要一个二维矩阵 |
| O(log n) | 对数空间 | 递归栈的深度（如二分查找） |
三、实战分析
3.1 O(1) 空间：原地修改
function swap(arr, i, j) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
这里只用到了一个临时变量 temp，不管数组多大，额外空间都是固定的。
3.2 O(n) 空间：需要辅助数组
function copyArray(arr) {
const newArr = [];
for (const item of arr) {
newArr.push(item);
}
return newArr;
}
我们创建了一个和原数组一样大的新数组，所以空间复杂度是 O(n)。
3.3 递归的空间复杂度
递归是个容易被忽视的空间杀手。每次递归调用都会在栈上分配一块空间（保存局部变量、返回地址等）。
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}
这个阶乘函数，会递归 n 层，所以空间复杂度是 O(n)。
四、时间 vs 空间：你只能选一个？
很多时候，时间和空间是此消彼长的关系。
例子：斐波那契数列
- 递归版：时间 O(2^n)，空间 O(n)（栈深）—— 时间爆炸。
- 记忆化递归：时间 O(n)，空间 O(n)（缓存 + 栈）—— 用空间换时间。
- 迭代版：时间 O(n)，空间 O(1)—— 时间和空间都最优。
这就是算法优化的艺术：在约束条件下，找到最佳的平衡点。
总结
- 空间复杂度衡量算法运行时额外占用的内存。
- O(1) 是最理想的，意味着原地处理。
- 递归会消耗栈空间，深度为 n 的递归空间复杂度至少是 O(n)。
- 时间和空间的权衡是算法设计的核心问题之一。
小明建议： 面试时，如果面试官问你算法复杂度，不要只回答时间复杂度，把空间复杂度也一起说了。这会让你显得更专业。
"时间就是金钱，空间也是金钱。" "所以写出一个时间空间双优的算法，就是在帮公司省钱。" —— 小明
最后，送你一个冷笑话： 一个算法工程师去面试。 面试官问："你的算法时间复杂度是多少？" 工程师："O(1)。" 面试官："空间复杂度呢？" 工程师："O(n²)……" 面试官："那你是开了个仓库来存东西啊。" 工程师："……我存的全是对甲方的怨念。"