空间复杂度

空间复杂度衡量的是随输入规模变化的峰值存活内存。在给出复杂度界限时，必须明确区分：这是指总内存占用，还是仅指除输入和必要输出之外的辅助空间（Auxiliary Space）。

内存构成

• 输入（Input）： 算法接收的数据表示。
• 输出（Output）： 最终生成的结果。有时输出本身巨大且不可避免，成为空间瓶颈。
• 辅助状态（Auxiliary State）： 算法运行中产生的临时结构，如哈希表、队列、访问标记集、缓冲区及临时对象。
• 调用栈（Call Stack）： 递归调用时，每个活跃调用对应一个栈帧。

峰值空间看的是某一时刻同时占用的最大内存，不是整个运行过程中分配过的内存总和。阶段 A 释放的内存不会与阶段 B 的内存同时存在；应比较各阶段的占用峰值，而不是把它们相加。

分析准则

• 统计同时存活对象： 注意切片、字符串拼接或列表拼接产生的副本，它们会额外占用内存。
• 递归空间： 把同一时刻所有活跃调用保留的内存相加。若每个栈帧都有相同的大小上界，才可简化为“栈帧大小乘最大递归深度”。整个运行过程的调用总次数不能直接用来计算峰值栈空间。
• 区分输出模式： 明确是流式输出（Streaming，低内存）还是全量物化（Materialized，高内存）。
• 计入数据结构表示： 图算法中，邻接矩阵占用 $\Theta(V^2)$，而邻接列表仅占用 $\Theta(V+E)$。

常见误区： 指数级时间复杂度 $\nRightarrow$ 指数级栈空间。例如深度优先搜索（DFS）可能遍历指数级的状态空间，但栈中仅需保留当前路径（线性深度）加上访问标记或记忆化缓存。

原地算法与空间压缩

• “原地（In-place）”的定义： 通常指数组重排仅使用 $O(1)$ 辅助存储。但需注意，递归栈或对象级分配可能破坏这一假设。描述算法时，应明确“原地”的具体约定。
• DP 空间优化： 若状态转移仅依赖有界的“前沿”（Frontier），可压缩 DP 表空间。但前提是：若后续需要回溯具体解（Witness），则不能丢弃重建路径所需的前驱信息。

时间与空间的权衡

• 以空间换时间： 记忆化（Memoization）、索引、哈希表、预计算表。通过增加内存开销避免重复计算。
• 以时间换空间： 重新计算（Recalculation）、流式处理、紧凑表示。节省内存，但可能增加时间开销或实现复杂度。

建议： 优化应基于实际约束（如内存限制、延迟要求），而非孤立地追求单一维度的渐近最优。

逐项计算内存

对 $n$ 条记录做原地插入排序，输入数组同时也是输出。下标和暂存的键只需 $O(1)$ 辅助字，但总存储仍为 $\Theta(n)$。若另行返回一个排序列表，仅输出就需要 $\Theta(n)$ 个槽位，还没算工作空间。共享对象只计算一次：复制 Python 列表复制的是引用，不一定复制引用指向的记录。

用下标边界实现的递归二分搜索有 $O(\log n)$ 个常数大小栈帧。若每次调用都切出半个列表，还会保留规模为 $n/2+n/4+\cdots<n$ 的副本，辅助空间就变成 $O(n)$。递归深度相同，不代表内存界限相同。一般应把存活栈帧的大小相加；只有每帧大小有相同界限时，才能直接用“帧大小乘深度”。

在显式图上做 DFS，访问集可能保存所有可达顶点。对深度 $d$、分支数 $b$ 的隐式搜索树，若不设全局访问集，每帧只保存常数大小的后继迭代器，就可能花指数时间却只用 $O(d)$ 个栈帧。若每层保存全部 $b$ 个后继，则需 $O(bd)$；若记忆化所有探索过的状态，内存也可能变成指数级。

这些界限统计的是记录大小有界时的机器字或引用数，不是精确字节数。整数位数、对象头、分配器开销和延迟回收都会影响进程实际内存。峰值存活对象分析不保证运行时立即把释放的内存归还操作系统。

参考

• Open Data Structures

我的阅读 · 打开过的笔记会记在当前浏览器里。