形式陈述

对在所有输入上停机的确定性图灵机 $M$，令 $S_M(n)$ 为所有长度为 $n$ 的输入上，运行期间同时访问的工作带单元数最大值。若 $S_M(n)=O(s(n))$，称 $M$ 使用 $O(s(n))$ 空间，并定义

$$\mathrm{SPACE}(s(n))=\{L:\text{某确定性图灵机以 }O(s(n))\text{ 空间判定 }L\}.$$

通常输入带只读，不计入工作空间；输出和机器模型的常数差异需固定约定。

直觉

时间统计总步骤数，空间统计计算过程中同时需要保留多少工作记忆。存储单元可以反复覆盖，因此一个使用很少空间的算法仍可能运行很久。

例子与边界

深度优先遍历隐式状态图可能只保存当前路径而节省空间。若把长度为 $n$ 的只读输入本身计入空间，就无法讨论亚线性空间，因此复杂度定义通常排除输入带。不同合理多带模型只造成常数或低阶差异，但极小空间界需要更谨慎。

推论与应用

空间复杂度产生 $\mathrm{L}$、$\mathrm{NL}$、$\mathrm{PSPACE}$ 等复杂度类，并通过配置图把空间界与可达性、时间上界联系起来。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Chapter 4。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，§8.1。