1. 为什么空间复杂性值得单独讲一章很多人在学复杂性理论的时候都有类似的疑问都已经有了时间复杂性那一整套框架P、NP、NP完全性也见识过了为什么教材非得用一整章来讲空间复杂性说实话我第一次翻到这一章的时候也这么想。但真正把空间复杂性学完之后我才意识到它远不是“时间复杂度换了个度量”那么简单它切入问题的角度、使用的证明手段、最后得到的结论都跟时间复杂性完全不同。先说一个最直观的区别时间过去了就是过去了没法复用时间一定是累积的但空间是可复用的某个内存槽位用完、释放掉后面还能继续用。这就导致空间复杂度的分析天然带有“峰值”的意味——它关心的不是整个计算过程中一共接触了多少存储单元而是在任意一个瞬间最多同时用了多少存储单元。这么一解释你就能很快理解为什么空间复杂度有时候体现的是计算的某种“结构宽度”。比如一个递归算法从时间上看就是把一个个子问题串行地解决但空间上看递归栈最深的那一时刻栈里同时存了所有等待返回的上下文这个深度就是空间复杂度的重要来源。换句话说时间刻画的是“做了多少事”空间刻画的是“同时摊开了多少东西”。这一章的内容在整个复杂性理论里属于承上启下的位置。承上它复用图灵机、可构造性、归约这些工具套路和时间复杂性章节高度类似启下空间复杂性直接通向更多现代课题比如对数空间内的图论判定问题、NL完全性、一点逻辑刻画内容甚至跟描述复杂性和数据库查询复杂度都有关联。如果你现在正在学或者准备复习这一章这篇文章的定位就是一份“陪读笔记”。我会把这一章的核心定义、几个关键定理、容易踩坑的理解误区以及我实际阅读和做题的过程中积累的经验都梳理一遍。学完之后你再回去看那些概念应该会有一种“原来它是为了回答这个问题才被定义出来的”的通透感。1.1 时间和空间两种复杂度本质上的差异可以打一个比方。假设你在做一道复杂的料理时间是你总共在厨房里站了多少分钟空间是你操作台面上同时铺开的锅碗瓢盆的数量。有的菜做起来很费时但操作台面一直很整洁只需要一个锅一个铲这是典型的“时间大、空间小”有的菜看着步骤不多但要同时准备七八种配料、三四个锅一起开工这是“空间大、时间未必大”。图灵机的计算也是这样。一台图灵机如果空间用得少意味着它在任何时刻只“摊开”了很少的工作带内容甚至可能反复回到同一个地方改写同一个单元格。空间的省用往往要靠重复读取、重新计算来换。这一点在线性空间的算法中特别常见。从理论后果上看时间复杂度的不可逆性制造了一个非常硬的事实如果一个算法时间的上界是某个函数那它所用的空间至多也不会超过同级别的更多资源。这句话听起来像废话但它给了我们一个基本的包含关系链。你很快就会在书里看到“P是PSPACE的子集NP也是PSPACE的子集”这类结论逻辑靠的正是“时间有限时空间一定有限”这条朴素的原则。1.2 空间复杂度的研究对象从“步数”转向“配置”要讨论空间先要讨论一种叫“配置”的对象。一个配置就是图灵机在某个时刻的全部快照当前状态、读写头位置、各条工作带上此刻的内容。你可以把它理解成拍了一张照片记录了机器在该时刻的所有信息。时间复杂度的计算可以用“步数”来衡量而空间复杂度天然跟“配置”挂钩。一台机器在一个输入上运行若它总共就只能访问固定数量的存储单元那么它的所有可能配置数量也是受限的。这个“配置数量”像是整个状态空间的地图规模空间越小地图越小机器的行为就越受限这也是很多空间类内判定问题的核心抓手。所以做空间复杂度分析时我习惯先画一张配置图把所有可能配置当作节点一步计算能转换的配置之间连边。这张图平方级的规模就是空间问题的“全景图”。不管是Savitch定理的证明还是后面要说的NL完全性问题本质上都是围绕这张配置图在转。先建立起这个画面后面所有内容都好理解了。2. 度量空间复杂度的框架从模型选择开始2.1 多带图灵机的空间计数规则图灵机模型的选择直接影响到空间复杂度的定义。最常用的约定是多带图灵机一条只读输入带一条只写输出带外加若干条工作带。输入带和输出带不计入空间复杂度工作带上使用过的最大单元数才是空间开销。为什么这么约定因为输入带只是存放原始数据不算算法本身的临时存储输出带也是如此。真正的“工作内存”是那些可读可写的工作带。具体数空间的时候统计的是“读写头扫过的单元的最大编号”而不是累计访问过多少个不同单元格。也就是说某一时刻工作带头停在最右边的那个位置就是从起点到这个位置的长度。这个定义下的空间度量是峰值度量跟实际理解很吻合。一张工作带上你有1000格就算只把其中两格来回擦写一万次空间复杂度还是1000格而不是10000访次。值得注意的一个细节是一个二进制计数器如果它能数到 n那么它至少需要 log n 个比特位。这个直觉在研究对数空间复杂度类时非常重要。很多人初学的时候会犯一个错误觉得维护一个数组下标 i也就是“把 i 记下来”只花了 O(1) 空间。这当然是错的——i 的取值范围是 0 到 n需要 log n 位才能表示。这个点会在后文的实操提示里反复出现。2.2 空间可构造函数与空间压缩定理在定义空间复杂度类之前需要先引入“空间可构造函数”这个概念。一个函数 S(n) 被称为空间可构造的如果存在一台图灵机在输入长度为 n 的任意串时恰好使用 S(n) 个存储单元然后在停止时输出一个长度为 S(n) 的特定标记。log n、n、n^2、2^n 这类常规函数都满足这个性质。为什么要单独定义它因为后面要用的空间层级定理、Savitch定理的陈述里都需要对两个空间界限函数进行某种“比较”。如果一个函数本身无法在空间受限的情况下被计算出来那就很难对它的分配做出精确判断甚至无法构造一台以它为界限的机器。简单说空间可构造函数是那些“我们的机器能数得清自己用了多少空间”的函数。它们构成了一个“自我监控”的基础使得对角线法能够顺利在其中施展。空间压缩定理说如果一台机器能在 S(n) 空间内解决问题那它也能在 S(n)/2 空间内解决同一个问题。原理是扩大工作带字母表把多个单元格的内容压缩编码到一个单元格里。这直接说明一个问题空间复杂度里的常数因子并不本质。所以看到 SPACE里有个10倍的常数不用紧张压缩一下就没有了。对比一下时间复杂性那边时间也有类似的时间压缩定理但时间压缩里并不允许直接把多个步骤“并行压”到一步压缩的幅度有限。而空间压缩的做法非常“物理”换一个字母表把信息密度提高即可。这算是空间复杂性中第一批违反直觉的结论之一。3. 复杂度类全景L、NL、PSPACE 与 NPSPACE3.1 对数空间类 L 和 NL为什么“对数”这么重要对数空间类 L SPACE(log n)NL NSPACE(log n)。先看“对数”这个量级的意义。要在一台多带图灵机上处理长度 n 的输入至少需要能够指出“我现在读输入带的哪一个位置”。一个 n 以内的位置编号需要 log n 位。所以 log n 空间连“只存一个指针”都只是勉强够用更不用说存下完整输入。这就是对数空间的优雅之处它逼着算法把所有额外信息都压缩到一个非常小的窗口里。L 类里的典型问题是“判断一个节点在链表中是否可达”顺着指针跨步走每一步只需要记录当前节点位置。这个题目在 O(1) 空间看似能做但如果节点编号是 n 以内的数计数器本身就占 log n 空间所以严格说它属于 L。NL 则是非确定性机器在对数空间内的版本。如果你没接触过非确定性可以粗略把它理解成“允许并行猜测一条路径”的机器模型。NL 的经典完全问题是“在无向或有向图中判断从 s 到 t 是否存在一条路径”这个问题的有向版本叫 STCONN 或有向可达性。它在非确定性的视角下非常自然每步猜一个节点确认节点之间有边一步步走到 t。NL 是否为 L 子集的问题至今未解。这类似于 P 与 NP 的关系只不过是在对数空间的框架里。但你可能会问为什么同样是对数空间限制非确定性看起来就强这么多这就要引入配置图了。一台在 O(log n) 空间内运行的机器配置总数只有多项式多个因为 log n 空间只能提供多项式种不同的工作带内容、状态和头位置的组合。非确定性搜索相当于在配置图上做路径搜索本质上是把“存在性”的判断直接交给非确定性去遍历。问题是能不能用确定性的算法避免这个遍历这就是 L vs NL 的实质。3.2 多项式空间类 PSPACE 与 NPSPACEPSPACE 是所有多项式空间可判定语言的集合NPSPACE 是非确定性版本。PSPACE 的定义看似“大”事实上确实大它包含 P 和 NP而且从目前已知结论来看PSPACE 远比 P 和 NP 更宽阔。为什么包含 NP任何一台多项式时间的非确定性机器在做计算时它能访问的存储单元也不会超过多项式个——毕竟每一步最多也只能多“打开”一个新单元。所以 NP 的计算开销放到空间的尺度上看也就是多项式空间。类似地P 也在 PSPACE 里。这件事反映了一个格局时间资源比空间资源更“贵”或者成本更高。在复杂性理论里人类对时间更敏感但对空间相对宽容。PSPACE 到底是不是等于 P这也不知道。但有一点可以肯定如果 PSPACE P那就直接推出 NP P因为 NP 是 PSPACE 子集。所以 PSPACE 与 P 的相等比 P 与 NP 的相等更强地超出了当前数学工具的射程。好在 PSPACE 这个类的结构还算清晰因为它有完全问题后面会讲到。NPSPACE 这个类在书里出现通常只有一个目的让你见识一下“在空间维度上非确定性和确定性的差距并没有时间维度上那么大”。这个结论来自 Savitch 定理。这也是整个空间复杂性章节里最令人印象深刻的定理之一。3.3 配置图视角下的空间类不妨再把配置图拿过来用一下。一台使用 O(s(n)) 空间且能在自己空间界限内停机不循环的机器它的配置数量是 2^{O(s(n))}。如果 s(n) log n配置数是多项式个如果 s(n) n^k配置数就是指数个。判定“是否存在一条路径从初始配置到接受配置”本质上就是有向图可达性问题。这个问题在一般图上很难难到什么级别呢它本身是一个 NL 完全问题。但注意这里难易的参照系是配置图中的顶点数。空间类的证明技巧不管是 Savitch 还是后面会讲的 QSAT 构造都离不开把“语言成员资格”翻译成“某个配置图上的路径存在性”这个基本动作。可以说配置图是空间复杂性的“第一性原理”。理解了一个问题的配置图规模你就理解了这个问题到底需要多大空间、可能的算法长什么样。我学习这一章时把大部分精力花在了画各种配置图上事实证明这是性价比最高的投入方式。4. Savitch定理用“重新计算”换掉“并行猜测”4.1 从非确定性到确定性空间上的神奇换算Savitch定理陈述如下对任意空间可构造函数 s(n) ≥ log n有 NSPACE(s(n)) ⊆ SPACE(s(n)^2)。翻译成人话任何非确定性机器在 s(n) 空间能解决的问题一定存在一台确定性机器在 s(n)^2 空间内也能解决。这个结论让人舒服的地方在于空间复杂度只平了一次方没有指数爆炸。对比时间维度非确定性时间类 NEXP 是否等于 EXP 至今是个大问题而空间维度却轻松做到了“平方化”。其中直觉上的原因是非确定性猜测可以理解为对配置图中路径的“存在性”查询而这种存在性查询可以利用分治递归来模拟不需要真的把每条路径都走一遍。s(n) ≥ log n 这个条件的含义是空间至少要足够存放一个指向配置图的“指针”——你需要能描述配置本身。如果空间太小连配置都表示不了后面所有的递归结构都无从谈起。这个条件属于技术性要求平时只要记住讨论空间复杂度时低于 log n 的情况都很特殊不在主要结论的适用范围里。4.2 核心递归技巧把“存在一条路”拆成两段Savitch定理证明的核心是定义一个递归过程“从配置 C1 能否在 t 步内到达配置 C2”。过程名叫 REACH(C1, C2, t)。它的逻辑非常简单粗暴如果存在某个中间配置 C_mid使得 REACH(C1, C_mid, t/2) 为真并且 REACH(C_mid, C2, t/2) 也为真那么答案就是真。判断一个“存在性”问题时非确定性可以直接猜 C_mid而确定性过程只能枚举所有可能的 C_mid逐个递归验证。这个过程消耗多少空间递归深度是 log t。每一步递归需要在返回后继续完成另一半验证所以要存下当前的 C_mid这需要 O(s(n)) 空间表示一个配置递归层数 log t 则额外乘一个 log t 因子。如果原始计算的最大步数是 2^{O(s(n))}配置空间大小那么 t 是 2^{O(s(n))} 级别log t 就是 O(s(n))。于是总空间是 O(s(n) * s(n)) O(s(n)^2)。细节上再加一点常数Savitch定理就成立了。我当年第一次看这个证明时最困惑的点在于为什么要反复调用 REACH 而不是一路记下去想通之后发现这正是空间复杂性和时间复杂性处理方式的本质分水岭——用时间上的重复计算去换空间上的节省。REACH 内部被反复调用相当于同一段路线被多次重走但在任何时刻保存的中间配置数量只是递归深度那么多。这不是“聪明”两个字能概括的它算是复杂性问题里“空间换时间”体系的起点。4.3 推论PSPACE NPSPACESavitch定理应用到多项式空间上立刻得到 NPSPACE PSPACE。因为任意 NPSPACE 机器使用空间 n^kSavitch 给出确定性机器使用空间 (n^k)^2 n^{2k}仍是多项式空间。这个结果的“意外”程度不亚于任何一条经典的复杂性结论。你想想时间维度上大家连“非确定性能否带来指数级突破”都搞不清楚空间维度直接给了一个干脆的答案不能。非确定性空间最多把复杂度平方一下而多项式函数的平方还是多项式。所以从 PSPACE 这个“高度”看非确定性和确定性几乎是一样的真正的分水岭不在“确定不确定”而在“空间到底允许多少”。这一点对理解复杂性全貌非常重要。不少人初学的时候会把“PSPACE NPSPACE”误解成“非确定性和确定性在空间上等价”进而觉得 L 应该也等于 NL。这是不对的。Savitch定理给的是平方关系不是 O(1) 关系。log n 的平方是 log^2 n仍然是亚线性的——这没有直接给出 NL L 的结论。两者之间差了一个“能否去掉 log^2”的鸿沟。5. PSPACE完全性与空间层级定理两个支柱5.1 QSAT量化布尔公式为什么是PSPACE完全如果要给 PSPACE 找一个代表性的完全问题那必然是 QSAT。QSAT 的全称是“可满足定量布尔公式问题”输入是一个被全称量词和存在量词层层包裹的布尔公式例如 ∃x ∀y ∃z (¬x ∨ y ∨ z)问题是判断这个公式是否为真。为什么 QSAT 在 PSPACE 里最简单的递归检测方法如下依次处理每一个量词。如果是存在量词就枚举当前变量的取值只要有一个取值能让剩余公式为真就算真如果是全称量词就枚举当前变量的所有取值要求每个取值都能让剩余公式为真。这个过程需要维护“当前变量的部分赋值”这个赋值长度不超过公式的变量个数空间是线性的。所以 QSAT ∈ PSPACE。QSAT 的 PSPACE 完全性证明则比较有代表性。任意一台多项式空间机器 M 和一个输入 x我们的目标是构造一个 QSAT 公式使得“公式为真”当且仅当“M 接受 x”。构造的思路仍然是配置图那一套把机器的每一步配置转移编码成布尔约束用存在量词表示“猜到了一条路径”用全称量词表示“路径上每一步都合法”。注意到这里用到了两种量词这恰好是 PSPACE 完全性证明里最精彩的部分。如果只用存在量词就只能表达“存在一条从起始到接受状态的路径”——那是 NP 完全问题 SAT 的结构。为了压制住“无限长循环”和“非法跳转”等坏情况需要一个全称量词来约束“路径上的每一步都必须满足合法转移关系、且最后一步是接受状态”。正是全称与存在交织才逼出了一个 PSPACE 完全的问题。5.2 空间层级定理空间越多能力越强吗空间层级定理说的是如果 f(n) 是空间可构造函数且 f(n) o(g(n))那么 SPACE(f(n)) ⊊ SPACE(g(n))。这是一个严格的包含关系。换句话说给你多一点空间你确实能解决更多问题。证明框架是标准的对角线方法。构造一台机器 M它在输入 w 上模拟某台把自身作为输入的机器并利用可构造的空间界限 g(n) 画出一道“栅栏”。如果被模拟的机器在 f(n) 空间内停机并接受M 就拒绝如果被模拟的机器拒绝M 就接受。这样 M 就不会出现在 SPACE(f(n)) 表中但它显然在 SPACE(g(n)) 空间内运行。这个思路和时间复杂性里的时间层级定理同源但空间版本更“干净”因为它可以在界限内精确控制自己的行为。空间层级定理的一个直观推论是SPACE(n) 作为一类不代表所有多项式空间。从 SPACE(log n) 到 SPACE(n) 到 SPACE(n^2)每跨一步都新增了能力。这也说明“空间越大能力越强”不是一句含糊的话它有一个严格的量级版本。5.3 空间复杂性在更大图景里的位置把空间类的所有已知关系串起来你会得到一条长长的箭头链条L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE NPSPACE ⊆ EXP。这个链条里有几处已知的大分隔比如时间层级定理保证 P ⊊ EXP但更细的分离完全处于待定状态。有一点值得留意PSPACE 是一个非常大的容器包括了很多看起来很困难的经典问题比如通用图灵机模拟某些指数逻辑系统、博弈论里的通用判定问题、以及和包含量词相关的各种决策问题。所以实际做题时如果要证明一个问题很难与其盯着 NP 完全性不如直接朝 PSPACE 完全性方向走往往一击即中。6. 实操视角算法设计中空间复杂度的分析与优化6.1 分析递归算法空间开销的正确姿势递归算法是空间复杂度分析的重灾区。很多人套用“递归深度 × 每层临时变量”这个公式时经常出错原因是没有把“输入本身占的空间”和“递归过程中新增的空间”分清楚。比如归并排序递归深度 O(log n)每层需要 O(n) 的辅助数组总空间 O(n)。这里很多人会误以为是 O(n log n)但各层的辅助数组空间可以复用栈深度只是叠加了每个层级的递归帧。快速排序递归深度取决于基准选取平均 O(log n)最坏 O(n)。每次划分是原地操作所以平均空间 O(log n)最坏 O(n)。DFS 遍历图需要一个访问标记数组和一个栈空间 O(V)。如果图特别大但你只关心连通性可以特意设计成对数空间的算法但普通 DFS 做不到。分析递归空间时最关键的一点是两个先后执行的递归调用不会同时存在它们的空间可以重叠。所以“递归总调用次数 × 每层空间”是错误公式正确公式是“最大递归深度 × 每层空间 非递归部分的全局空间”。如果不注意这个细节很容易把很多分治算法的空间复杂度算高一个数量级。6.2 用时间重复换空间典型技巧空间复杂度的优化几乎是固定三板斧第一看看能不能只保留前一步的 DP 数组把 O(nW) 降成 O(W)第二看看能不能用随机化替代显式存储例如 2-SAT 的随机游走算法把空间降到对数级别第三看看问题能不能转化成判定性问题而不是构造性问题因为很多问题的判定版本只需要存“当前是否可达”而不是整条路径。这里再强调一下“指针存储”的坑。你认为自己只存了一个链表头指针空间当然是 O(1)。但如果链表长度是 n指针本身需要 log n 位表示。你当然可以说“常数个 O(log n) 的指针也是 O(log n) 空间”但如果题目只要求 O(1) 空间那意味着我们连 log n 个比特都不能随大小增长。这也顺带说明了为什么有些看似“节省空间”的算法并不是严格的对数空间算法。给一个我讲课时常用的例子判断一个无向图是否连通。标准 BFS/DFS 空间 O(V)。有没有更省的有比如“逐步扩展法”从起点出发跳一跳能到的节点圈出一个集合反复向外扩一步直到不再变化。这个过程不需要保存整个访问数组只需保存当前集合的边界和大小计数器配合无向图的邻接表扫描可以把空间压到 O(log V)但代价是访问边表的次数暴增。这个例子非常清晰地展示了“时间换空间”的典型代价结构。6.3 空间复杂度分析中的三个经典误区第一个误区把“不额外分配数组”当成“O(1) 空间”。原地排序虽然不另外开数组但递归调用栈的深度依然是空间开销。堆排序因为用迭代彻底避开了递归栈所以能真正做到 O(1) 额外空间快排就做不到。第二个误区忽略输入带寻址。在做对数空间类分析时很多人觉得“我只是在输入带上从左往右扫一遍不会用额外空间”。严格讲你至少需要一个位置计数器来记住当前扫描位置这个计数器就是 log n 空间。在很多情况下一个 O(log n) 空间算法可以只靠不断重扫输入带完成计算但如果你以为这是 O(1)后续的 L 类归约证明都会约出问题。第三个误区把空间复杂度和内存占用直接划等号。图灵机的空间复杂度讨论的是工作带上的存储单元数而真实程序里程序代码本身的体积、编译生成的结构体对齐、系统栈的管理开销都不属于这个理论模型。理论模型做的是抽象度量它忽略常数和具体实现的所有低阶细节。如果做算法的复杂度分析时总被这些实际细节干扰很难看清问题的本质量级。7. 常见问题与排查思路学习空间复杂性那些最容易卡住的地方7.1 常见问题速查表常见疑问易错认知正确理解输入算不算空间整个输入需要 O(n) 空间所以所有算法空间至少 O(n)输入带只读不计入空间复杂度只有工作带算空间Savitch定理为什么不让 L NL平方关系也是等价所以 L 应该等于 NL平方只把 log n 变 log^2 nNL 与 L 的差距依然未知PSPACE 完全性是否需要全称量词只用存在量词就能表达 PSPACE 问题只用存在量词表达的是 NP 结构全称量词的约束才压出 PSPACE空间可构造函数是否多余任何函数都能做空间界限只有空间可构造函数才能在对角化中被机器“掌控”非可构造函数连机器自我限制都做不到常数空间 O(1) 是否普遍只要不动态分配数组就是 O(1)需要存储随输入规模增长的指针/计数器时空间就是 O(log n)这张表里每一行都是我教学生时反复纠正过的真实问题。尤其是最后一行“指针计数器”的情况几乎每个初次接触对数空间复杂度的人都会栽一次。记住空间复杂度是渐进的任何随输入规模增长而增长的存储需求都要以相应量级计入空间复杂度。7.2 学完本章后你应该具备的三种能力第一能快速判断一个问题应该属于哪个复杂度类。判断依据不是“算法的时间复杂度”而是“算法需要的峰值工作存储量”。看到可满足性类问题想 NP看到带有量词嵌套的非平凡布尔决策想 PSPACE看到只需要扫一遍输入并更新常数个计数器的问题先怀疑 L。第二能动手画出配置图并估算配置数。进入空间复杂性领域后配置图不再只是一个证明工具它应该成为你分析算法的一个常规手段。面做一个复杂度论证时第一件事永远是问“这台机器的配置空间有多大从初始配置到接受配置这段路该怎么证明”第三能熟练进行空间-时间权衡的取舍。真实工作里内存比 CPU 更常成为瓶颈。当你遇到一个空间超限的算法先看看它的递归深度能不能降再看 DP 数组能不能滚最后想能不能用重复计算换空间。Savitch 给我们的经验是在空间不够时重新计算并不可怕只要重算的次数没有造成时间上的指数爆炸。7.3 最后分享一点个人学习心得我自己学这一章时最大的领悟是“空间”这个概念比“时间”更需要模型感。时间就是步数凭直觉就能数空间却要时刻问“哪些存储是算的、哪些不算、哪些可以复用”。如果不建立一个稳定的模型多带图灵机 工作带峰值 配置图很容易在分析时出现前后矛盾的标准。另外一个小技巧是每次学完一个空间类试着在配置图上手动跑一个最简单的实例。比如拿一台需要 log n 空间的机器画出它的配置图数一数配置数量级。亲手算过一次后你就不会再觉得那些包含关系是凭空掉下来的。空间复杂性的所有关键结论几乎都能在配置图上“看”出来——这是这一章送给我的最大思维工具也希望它能帮你看清那些纸面上的定理背后真正发生的事。