你的程序是个背包客：聊聊空间复杂度这回事 - 每日分享

你有没有在机场见过那种被拦下来的旅客？值机柜台前，工作人员指着他的登机箱说：“先生，这个必须托运，客舱放不下。”箱子本身不重，就是太大了。

程序运行时也会遇到同样的尴尬。内存就是那个有限的客舱，你的代码就是那个箱子。有时候算法跑着跑着突然卡死或者直接崩掉，不是逻辑写错了，而是它在运行过程中偷偷往箱子里塞了太多东西——临时变量、中间结果、递归调用记录——直到内存管理员过来说：不行，装不下了。

这就是空间复杂度要解决的问题。不是你的输入数据有多大，而是你为了处理这些数据，额外占了多少地方。

先搞清楚一件事：什么叫“额外”

很多人第一次接触空间复杂度，会下意识地把输入数据也算进去。比如看到一个长度为 n 的数组，就说“空间复杂度是 O(n)”。这个理解偏了。

空间复杂度衡量的是算法运行时临时开辟的额外空间。输入数据是题目已经给你的，它就在那里，不多不少。你要评估的是：为了完成计算，我又额外拿了多少内存？

打个比方。你帮老师整理全班 n 个同学的成绩单。成绩单本身是老师给你的，不算你的工作量。但如果你拿了一张新纸，把排序后的结果抄上去，这张新纸就是你的额外开销，大小和 n 有关，所以是 O(n)。如果你直接在原成绩单上用铅笔涂改，顶多手里攥块橡皮，额外空间就是常数级 O(1)。

这个区分很关键。不把输入数据排除在外，不同算法之间的空间效率就没法公平比较了——大家面对的都是同一份输入，比的是谁更省“私房钱”。

有一道判断题正好戳中这个点：“程序的空间复杂度只考虑算法运行时临时开辟的额外存储空间，不包括输入数据本身占用的空间。” 答案是对的。这道题看似简单，但它是理解空间复杂度的第一道门槛。跨不过去，后面的分析全是糊涂账。

另一道选择题问：空间复杂度为 O(1) 意味着什么？

选项里有一个很典型的错误答案：“程序运行时完全不占用内存。”这是把 O(1) 和“零内存”划等号了。但 O(1) 的真正含义是：额外空间是一个常数，不随输入规模 n 的增长而增长。

你的程序当然会占内存——代码本身要加载，几个变量要分配，函数调用要有栈帧。但这些开销是固定的，输入变成一千、一万、一百万，它还是那么多。这就是 O(1)。

看个例子：

def square_in_place(arr):
    for i in range(len(arr)):
        arr[i] = arr[i] * arr[i]
    return arr

这里只用了 i 这一个循环变量，没有创建新列表。不管 arr 有多长，额外空间就是那几个字节。这就是 O(1)。

对比一下：

def square_list(arr):
    result = []
    for x in arr:
        result.append(x * x)
    return result

result 的长度等于输入数组的长度。输入翻倍，额外空间也翻倍。这是 O(n)。

两种写法都能完成任务，但空间开销差了一个量级。在实际工程中，如果输入规模很大而内存有限，这个差距可能就是“能跑”和“跑不起来”的区别。

递归是个很优雅的工具，写起来简洁，读起来清晰。但它有个隐藏账单：调用栈。

每次递归调用，系统都要把当前函数的参数、局部变量、返回地址压入调用栈。递归深度为 n，栈就要占 n 层空间。这个开销是实打实的，只是它不像 new 一个数组那么显眼，容易被忽略。

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

这段代码看起来只用了 n 一个变量，但调用 factorial(1000) 的时候，栈里会同时存在 1000 个栈帧。空间复杂度是 O(n)，不是 O(1)。Python 默认递归深度限制是 1000 左右，超过就报 RecursionError——这其实就是空间不够用了。

所以写递归的时候，除了想清楚什么时候终止，还得想清楚：这个递归会压多少层栈？能不能改成迭代？很多时候，迭代版本不仅空间复杂度更低，时间复杂度也更优。斐波那契数列的递归和迭代对比就是经典案例——递归版本的空间和时间都是灾难级别的，迭代版本两个变量就搞定。

算法设计里有个永恒的话题：空间换时间，或者时间换空间。

哈希表是最典型的空间换时间。你多花 O(n) 的空间存一个字典，把查找操作从 O(n) 降到 O(1)。在内存充足的情况下，这笔买卖通常划算。

反过来，原地排序（比如堆排序）是时间换空间的例子。它不额外开辟大数组，直接在原数组上交换元素，空间复杂度 O(1)，但实现起来比归并排序复杂，常数因子也可能更大。

选哪种策略，取决于你的运行环境。在服务器上跑，内存几个 G 随便用，那就怎么快怎么来。但在嵌入式设备或者手机上，内存是稀缺资源，你就得精打细算。没有绝对的最优解，只有适合当前场景的权衡。

在循环里拼接字符串。 Python 的字符串是不可变的，每次 result = result + ch 都会创建一个新字符串对象，旧的被丢弃。虽然最终只有一个 result 变量，但过程中产生的临时对象空间是 O(n²) 级别的。正确做法是用列表收集，最后 join。

以为只有显式声明容器才占空间。 生成器表达式、推导式、函数返回的临时元组，这些都在消耗内存，只是不那么显眼。

混淆时间复杂度和空间复杂度。 看到一个 O(n²) 的算法就以为它一定慢，其实它可能只是空间开销大，时间上未必差。两个维度要分开评估。

空间复杂度这个指标，平时写业务代码可能感受不深——毕竟现在的机器内存都很大。但一旦涉及大规模数据处理、嵌入式开发、或者算法竞赛，它就是决定成败的关键因素之一。

养成一个习惯：写完一个算法，除了想“它跑得够快吗”，再多问一句“它额外占了多少内存”。特别是用了递归、创建了新容器、或者在循环里做了对象创建的时候，多留个心眼。

进阶学习的方向，我建议从这几个点切入：深入理解调用栈的工作机制，搞清楚递归的空间开销到底怎么算；学习常见的空间优化技巧，比如原地算法、滚动数组、状态压缩；再看看记忆化搜索和动态规划里空间复杂度的分析方法，那里面的技巧更丰富。

把空间复杂度当成你算法工具箱里的一个常规检查项，而不是考试前才想起来背的概念。这样你写出来的代码，才真正经得起规模增长的考验。

关于作者

我是赵老师，持有 NOI 信息学奥赛教练证书，拥有 15 年以上的软件开发经验，从事信息学少儿编程教学已有 8 年时间。

这些年累计帮助多名学生通过编程特长升入自己心仪的目标学校。

如果你在编程学习上有任何疑问，欢迎联系我：18620372957（微信同号）