空间复杂度

时间复杂度公理库时间复杂度Time complexity · Running time在固定计算模型与输入编码后，算法运行步骤数随输入规模增长的量级。累计执行过多少步，空间复杂度统计一条运行中需要开辟多少工作格。同一格可以擦除后存放新内容，重写一千次仍只占一个格；因此时间可以远大于空间。所谓“同时保留的信息峰值”是这种复用的直观说法，正式计量则以曾访问的工作带区域为准。

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

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

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

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

计费边界 ​

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

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

空间计量导出DSPACE公理库确定性空间复杂性类Deterministic space class · DSPACE由确定性图灵机在给定工作空间界内判定的语言集合。和非确定空间类。配置由状态、头位置与工作带内容组成；空间界限制配置编码长度，进而限制可能配置总数。这条“空间 → 配置图 → 时间或可达性”的路径是 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可由确定性图灵机在多项式空间内判定的语言类。取所有多项式空间的并。空间可构造性不是单次空间计量的定义条件，但在空间层级等需要机器识别自身预算的定理中通常会显式加入。