算法空间复杂度详解与常见示例

什么是空间复杂度

• 是一个函数，用大 O 表示，比如 O(1)、O(n)、O(n^2)
• 算法在运行过程中临时占用存储空间大小的量度

这里有几个点需要说清楚，不然很容易算错。

第一，衡量的是「额外」占用的空间，不含输入数据本身。一个函数接收长度为 n 的数组，遍历一遍求和，空间复杂度是 O(1) 而不是 O(n)——那个数组是调用方传进来的，不是这个算法申请的。这一点在面试里经常被追问，也是最容易搞混的地方。

第二，跟时间复杂度一样只看增长趋势，常数因子和低阶项都要丢掉。声明一个变量是 O(1)，声明五十个变量还是 O(1)，因为不管输入多大，这个数量都不变。反过来说，判断一段代码的空间复杂度，核心问题只有一个：占用的空间会不会随输入规模一起长，以什么速度长。

第三，空间和时间经常可以互换，这是空间复杂度真正的实践价值所在。最典型的例子是用哈希表换查找速度：多花 O(n) 的空间存一份映射，把每次查找从 O(n) 的遍历降到 O(1)。「两数之和」用 Map 的解法就是这个套路。反方向也成立，内存受限的场景里宁可多算几遍也不缓存中间结果。这种取舍在实际项目里比追求某个单项最优更常见。

还有一点容易被忽略：递归的调用栈也算空间。每层递归都要在栈上保留自己的局部变量和返回地址，递归深度为 n 的函数，即使函数体里没申请任何数据结构，空间复杂度也是 O(n)。二叉树的递归遍历就是这样，它的空间复杂度取决于树的高度，平衡树是 O(log n)，退化成链表的话是 O(n)。这也是深递归会栈溢出的原因。

示例

下面按增长速度从低到高看三个典型情况，判断方法就是前面那句话：数一数占用的空间跟 n 是什么关系。

O(1)

下面这段代码只声明了单个变量

关键不在于「只有一个变量」，而在于这个数量是固定的，跟 n 没关系。就算再加二十行变量声明，只要不随输入增长，仍然是 O(1)。这类也叫常数空间。

let i = 0;
i += 1;

O(n)

数组 list 在循环中添加了 n 个值

这就是线性空间：n 变成两倍，占用的空间也跟着变成两倍。注意判断依据是数组最终存了多少元素，而不是循环跑了多少次。如果循环里做的是累加到一个变量上而不是 push 进数组，循环次数一样是 n，空间复杂度却是 O(1)。循环次数决定时间，实际存下来的数据量决定空间，这两件事要分开看。

日常代码里 map、filter 这类会返回新数组的方法，都是 O(n) 的额外空间。

const list = [];
for (var i = 0; i < n; i++) {
  list.push(i);
}

O(n^2)

数组 matrix 在循环后存储了两层数组（矩阵）

外层循环建了 n 个子数组，每个子数组里又放了 n 个元素，总共 n 乘 n 个格子，所以是平方级。

平方空间的增长有多快值得有个直观印象：n 是一千时是一百万个格子，还能接受；n 到一万就是一亿个，按每个元素八字节算，光数据就接近一个 G，基本跑不动了。所以见到二维数组，第一反应应该是估一下规模撑不撑得住。

动态规划是最容易写出平方空间的地方，两个字符串的编辑距离、最长公共子序列这类题，标准解法都是开一个二维表。而这类题往往能优化：如果状态转移只依赖上一行，就没必要留下整张表，用两个一维数组滚动使用即可，空间从 O(n^2) 降到 O(n)。这是很常见的一类优化，思路是「只保留还会被用到的状态」。

const matrix = [];
for (var i = 0; i < n; i++) {
  matrix.push([]);
  for (var j = 0; j < n; j++) {
    matrix[i].push([j]);
  }
}