空间复杂度

空间复杂度用于衡量算法所需的内存，是输入规模的函数。它与时间复杂度一起，构成计算复杂性中的基本资源度量。时间衡量计算步骤的数量，空间则衡量执行过程中使用的存储量。具体计量哪些存储，取决于计算模型，以及是否将输入、输出和临时存储纳入计算。(ocw.mit.edu)

定义与渐近记号

对于算法 $A$，令 $s_A(x)$ 表示它在输入 $x$ 上的空间用量。其最坏情况空间复杂度为

其中，$|x|$ 表示输入规模。视具体问题而定，规模可以指输入元素的数量，也可以指其编码表示的长度。这个定义区分了某个特定输入所消耗的资源，与所有相同规模的输入中所需资源的最大值。(cs.uwaterloo.ca)

空间界通常用大O记号等渐近记号表示。$O(n)$ 表示，当输入规模足够大时，内存用量不超过 $n$ 的某个常数倍；$\Theta(n)$ 则表示其增长率的上界和下界一致。常见的空间增长阶包括常数、对数、线性和平方阶。渐近分析忽略常数因子，而具体的内存分析则计算值、引用和对象实际占用的存储空间。(algs4.cs.princeton.edu)

哪些存储计入空间

辅助空间是输入表示之外额外使用的工作存储空间。总空间分析则包括输入，以及所声明的计量约定涵盖的其他存储。因此，处理一个已有的、包含 $n$ 个元素的数组时，即使数组本身占用线性空间，算法也可能只使用常数辅助空间。输出的计量方式也需要明确：不计入写往外部的输出，与将结果保留在内存中的情况并不相同。(cs.cornell.edu)

算法的内存分析通常关注同一时刻所需存储空间的最大值，而不是整个执行过程中历次内存分配量的总和。已经释放并重新使用的内存无需重复计算。分析必须包括临时对象、保留的数据结构以及尚未结束的过程调用。传递已有数组的引用，本身不会复制该数组；构造新数组则会占用新的存储空间。(courses.cis.cornell.edu)

在用于研究较小空间界的图灵机模型中，输入通常放在只读带上，而空间用量只计算可写工作带上的单元。独立的只写输出带也可以不计入。这些约定使次线性的工作空间界具有意义，尽管输入本身仍需要实际的存储空间。(courses.cs.cornell.edu)

计算模型与计量单位

空间可以用比特、字节、带单元或机器字来计量。在字长随机存取机模型中，内存由可寻址的机器字组成，每个字包含 $w$ 比特。因此，一个使用 $k$ 个机器字的算法，仅这些字就占用 $kw$ 比特；若未明确 $w$，就不应将这两种单位视为可以互换。(ocw.mit.edu)

例如，一个可表示 $n$ 个位置的索引需要 $\Theta(\log n)$ 比特，尽管它可能只占一个机器字。因此，以机器字为单位分析时所说的“常数空间”，其比特数仍可能随输入规模增长。同样，任意大的整数也不能直接视为大小恒定的对象：其编码长度取决于数值的大小。(cs.cmu.edu)

具体的内存需求还取决于表示方式的选择，以及编程语言的实现。除所表示的值之外，引用、对象头和对齐填充也会占用存储空间。即使这些开销不改变渐近界，也可能对实际内存用量产生显著影响。(algs4.cs.princeton.edu)

递归与典型算法

递归通过调用栈消耗内存。如果每个尚未结束的调用都需要常数空间，且最大递归深度为 $d$，那么栈空间为 $O(d)$。相关的量不是调用总次数：依次执行的调用可以复用存储空间。将适合改写的递归代码转换为迭代，可以消除不断增长的调用栈；是否自动进行尾调用优化则取决于具体实现。(courses.cis.cornell.edu)

在图论中的图遍历问题中，常规的深度优先搜索会维护访问状态信息，以及显式或递归形式的遍历栈。对于有 $V$ 个顶点的图，不计图的表示所占空间，其辅助空间为 $O(V)$。搜索可能执行大量计算，却只保留当前的遍历状态，而不保存完整的执行历史。(cs.cornell.edu)

标准的基于数组的归并排序体现了另一种内存消耗来源。其分治法结构的递归深度为对数级，但合并缓冲区需要 $\Theta(n)$ 的额外空间。因此，总体辅助空间界是线性的，而不是对数级的。这个界描述的是该特定实现，并不适用于所有可能的合并或排序方法。(algs4.cs.princeton.edu)

时间与空间的权衡

当保留信息可以避免后续计算，或者重新计算信息可以减少需要保留的存储量时，就产生了时间与空间的权衡。记忆化常用于动态规划，它保存已经计算出的结果，使重复出现的子问题可以通过查表得到答案。这能显著减少重复的递归计算，但保存的结果也会增加内存用量。(cs.cornell.edu)

空间也可以在相继执行的阶段之间复用。在空间受限的模拟中，即使计算步骤数量非常庞大，依次进行的递归搜索仍可以共享工作存储空间。这种复用是时间界与空间界可能相差甚远的原因之一。(courses.cs.cornell.edu)

空间复杂度类

复杂度类 $\mathrm{DSPACE}(s(n))$ 包含可以在 $O(s(n))$ 工作空间内以确定性方式求解的判定问题；$\mathrm{NSPACE}(s(n))$ 则是对应的非确定性复杂度类。PSPACE 允许使用多项式空间，NPSPACE 则允许使用非确定性多项式空间。这里的“多项式”指的是内存界，运行时间不一定也是多项式级的。(ocw.mit.edu)

萨维奇定理指出，在满足标准假设、且空间界至少为对数级时，

其模拟方法以可能非常庞大的计算量，换取存储用量的受控增长。由于多项式的平方仍保持多项式增长，该定理推出 $\mathrm{PSPACE}=\mathrm{NPSPACE}$。(courses.cs.cornell.edu)