空间复杂度

时间复杂度公理库时间复杂度Time complexity · Running time在固定计算模型与输入编码后，算法运行步骤数随输入规模增长的量级。累计执行过多少步，空间复杂度统计一条运行中需要开辟多少工作格。同一格可以擦除后存放新内容，重写一千次仍只占一个格；因此时间可以远大于空间。所谓“同时保留的信息峰值”是复用的直观说法，正式计量则以曾访问的工作带区域为准。一个程序若只写一位、擦掉后向右移动，再反复这样做，当前非空格始终只有一个，但访问区域不断增长；它仍消耗增长的空间。要得到小空间算法，必须真正回用已开辟的区域，而非仅把不用的数据擦成空白。

只读输入与只写输出把“给定的数据”“中间工作区”“产生的结果”分开。若把输入本身算进工作空间，所有长度为 $n$ 的实例都会先付 $\mathrm{\Omega }(n)$，对数空间和其他亚线性现象就被模型约定掩盖。

三位计数器展示空间复用 ​

工作带上的三个位可以依次经历

这段运行执行多次进位，却始终只访问三个工作格。一般地，$s$ 位计数器可经历 $2^s$ 个不同内容，说明 $O(s)$ 空间的计算完全可能运行指数于 $s$ 的步数。反过来，运行 $t$ 步的标准机器至多在每条带上新访问 $t+1$ 个格，因此时间上界会给出同阶的粗略空间上界。

计费边界 ​

递归调用栈、显式队列、哈希表元数据和保存的指针都属于工作空间，不能只统计主要数组。复杂度理论中的格子数也不同于进程 RSS；运行库、内存分配器、代码页和缓存属于另一套工程测量模型。

Savitch 定理公理库Savitch 定理Savitch's theorem通过配置可达性的中点递归与工作区复用，把非确定空间 s 确定化为平方空间。的八顶点例子把这一原则落实为四帧账本：逐帧记录端点、中点、阶段和返回位，左子调用结束后让右子调用复用原来的子调用工作区。删除一条边会增加需要探索的失败候选，却不增加最大递归深度。练习时应另列只读矩阵与输入扫描索引，不能把教学帧的载荷位数当作整机精确空间。

当 $s(n)<\log n$ 时，机器能否保存输入位置都成为实质问题。单带还是多带、输入头位置是否可由有限控制获得、纸带是否随机访问，会改变这一区域的表达能力。因此空间层级和 Savitch 一类标准结论通常在 $s(n)\ge \log n$ 且模型固定后陈述。

空间计量导出DSPACE公理库确定性空间复杂性类Deterministic space class · DSPACE由确定性图灵机在给定工作空间界内判定的语言集合。和非确定空间类。配置由有限状态、所有头位置与工作带内容组成。若工作空间为 $s(n)\ge \log n$，固定工作字母表的内容选择数为 $2^{O(s(n))}$，输入头的 $n+2$ 个位置、工作头位置和有限控制的额外因子也可吸收进去，因此完整配置至多 $2^{O(s(n))}$ 个。确定性判定机不能重访同一配置，否则以后无限循环；非确定机器虽能有环，但一条通向接受的路径总可删除回路。这分别把停机时间和接受路径长度连接到空间预算，不能把所有非确定分支的数量当作配置数量。这条“空间 → 配置图 → 时间或可达性”的路径是 L、NL、PSPACE 与 Savitch 定理共同的技术基础。

工程模型还需说明计量单位：$n$ 个机器字占 $\mathrm{\Theta }(nw)$ 位。简洁数据结构公理库简洁数据结构Succinct data structure以接近对象族信息论下界的 bit 数保存对象，同时直接支持查询。比较信息论最少位数与冗余，线性 Sketch公理库线性 SketchLinear sketch以线性映射 Sf 压缩频率向量，使更新与分布式摘要可直接相加。还报告失败概率，外存模型公理库外存 / I/O 模型External-memory model · I/O model · Aggarwal–Vitter model只计大小为 B 的数据块在容量为 M 的内存与外存之间传输次数的两层存储模型。则区分内存容量、磁盘空间和块传输。

只写“$O(n)$ 空间”而不说明 bit、word、输入与索引，无法判断实际节省了哪一类资源。

L公理库复杂度类 LComplexity class L · Deterministic logspace可在确定性对数空间内判定的语言类。把预算固定为 $O(\log n)$，PSPACE公理库复杂度类 PSPACEComplexity class PSPACE可由确定性图灵机在多项式空间内判定的语言类。取所有多项式空间的并。空间可构造性不是单次空间计量的定义条件，但在空间层级等需要机器识别自身预算的定理中通常会显式加入。