hello-algo 空间复杂度精讲：用“暂存空间 + 输出空间”口径量化算法内存开销

hello-algo 空间复杂度精讲：用“暂存空间 + 输出空间”口径量化算法内存开销

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本文以《Hello 算法》（hello-algo）计算复杂度章节中的空间复杂度主题为主线，系统讲解空间复杂度的统计口径、推算规则与五种常见阶数（常数、对数、线性、平方、指数），并结合仓库中codes/python/chapter_computational_complexity/space_complexity.py的六个可运行函数与codes/pythontutor/chapter_computational_complexity/space_complexity.md的分步动画注释，给出从原理到实测的完整分析路径。读完后，你将能够独立判断一段 Python 代码在循环、递归、动态分配等场景下各自占用的内存阶数，并能在真实工程中做出“以空间换时间”或“以时间换空间”的权衡决策。

什么是空间复杂度，以及“统计什么”

空间复杂度（space complexity）用于衡量算法占用内存空间随着数据量变大时的增长趋势。这个概念与时间复杂度非常类似，只需将“运行时间”替换为“占用内存空间”。

算法在运行过程中使用的内存空间主要包括三种（对应完整多语言版讲解见 docs/chapter_computational_complexity/space_complexity.md）：

• 输入空间：用于存储算法的输入数据。
• 暂存空间：用于存储算法在运行过程中的变量、对象、函数上下文等数据。
• 输出空间：用于存储算法的输出数据。

一般情况下，空间复杂度的统计范围是**“暂存空间”加上“输出空间”**（输入空间往往由调用方决定，通常不计入）。暂存空间可进一步细分为三部分：

• 暂存数据：保存算法运行过程中的各种常量、变量、对象等；
• 栈帧空间：保存调用函数的上下文数据。系统每次调用函数都会在栈顶部创建一个栈帧，函数返回后栈帧空间会被释放；
• 指令空间：保存编译后的程序指令，实际统计中通常忽略不计。

因此，分析一段程序的空间复杂度时，通常统计暂存数据、栈帧空间和输出数据三部分。仓库中的 Python 版本示例（与 docs/chapter_computational_complexity/space_complexity.md 中 Python 代码块一致的概念示意）：

class Node: """类""" def __init__(self, x: int): self.val: int = x # 节点值 self.next: Node | None = None # 指向下一节点的引用 def function() -> int: """函数""" # 执行某些操作... return 0 def algorithm(n) -> int: # 输入数据 A = 0 # 暂存数据（常量，一般用大写字母表示） b = 0 # 暂存数据（变量） node = Node(0) # 暂存数据（对象） c = function() # 栈帧空间（调用函数） return A + b + c # 输出数据

仓库中的 Python 实现与运行方式

本章的可运行代码位于 codes/python/chapter_computational_complexity/space_complexity.py，文件头部通过修改sys.path引入仓库自带的模块包，再从中取用节点类与打印工具：

import sys from pathlib import Path sys.path.append(str(Path(__file__).parent.parent)) from modules import ListNode, TreeNode, print_tree

从源码结构看，modules包的入口 codes/python/modules/__init__.py 统一再导出ListNode、TreeNode、print_tree等符号；其定义分别位于 codes/python/modules/list_node.py（val+next两个字段）与 codes/python/modules/tree_node.py（val、height、left、right字段）。

运行环境方面需要注意版本前提：源文件使用了dict[int, str]（PEP 585 泛型）和TreeNode | None（PEP 604 联合类型）这类新式类型标注，因此至少需要 Python 3.10。仓库的 codes/Dockerfile 中 Python 环境正是以apt-get install -y python3.10安装的，与此吻合。运行方式很简单，在项目根目录下执行：

python3 codes/python/chapter_computational_complexity/space_complexity.py

文件的 Driver Code（L78-L90）以n = 5为输入依次调用六个阶数示例函数：constant(n)、linear(n)、linear_recur(n)、quadratic(n)、quadratic_recur(n)、build_tree(n)，最后用print_tree打印建出的满二叉树。由于n很小，直接运行观察输出即可；要观察“内存如何随 n 增长”，则应借助下一节的 pythontutor 分步动画。

pythontutor 动画注释：逐指令观察内存生命周期

codes/pythontutor目录是为在线 Python 教学演示器准备的一批注释文件，codes/pythontutor/chapter_computational_complexity/space_complexity.md 中按函数顺序存放了 6 个 HTML 注释块，标记格式为：

<!-- [file]{space_complexity}-[class]{}-[func]{constant} -->

注释后紧跟一条经 URL 编码的演示器 render 链接，其中内嵌了完整的 Python 源码；文档站构建时会把该标记替换为可逐步执行的交互动画，从而在可视化面板中观察每一行代码执行时的堆/栈状态。

值得注意的实现细节：由于演示器沙箱无法导入仓库的modules包，内嵌代码是自包含的——constant演示在文件顶部内联定义了一个ListNode类（字段为val与next），build_tree演示同样内联定义了TreeNode（val、left、right）。此外演示版对数组规模做了收缩以便动画可读，例如constant中写的是nums = [0] * 10，而仓库源码 L24 中为nums = [0] * 10000——两者对空间阶数的结论完全一致，因为固定长度数组都是 O(1)。六个演示对应的函数与源文件中的实现一一对应：

推算方法：只关注最差空间复杂度，且以峰值内存为准

空间复杂度的推算方法与时间复杂度大致相同，只需将统计对象从“操作数量”转为“使用空间大小”。而与时间复杂度不同的是，通常只关注最差空间复杂度。原因是内存空间是一项硬性要求，必须确保在所有输入数据下都有足够的内存空间预留。

“最差”有两层含义（对应 docs 主文档中的示例）：

def algorithm(n: int): a = 0 # O(1) b = [0] * 10000 # O(1) if n > 10: nums = [0] * n # O(n)

1. 以最差输入数据为准：当n < 10时，空间复杂度为 O(1)；但当n > 10时，初始化的数组nums占用 O(n) 空间，因此最差空间复杂度为 O(n)；
2. 以算法运行中的峰值内存为准：程序执行最后一行之前只占 O(1) 空间，但初始化数组nums时峰值为 O(n)，因此最差空间复杂度仍按 O(n) 计。

在递归函数中，需要特别注意统计栈帧空间。docs 主文档给出了一组经典对照（Python 版）：

def function() -> int: # 执行某些操作 return 0 def loop(n: int): """循环的空间复杂度为 O(1)""" for _ in range(n): function() def recur(n: int): """递归的空间复杂度为 O(n)""" if n == 1: return return recur(n - 1)

loop()与recur()的时间复杂度都是 O(n)，但空间复杂度不同：

• loop()在循环中调用了 n 次function()，每轮调用都立即返回并释放栈帧，因此空间复杂度仍为 O(1)。这正对应constant()函数中“循环中的函数占用 O(1) 空间”那段代码（L29-L31）；
• recur()运行过程中会同时存在 n 个尚未返回的recur()调用，层层压栈，占用 O(n) 栈帧空间。

五种常见空间复杂度阶数与代码证据

设输入数据大小为 n，常见空间复杂度类型从低到高为：

O(1) < O(log n) < O(n) < O(n²) < O(2ⁿ)

即：常数阶 < 对数阶 < 线性阶 < 平方阶 < 指数阶。

常数阶 O(1)

常数阶常见于数量与输入数据大小 n 无关的常量、变量、对象。仓库实现（L20-L31）：

def constant(n: int): """常数阶""" # 常量、变量、对象占用 O(1) 空间 a = 0 nums = [0] * 10000 node = ListNode(0) # 循环中的变量占用 O(1) 空间 for _ in range(n): c = 0 # 循环中的函数占用 O(1) 空间 for _ in range(n): function()

易错点：nums = [0] * 10000虽然元素很多，但长度与 n 无关，仍是 O(1)；两个for循环中的变量c与function()调用，每轮结束就释放，不会累积，整体仍是 O(1)。

线性阶 O(n)

线性阶常见于元素数量与 n 成正比的数组、链表、栈、队列等（L34-L41）：

def linear(n: int): """线性阶""" # 长度为 n 的列表占用 O(n) 空间 nums = [0] * n # 长度为 n 的哈希表占用 O(n) 空间 hmap = dict[int, str]() for i in range(n): hmap[i] = str(i)

递归产生的线性阶同样由“栈帧深度”决定（L44-L49）：

def linear_recur(n: int): """线性阶（递归实现）""" print("递归 n =", n) if n == 1: return linear_recur(n - 1)

该函数递归深度为 n，即同时存在 n 个未返回的linear_recur()调用，使用 O(n) 大小的栈帧空间——这一点可以在 pythontutor 动画中逐指令看到调用栈随n递减逐层加深、再逐层弹出的过程。

平方阶 O(n²)

平方阶常见于矩阵和图，元素数量与 n 成平方关系（L52-L55）：

def quadratic(n: int): """平方阶""" # 二维列表占用 O(n^2) 空间 num_matrix = [[0] * n for _ in range(n)]

递归版本更能体现“空间随递归层层叠加”的机制（L58-L64）：

def quadratic_recur(n: int) -> int: """平方阶（递归实现）""" if n <= 0: return 0 # 数组 nums 长度为 n, n-1, ..., 2, 1 nums = [0] * n return quadratic_recur(n - 1)

递归深度为 n，每层各自持有一个未释放的数组，长度分别为 n、n−1、…、2、1，总元素个数为等差数列求和 n(n+1)/2，故总体占用 O(n²) 空间。注意各层的nums因栈帧未返回而无法被回收，这是它与“循环中分配定长数组（O(1)）”的本质区别。

指数阶 O(2ⁿ)

指数阶常见于二叉树（L67-L74）：

def build_tree(n: int) -> TreeNode | None: """指数阶（建立满二叉树）""" if n == 0: return None root = TreeNode(0) root.left = build_tree(n - 1) root.right = build_tree(n - 1) return root

层数为 n 的满二叉树节点总数为 2ⁿ − 1（每层节点数是上一层的 2 倍），因此占用 O(2ⁿ) 空间。这里的空间增长来自堆上持续存在的节点对象：TreeNode实例在树构建完成后仍全部存活，直到返回给调用方。Driver Code 中的print_tree(root)会将其打印出来，n=5 时即 2⁵−1 = 31 个节点。

对数阶 O(log n)

docs 主文档指出，对数阶常见于分治算法。例如归并排序，输入长度为 n 的数组，每轮递归将数组从中点划分为两半，形成高度为 log n 的递归树，使用 O(log n) 栈帧空间。再例如将数字转化为字符串：输入正整数 n，它的位数为 ⌊log₁₀ n⌋ + 1，对应字符串长度同为 ⌊log₁₀ n⌋ + 1，因此空间复杂度为 O(log₁₀ n + 1) = O(log n)。

权衡时间与空间：以空间换时间还是以时间换空间

理想情况下，我们希望算法的时间复杂度和空间复杂度都最优；但实际情况中，同时优化两者通常非常困难。降低时间复杂度通常以提升空间复杂度为代价，反之亦然。牺牲内存空间来提升运行速度的思路称为“以空间换时间”，反之称为“以时间换空间”。

本章的示例本身就是一个小对照：linear()中维护一个 n 项哈希表，用 O(n) 额外空间换取后续按 key 的 O(1) 查找，是典型的“以空间换时间”；而linear_recur()不额外开辟数据容器，却因递归调用链付出了 O(n) 栈帧空间——它提醒我们，即使代码里没有显式数据结构，递归深度本身也会消耗内存。

选择哪种思路取决于更看重哪个方面。大多数情况下时间比空间更宝贵，“以空间换时间”是更常用的策略；但在数据量很大、内存受限时，控制空间复杂度同样关键（例如用遍历代替递归、用滚动数组代替完整二维 DP 表）。

小结

• 空间复杂度的统计口径 = 暂存数据 + 栈帧空间 + 输出数据；输入空间与指令空间通常不计。
• 只算最差情况与峰值内存：if n > 10: nums = [0] * n的最差空间复杂度为 O(n)。
• 循环调用的空间不累积（O(1)），递归调用的栈帧会累积（O(深度)），这是 loop/recur 对照示例 的核心结论。
• 五种常见阶数各有标志性来源：定长容器 → O(1)，正比容器 → O(n)，矩阵 → O(n²)，满二叉树 → O(2ⁿ)，分治递归树 → O(log n)。
• 仓库内可直接运行 codes/python/chapter_computational_complexity/space_complexity.py 验证行为，并通过 codes/pythontutor/chapter_computational_complexity/space_complexity.md 的 6 段动画标记逐指令观察内存生命周期。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo