第26章 复杂度理论
学习目标
- 掌握渐近符号的形式化定义与运算
- 理解摊还分析的三种方法
- 掌握NP完全性理论的基本概念
- 理解问题复杂度的下界证明方法
- 掌握算法优化的理论基础
26.1 渐近符号
26.1.1 形式化定义
定义 26.1（大O符号） $f(n) = O(g(n))$ 当且仅当存在正常数 $c$ 和 $n_0$，使得：
$$\forall n \geq n_0: 0 \leq f(n) \leq c \cdot g(n)$$
定义 26.2（大Ω符号） $f(n) = \Omega(g(n))$ 当且仅当存在正常数 $c$ 和 $n_0$，使得：
$$\forall n \geq n_0: 0 \leq c \cdot g(n) \leq f(n)$$
定义 26.3（大Θ符号） $f(n) = \Theta(g(n))$ 当且仅当：
$$f(n) = O(g(n)) \land f(n) = \Omega(g(n))$$
定义 26.4（小o符号） $f(n) = o(g(n))$ 当且仅当：
$$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$$
定义 26.5（小ω符号） $f(n) = \omega(g(n))$ 当且仅当：
$$\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$$
26.1.2 性质
定理 26.1（传递性）
- $f = O(g) \land g = O(h) \Rightarrow f = O(h)$
- $f = \Omega(g) \land g = \Omega(h) \Rightarrow f = \Omega(h)$
- $f = \Theta(g) \land g = \Theta(h) \Rightarrow f = \Theta(h)$
定理 26.2（自反性）
- $f = O(f)$
- $f = \Omega(f)$
- $f = \Theta(f)$
定理 26.3（对称性） $f = \Theta(g) \Leftrightarrow g = \Theta(f)$
定理 26.4（转置对称性） $f = O(g) \Leftrightarrow g = \Omega(f)$
26.1.3 运算规则
定理 26.5（加法规则） 若 $f_1 = O(g_1)$ 且 $f_2 = O(g_2)$，则：
$$f_1 + f_2 = O(\max(g_1, g_2))$$
定理 26.6（乘法规则） 若 $f_1 = O(g_1)$ 且 $f_2 = O(g_2)$，则：
$$f_1 \cdot f_2 = O(g_1 \cdot g_2)$$
定理 26.7（多项式规则） 对于 $k$ 次多项式 $p(n)$：
$$p(n) = \Theta(n^k)$$
26.2 摊还分析
26.2.1 形式化定义
定义 26.6（摊还代价） 对于数据结构操作序列，摊还代价是总代价除以操作次数。
定义 26.7（摊还分析） 摊还分析证明数据结构操作序列的总代价上界，即使单次操作代价可能很高。
26.2.2 聚合分析
定义 26.8（聚合分析） 直接计算 $n$ 次操作的总代价 $T(n)$，则摊还代价为 $T(n)/n$。
例：栈的多重弹出
class Stack:
def __init__(self):
self.items = []
def push(self, x):
self.items.append(x)
def pop(self):
return self.items.pop() if self.items else None
def multipop(self, k):
result = []
while self.items and k > 0:
result.append(self.items.pop())
k -= 1
return result定理 26.8 $n$ 次栈操作（push、pop、multipop）的总代价为 $O(n)$。
证明：每个元素最多被push一次、pop一次。总操作数不超过 $2n$，故总代价 $O(n)$。摊还代价 $O(1)$。 ∎
26.2.3 核算方法
定义 26.9（核算方法） 为每个操作分配摊还代价，使得摊还代价之和等于实际代价之和加上存储的"信用"。
条件：对于任意操作序列，累计信用非负。
例：动态数组扩容
class DynamicArray:
def __init__(self):
self.capacity = 1
self.size = 0
self.array = [None] * self.capacity
def append(self, x):
if self.size == self.capacity:
self._resize()
self.array[self.size] = x
self.size += 1
def _resize(self):
new_capacity = 2 * self.capacity
new_array = [None] * new_capacity
for i in range(self.size):
new_array[i] = self.array[i]
self.array = new_array
self.capacity = new_capacity定理 26.9 动态数组append操作的摊还代价为 $O(1)$。
证明：设摊还代价为 3：
- 1 用于插入元素
- 1 存储为信用（用于未来搬迁）
- 1 存储为信用（用于帮助搬迁其他元素）
扩容时，$n$ 个元素搬迁，使用存储的 $n$ 信用。信用始终非负。 ∎
26.2.4 势能方法
定义 26.10（势能函数） 势能函数 $\Phi$ 将数据结构状态映射到非负实数。
定义 26.11（摊还代价） 第 $i$ 次操作的摊还代价：
$$\hat{c}i = c_i + \Phi(D_i) - \Phi(D)$$
其中 $c_i$ 为实际代价，$D_i$ 为操作后状态。
定理 26.10 若 $\Phi(D_0) = 0$ 且对所有 $i$，$\Phi(D_i) \geq 0$，则：
$$\sum_{i=1}^{n} c_i \leq \sum_{i=1}^{n} \hat{c}_i$$
证明：
$$\sum_{i=1}^{n} \hat{c}i = \sum^{n} (c_i + \Phi(D_i) - \Phi(D_{i-1})) = \sum_{i=1}^{n} c_i + \Phi(D_n) - \Phi(D_0)$$
由 $\Phi(D_n) \geq 0$ 和 $\Phi(D_0) = 0$：
$$\sum_{i=1}^{n} \hat{c}i \geq \sum^{n} c_i$$
∎
例：二进制计数器
class BinaryCounter:
def __init__(self, n: int):
self.bits = [0] * n
def increment(self):
i = 0
while i < len(self.bits) and self.bits[i] == 1:
self.bits[i] = 0
i += 1
if i < len(self.bits):
self.bits[i] = 1定理 26.11 二进制计数器increment操作的摊还代价为 $O(1)$。
证明：定义势能 $\Phi$ 为计数器中 1 的个数。
- 翻转 1→0：实际代价 1，势能减少 1，摊还代价 0
- 翻转 0→1：实际代价 1，势能增加 1，摊还代价 2
每次increment最多翻转一个 0→1，故摊还代价最多 2。 ∎
26.3 NP完全性理论
26.3.1 计算模型
定义 26.12（判定问题） 判定问题的答案为"是"或"否"。
定义 26.13（确定性图灵机） 确定性图灵机（DTM）在每一步有唯一确定的转移。
定义 26.14（非确定性图灵机） 非确定性图灵机（NTM）在每一步可能有多个转移，只要存在一条接受路径即接受。
26.3.2 复杂度类
定义 26.15（P类） P类是确定性图灵机在多项式时间内可解的判定问题集合：
$$P = \bigcup_{k=1}^{\infty} \text{DTIME}(n^k)$$
定义 26.16（NP类） NP类是非确定性图灵机在多项式时间内可解的判定问题集合：
$$NP = \bigcup_{k=1}^{\infty} \text{NTIME}(n^k)$$
定义 26.17（NP等价刻画） 问题 $L \in NP$ 当且仅当存在多项式时间算法验证"是"实例。
定理 26.12 $P \subseteq NP$。
证明：确定性图灵机是非确定性图灵机的特例。 ∎
26.3.3 多项式归约
定义 26.18（多项式时间归约） 问题 $A$ 多项式时间归约到 $B$（记作 $A \leq_p B$），若存在多项式时间可计算的函数 $f$，使得：
$$x \in A \Leftrightarrow f(x) \in B$$
定理 26.13（归约传递性） 若 $A \leq_p B$ 且 $B \leq_p C$，则 $A \leq_p C$。
证明：设 $f$ 将 $A$ 归约到 $B$，$g$ 将 $B$ 归约到 $C$。则 $g \circ f$ 将 $A$ 归约到 $C$。多项式函数的复合仍为多项式。 ∎
26.3.4 NP完全性
定义 26.19（NP困难） 问题 $B$ 是NP困难的，若对所有 $A \in NP$：$A \leq_p B$。
定义 26.20（NP完全） 问题 $B$ 是NP完全的，若 $B \in NP$ 且 $B$ 是NP困难的。
定理 26.14（Cook-Levin定理） 布尔可满足性问题（SAT）是NP完全的。
证明概要：
- SAT $\in NP$：给定赋值，可在多项式时间验证是否满足公式
- SAT是NP困难的：模拟NTM的计算过程，构造布尔公式表示计算历史
∎
定理 26.15 若存在NP完全问题 $L \in P$，则 $P = NP$。
证明：设 $L$ 为NP完全且 $L \in P$。对于任意 $A \in NP$，由NP完全性，$A \leq_p L$。由 $L \in P$，$A \in P$。故 $NP \subseteq P$，结合 $P \subseteq NP$，得 $P = NP$。 ∎
26.3.5 经典NP完全问题
| 问题 | 描述 |
|---|---|
| SAT | 布尔公式可满足性 |
| 3-SAT | 3-CNF公式可满足性 |
| 顶点覆盖 | 图是否存在大小 $\leq k$ 的顶点覆盖 |
| 独立集 | 图是否存在大小 $\geq k$ 的独立集 |
| 团 | 图是否存在大小 $\geq k$ 的团 |
| 哈密顿路径 | 图是否存在经过所有顶点的路径 |
| TSP判定 | 是否存在长度 $\leq k$ 的哈密顿回路 |
| 背包判定 | 是否存在价值和 $\geq v$ 的物品子集 |
26.4 下界理论
26.4.1 信息论下界
定义 26.21（信息论下界） 基于问题输出空间大小的下界。
定理 26.16（排序下界） 比较排序的最坏情况需要 $\Omega(n \log n)$ 次比较。
证明：排序问题的输出空间大小为 $n!$（所有排列）。每次比较最多将输出空间减半。需要至少 $\log_2(n!) = \Omega(n \log n)$ 次比较。 ∎
26.4.2 对抗性论证
定义 26.22（对抗者） 对抗者是一个"恶意"的对手，根据算法的查询给出最不利的回答。
定理 26.17（查找下界） 在最坏情况下，查找有序数组中的元素需要 $\Omega(\log n)$ 次比较。
证明：对抗者维护可能的答案区间。每次比较后，对抗者选择保留较大的区间。区间大小最多减半，需要 $\Omega(\log n)$ 次比较。 ∎
26.4.3 代数决策树模型
定义 26.23（代数决策树） 代数决策树是每个内部节点包含多项式比较 $f(x) \geq 0$ 的决策树。
定理 26.18（Ben-Or定理） 对于判定问题 $W \subseteq \mathbb{R}^n$，若 $W$ 有 $N$ 个连通分支，则代数决策树高度为：
$$h = \Omega(\log N - n)$$
26.5 算法优化策略
26.5.1 空间换时间
原理：使用额外空间存储中间结果，减少重复计算。
例：记忆化搜索
from functools import lru_cache
from typing import Dict
def fibonacci_memo(n: int, memo: Dict[int, int] = None) -> int:
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
return memo[n]
@lru_cache(maxsize=None)
def fibonacci_lru(n: int) -> int:
if n <= 1:
return n
return fibonacci_lru(n - 1) + fibonacci_lru(n - 2)26.5.2 预处理
原理：提前计算并存储信息，加速后续查询。
例：前缀和
class PrefixSum:
def __init__(self, arr: list):
self.prefix = [0]
for x in arr:
self.prefix.append(self.prefix[-1] + x)
def range_sum(self, left: int, right: int) -> int:
return self.prefix[right + 1] - self.prefix[left]26.5.3 懒惰求值
原理：延迟计算直到真正需要时。
class LazyRange:
def __init__(self, start: int, end: int):
self.start = start
self.end = end
def __iter__(self):
return iter(range(self.start, self.end))
def __getitem__(self, index: int) -> int:
return self.start + index
def __len__(self) -> int:
return self.end - self.start26.5.4 分支预测优化
def sum_with_branch_prediction(arr: list, threshold: int) -> int:
total = 0
for x in arr:
if x > threshold:
total += x
return total
def sum_branch_free(arr: list, threshold: int) -> int:
total = 0
for x in arr:
total += x * (x > threshold)
return total26.6 复杂度层次
26.6.1 时间层次定理
定理 26.19（时间层次定理） 对于时间可构造函数 $f(n)$：
$$\text{DTIME}(f(n)) \subsetneq \text{DTIME}(f(n)^2)$$
推论 26.1 $P \subsetneq \text{EXP}$。
26.6.2 空间层次定理
定理 26.20（空间层次定理） 对于空间可构造函数 $f(n)$：
$$\text{DSPACE}(f(n)) \subsetneq \text{DSPACE}(f(n) \log f(n))$$
26.6.3 复杂度类关系
$$\text{L} \subseteq \text{NL} \subseteq P \subseteq \text{NP} \subseteq \text{PSPACE} \subseteq \text{EXP}$$
26.7 本章小结
本章介绍了复杂度理论：
- 渐近符号：$O$、$\Omega$、$\Theta$、$o$、$\omega$ 的形式化定义
- 摊还分析：聚合、核算、势能三种方法
- NP完全性：P vs NP、多项式归约、NP完全问题
- 下界理论：信息论下界、对抗性论证
- 优化策略：空间换时间、预处理、懒惰求值
结语
恭喜您完成《Python数据结构》的学习！
本书从基础数据结构到高级算法，系统介绍了：
- 线性结构：列表、栈、队列
- 树形结构：二叉树、平衡树、堆
- 图结构：表示、遍历、最短路径、最小生成树
- 哈希结构：哈希表、冲突解决
- 排序算法：比较排序、线性排序
- 搜索算法：二分查找、高级搜索
- 算法范式：分治、动态规划、贪心
- 复杂度理论：渐近分析、NP完全性
数据结构与算法是计算机科学的基石。持续学习与实践将使您成为更优秀的程序员。
参考文献
- Cormen, T. H., et al. (2009). Introduction to Algorithms, 3rd ed. MIT Press.
- Sipser, M. (2012). Introduction to the Theory of Computation, 3rd ed. Cengage Learning.
- Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press.
- Tarjan, R. E. (1985). Amortized computational complexity. SIAM Journal on Algebraic Discrete Methods, 6(2), 306-318.
- Cook, S. A. (1971). The complexity of theorem-proving procedures. STOC, 151-158.