空间复杂度（Big O）怎么分析：别再只会背 O(1)/O(n)

很多人做算法题时会说：

时间复杂度：$O(n)$
空间复杂度：$O(1)$

然后就没了。

问题是：空间复杂度经常不是 $O(1)$，甚至在工程里比时间更致命（内存爆了程序就挂）。

这篇文章给你一套“能推演”的空间复杂度分析方法。

1. 空间复杂度到底在算什么？

空间复杂度讨论的是：

随着输入规模 $n$ 增长，算法需要的额外空间（auxiliary space）增长趋势。

注意两个常见误区：

不一定算输入本身占用的空间（输入由外部提供）
通常分析的是额外空间，而不是程序的“总内存占用”

“额外空间”包括：

新创建的数组/对象/哈希表
递归调用栈
临时变量（通常是常数级）

2. 一套通用分析步骤

你可以按这个顺序做：

找出随 $n$ 变化而增长的结构：数组、Map、Set、对象、递归深度
判断它们的最大规模：是 $n$、$\log n$ 还是常数
把它们加总，取最高阶

空间复杂度常见结果：

$O(1)$：额外空间与输入无关（原地算法常见）
$O(\log n)$：通常来自递归栈（比如二分、平衡树）
$O(n)$：辅助数组/哈希表/队列堆积
$O(n^2)$：二维 DP 表等

3. 递归：空间复杂度经常藏在“栈”里

看一个经典例子：求阶乘。

function factorial(n) {
  if (n <= 1) return 1
  return n * factorial(n - 1)
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$（递归深度 $n$，每层调用占一个栈帧）

很多人会误判为 $O(1)$，因为“没 new 数组”。但栈也是空间。

如果改成迭代：

function factorial(n) {
  let result = 1
  for (let i = 2; i <= n; i++) result *= i
  return result
}

空间复杂度就变成 $O(1)$（只用常数个变量）。

4. 原地（in-place）不等于“零空间”

原地算法通常指：

不随 $n$ 申请额外线性空间
或额外空间是常数级

但注意：

原地排序（如快速排序）在递归实现时，栈空间可能是 $O(\log n)$
在最坏情况下（极端 pivot），递归深度可能退化到 $O(n)$

所以“快排空间复杂度 $O(1)$”这种说法往往不严谨。

5. 常见结构的空间代价直觉

5.1 哈希表/Map/Set

如果你用 Map 存储 $n$ 个元素：

空间复杂度通常是 $O(n)$

工程上还要考虑：

装载因子与扩容造成的峰值
key/value 的引用与对象开销

5.2 辅助数组

归并排序是典型：

时间 $O(n\log n)$
空间 $O(n)$（需要临时数组）

5.3 DP 表

二维 DP（如编辑距离）：

空间 $O(nm)$

很多 DP 可以做“滚动数组优化”，把空间从 $O(nm)$ 降到 $O(\min(n,m))$。

6. 面试里怎么说才算“到位”

建议用一个模板：

我分析的是额外空间（不计输入）。
主要额外空间来自 X（例如哈希表/辅助数组/递归栈）。
它的规模随 $n$ 增长为 Y，所以空间复杂度为 $O(Y)$。

举例：

“用了 Map 存储访问过的节点，最多存 $n$ 个，所以额外空间 $O(n)$。”
“递归深度 $\log n$，每层常数空间，所以额外空间 $O(\log n)$。”

7. 小练习：3 题快速自测

反转链表（迭代）

额外空间？

二叉树先序遍历（递归）

额外空间？（提示：与树高度有关）

两数之和（用哈希表）

额外空间？

答案提示：分别常见为 $O(1)$、$O(h)$、$O(n)$。

总结

空间复杂度关注“额外空间”的增长趋势。
递归栈是最常被忽略的空间来源。
原地算法也可能有 $O(\log n)$ 栈空间。
面试表达要说清楚“来源是什么、规模是多少”。

空间复杂度进阶：递归栈、原地算法与峰值内存