第7章：空间复杂性（Space Complexity）

一、导读

1.1 本章学习目标

第7章讲解空间复杂性——计算所需的内存资源。

1.2 为什么第七章如此重要

空间复杂性补充了时间复杂性，完整描述了算法的资源需求。

1.3 核心问题引导

L 和 NL 是什么类？

Savitch 定理是什么？

空间和时间有什么关系？

NL 完全问题有哪些？

二、核心概念详解

7.1 空间复杂性类

L：对数空间可判定的语言
NL：非确定性对数空间可判定的语言

关系：L ⊆ NL ⊆ P

7.2 Savitch 定理

定理：对于任意函数 $s(n) \geq \log n$，如果非确定性图灵机在 $O(s(n))$ 空间内判定语言 $L$，则确定性图灵机在 $O(s(n)^2)$ 空间内判定 $L$。

推论：NSPACE(s(n)) ⊆ DSPACE(s(n)²)
特别地：NL ⊆ L² ⊆ P

这意味着非确定性不会增加太多空间需求

7.3 空间与时间的关系

关键关系：
- P ⊆ PSPACE（多项式空间）
- NP ⊆ PSPACE
- PSPACE ⊆ EXPTIME

开放问题：
- P = PSPACE？（大多数人认为不等）
- NP = PSPACE？

7.4 NL 完全

NL 完全问题：
- s-t 连通性（有向图）
- 2-SAT

如果 NL = L，则这些问题都在对数空间内可解

三、实战案例

7.1 空间复杂度分析

算法空间复杂度：
- 冒泡排序：O(1)（原地排序）
- 归并排序：O(n)（需要额外空间）
- DFS：O(h)（递归栈，h 为树高）
- BFS：O(w)（队列，w 为最大宽度）

四、本章小结

空间复杂性描述算法的内存需求。L 和 NL 是对数空间类。Savitch 定理表明非确定性不会增加太多空间需求。

五、思考与练习

L 和 NL 有什么区别？

Savitch 定理的含义是什么？

空间和时间如何权衡？

NL 完全问题有哪些？

PSPACE 完全问题有哪些？