CLRS《算法导论》核心知识补充

#数据结构 · #算法 · #CLRS · #主定理 · #摊还分析 · #NP完全 · #进阶

基于 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 合著的 Introduction to Algorithms（第 4 版）。本文补充 Hello 算法基础 未覆盖的深层内容：主定理、摊还分析、下界证明、斐波那契堆、van Emde Boas 树、字符串匹配、NP 完全性。

---

1. 算法分析进阶

1.1 主定理（Master Theorem）— 分治递归的通用解法

对于形如 $T(n)=a\cdot T(n/b)+f(n)$ 的递归式（$a\ge 1,b>1$）：

情况 1：若 $f(n)=O(n^{{\log }_{b}a-ϵ})$（$ϵ>0$），则 $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$

情况 2：若 $f(n)=\mathrm{\Theta }(n^{{\log }_{b}a}{\log }^{k}n)$，则 $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}{\log }^{k+1}n)$

情况 3：若 $f(n)=\mathrm{\Omega }(n^{{\log }_{b}a+ϵ})$ 且 $af(n/b)\le cf(n)$（$c<1$），则 $T(n)=\mathrm{\Theta }(f(n))$

实战练习

算法	递归式	a	b	$f(n)$	情况	结果
归并排序	$T(n)=2T(n/2)+O(n)$	2	2	$O(n)$	2 (k=0)	$\mathrm{\Theta }(n\log n)$
二分查找	$T(n)=T(n/2)+O(1)$	1	2	$O(1)$	2 (k=0)	$\mathrm{\Theta }(\log n)$
Strassen 矩阵乘	$T(n)=7T(n/2)+O(n^2)$	7	2	$O(n^2)$	1	$\mathrm{\Theta }(n^{{\log }_{2}7})\approx \mathrm{\Theta }(n^{2.81})$
遍历二叉树	$T(n)=2T(n/2)+O(1)$	2	2	$O(1)$	1	$\mathrm{\Theta }(n)$

思路：比较 $f(n)$ 和 $n^{{\log }_{b}a}$ 的增长速度——谁大谁主导。一样大则乘以 $\log n$。

flowchart TD
    Recur["T(n) = a·T(n/b) + f(n)"] --> Compare{"比较 f(n) 与 n^log_b_a"}
    Compare -->|"f(n) 更小<br/>（差 ε 倍）"| Case1["情况 1: T(n)=Θ(n^log_b_a)<br/>例: 二叉树遍历 O(n)"]
    Compare -->|"同等增长<br/>（可能差 log^k n）"| Case2["情况 2: T(n)=Θ(n^log_b_a·log^{k+1}n)<br/>例: 归并排序 O(n log n)"]
    Compare -->|"f(n) 更大<br/>（差 ε 倍, 且 af(n/b)≤cf(n)）"| Case3["情况 3: T(n)=Θ(f(n))<br/>例: 快速选择分区的部分递归"]
    Compare -->|"无法比较"| Fail["主定理不适用<br/>尝试递归树或代入法"]

    style Case1 fill:#4CAF50,color:#fff
    style Case2 fill:#2196F3,color:#fff
    style Case3 fill:#FF9800,color:#fff
    style Fail fill:#F44336,color:#fff
    style Recur fill:#607D8B,color:#fff

---

1.2 摊还分析（Amortized Analysis）

摊还分析回答："n 次操作的总时间是多少？"——而不是单次最坏时间。

方法一：聚合分析（Aggregate Method）

直接算 n 次操作的总代价，除以 n。

实例：动态数组扩容

插入 n 个元素的扩容次数：
  第 1 次扩容：拷贝 1 个元素
  第 2 次扩容：拷贝 2 个元素
  第 4 次扩容：拷贝 4 个元素
  ...
  第 2^k 次扩容：拷贝 2^k 个元素

总拷贝次数 ≤ n + n/2 + n/4 + ... ≤ 2n
n 次插入总代价 ≤ n*O(1) + 2n = O(n)
→ 每次插入摊还 O(1)

方法二：记账法（Accounting Method）

每次操作"预存"一些代价给未来。插入时多收一点，存到"账户"里，扩容时从账户扣。

每次插入收费 3 元：1 元插入，2 元存入账户
扩容时：拷贝每个元素的 1 元从账户中出
→ 账户永不透支 → 摊还 O(1)

方法三：势能法（Potential Method）

定义势能函数 $\mathrm{\Phi }(D_i)$ 表示数据结构 $D_i$ 的"势能"。摊还代价 = 实际代价 + $\mathrm{\Delta }\mathrm{\Phi }$。

动态数组的势能函数：$\mathrm{\Phi }=2\cdot size-capacity$（插入后势能升，扩容后势能降）。

---

1.3 基于比较的排序下界

定理：任何基于比较的排序算法，最坏情况下至少需要 $\mathrm{\Omega }(n\log n)$ 次比较。

证明思路（决策树模型）：

• n 个元素有 n! 种排列 → 决策树至少 n! 个叶子
• 高度为 h 的二叉树最多 $2^h$ 个叶子
• $2^h\ge n!$ → $h\ge \log (n!)\approx n\log n-n\log e=\mathrm{\Omega }(n\log n)$

推论：堆排序和归并排序在最坏意义上已经是最优的比较排序。

---

1.4 线性时间排序的下界突破

算法	时间	条件
计数排序	$O(n+k)$	整数，范围 k 不大
基数排序	$O(d(n+k))$	d 位数字，每位范围 k
桶排序	$O(n)$ 期望	均匀分布

这些算法不通过比较，因此突破了 $\mathrm{\Omega }(n\log n)$ 下界。

基数排序的精妙之处

基数排序有两种顺序：

• LSD (Least Significant Digit)：从低位到高位，必须用稳定排序
• MSD (Most Significant Digit)：从高位到低位，递归分桶

对 32 位整数排序：
  用 8 位为基数 → 4 轮 → 每轮 O(n+256)
  总计 O(4n) = O(n)

---

2. 高级数据结构

2.1 斐波那契堆（Fibonacci Heap）

二叉堆的插入是 $O(\log n)$。斐波那契堆的插入只需 O(1) 摊还。

核心操作对比

操作	二叉堆	斐波那契堆	说明
insert	$O(\log n)$	$O(1)$ 摊还	直接挂到根链表
extract-min	$O(\log n)$	$O(\log n)$ 摊还	删除最小，consolidate
decrease-key	$O(\log n)$	$O(1)$ 摊还	剪切 + 级联剪切
delete	$O(\log n)$	$O(\log n)$ 摊还	decrease-key + extract-min
merge	$O(n)$	$O(1)$	连接两个根链表

为什么摊还 O(1) 插入？

插入时不做任何结构调整——直接把新节点挂到根链表中。只有在 extract-min 时才做 consolidate（合并同度树）。

插入 1 → 根链表: [1]
插入 2 → 根链表: [1] [2]
...
插入 n → 根链表: [1] [2] ...[n]
extract-min → 遍历根链表找最小，然后两两合并同度树 → O(max_degree + n)

关键应用：Dijkstra 算法 + 斐波那契堆 → $O(E+V\log V)$（vs 二叉堆的 $O((V+E)\log V)$）。

但实际工程中几乎不用斐波那契堆——常数因子太大，且现代 CPU 对二叉堆的缓存友好度更好。

---

2.2 van Emde Boas 树（vEB Tree）

当 key 是小范围整数（0 到 u-1）时，vEB Tree 的增删查改都是 O(log log u)——比二叉搜索树的 O(log n) 更快。

原理

将全域 {0, 1, ..., u-1} 分为 √u 个簇，每个簇 √u 个元素。
递归地在簇内建立 vEB Tree。

结构	时间复杂度	空间	适用
二叉搜索树	$O(\log n)$	$O(n)$	通用
vEB Tree	$O(\log \log u)$	$O(u)$	key 范围小
哈希表	$O(1)$ 期望	$O(n)$	不需要有序

应用：IP 路由表（32 位整数 key）、网络交换机的 TCAM 替代、DNS 缓存。

但在实际系统中更多用**压缩前缀树（Patricia Trie）**来替代 vEB Tree——空间更小。

---

2.3 并查集（Disjoint-Set / Union-Find）

并查集维护一个不相交集合的划分。经典实现同时使用：

1. 按秩合并：矮树挂在高树下
2. 路径压缩：查找时把路径上所有节点直接挂到根

type UnionFind struct {
    parent []int
    rank   []int
}

func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x]) // 路径压缩
    }
    return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) {
    rx, ry := uf.Find(x), uf.Find(y)
    if rx == ry { return }
    if uf.rank[rx] < uf.rank[ry] {
        rx, ry = ry, rx
    }
    uf.parent[ry] = rx
    if uf.rank[rx] == uf.rank[ry] {
        uf.rank[rx]++
    }
}

摊还复杂度：$O(\alpha (n))$，其中 $\alpha (n)$ 是阿克曼函数的反函数——对任何实际 n≤宇宙原子数，$\alpha (n)\le 4$。近乎常数时间。

应用：

• Kruskal 最小生成树（判断加入边是否形成环）
• 图的连通分量
• 图像处理（连通区域标记）
• 等价类划分（编译器中的类型等价）

带权并查集

节点不仅记录父节点，还记录到父节点的"权值"（如距离、差值）：

// 食物链问题 / 变量等式和不等式
// parent[x] 和 weight[x]（x 到 parent[x] 的关系）
func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        root := uf.Find(uf.parent[x])
        uf.weight[x] += uf.weight[uf.parent[x]] // 累加权值
        uf.parent[x] = root
    }
    return uf.parent[x]
}

---

3. 选择算法（Selection）进阶

3.1 BFPRT 算法 — 最坏 O(n) 的选择

快速选择的平均时间是 O(n)，但最坏 O(n²)。BFPRT（Blum-Floyd-Pratt-Rivest-Tarjan, 1973）保证最坏 O(n)：

1. 将 n 个元素分成 ⌈n/5⌉ 组，每组 5 个
2. 每组内部排序，取中位数 → ⌈n/5⌉ 个中位数
3. 递归求这些中位数的中位数 → pivot
4. 以 pivot 分区 → 类似快速选择递归一侧

T(n) ≤ T(n/5) + T(7n/10) + O(n) → T(n) = O(n)

工程现实：BFPRT 常数因子很大（约 50×），实践中快速选择 + 随机 pivot 几乎不会碰到最坏情况。

---

3.2 顺序统计量（Order Statistics）

问题	算法	复杂度
最小值/最大值	遍历	$O(n)$
同时找最小和最大	成对比较	$\lceil 3n/2\rceil -2$ 次比较
第 k 小	快速选择	$O(n)$ 期望
第 k 小（最坏保证）	BFPRT	$O(n)$
中位数	快速选择 / BFPRT	$O(n)$
Top K	堆	$O(n\log k)$
Top K（全排序）	排序	$O(n\log n)$

---

4. 动态规划进阶

4.1 最优子结构与重叠子问题的严格区分

特性	含义	检验方法
最优子结构	问题的最优解包含子问题的最优解	反证法：如果不是，可以替换得到更好的解
重叠子问题	递归树中反复出现相同子问题	画出递归树，看是否有重复节点

不具备最优子结构的例子：最长简单路径（不含重复顶点）——子路径的最长简单路径组合起来可能不是简单路径（有环）。

4.2 两种实现方式

	自顶向下（记忆化）	自底向上（填表）
实现	递归 + memo	迭代填表
栈溢出	可能（递归深度）	不会
计算顺序	按需计算	必须全部计算
适用	子问题稀疏	子问题密集

4.3 经典问题深入

最长公共子序列（LCS）

dp[i][j] =
  dp[i-1][j-1] + 1              (if X[i] == Y[j])
  max(dp[i-1][j], dp[i][j-1])   (if X[i] != Y[j])

应用：diff 工具（git diff）、DNA 序列比对、文件比较

最优二叉搜索树（Optimal BST）

给定 key 的查找概率分布，构建使平均查找代价最小的 BST。$O(n^3)$ DP。

dp[i][j] = 以 i..j 为 key 的最优 BST 期望代价
dp[i][j] = min_{k=i}^{j} (dp[i][k-1] + dp[k+1][j]) + sum_{p=i}^{j} prob[p]

Knuth 优化 → O(n²)

---

5. 字符串匹配

5.1 算法总览

算法	预处理	匹配	特点
朴素	0	$O(nm)$	简单，短模式足够快
KMP	$O(m)$	$O(n)$	标准，不回溯文本
Boyer-Moore	$O(m)$	$O(n/m)$ 最好	从右向左匹配，实际最快
Rabin-Karp	$O(m)$	$O(n+m)$ 期望	滚动哈希，多模式
基于自动机	$O(m|\mathrm{\Sigma }|)$	$O(n)$	理论优美，空间大

5.2 KMP（Knuth-Morris-Pratt）

核心是前缀函数 $\pi$：模式串的每个前缀，其最长真前缀且是真后缀的长度。

pattern = "ababc"
π[0]=0  (a)
π[1]=0  (ab)
π[2]=1  (aba: a 是前后缀)
π[3]=2  (abab: ab 是前后缀)
π[4]=0  (ababc)

匹配时文本指针不回退，只移动模式指针到 π 值。

sequenceDiagram
    participant T as 文本: "abababc"
    participant P as 模式: "ababc"
    participant Pi as 前缀函数 π

    Note over T,Pi: KMP 匹配过程

    rect rgb(240, 248, 255)
        Note over T,Pi: Step 1: 匹配到位置4时 "ababa" vs "ababc" 失配
        T->>P: "ababa" vs "ababc" (位置4: 'a'≠'c')
        P->>Pi: 查 π[3]=2 → 模式回退到位置2
    end

    rect rgb(255, 248, 240)
        Note over T,Pi: Step 2: 从"ab"继续匹配
        Pi->>P: π[3]=2, 已知前2字符"ab"已匹配, 从位置2继续
        P->>T: 文本指针不动, 继续比较 → 匹配成功
    end

    Note over T,Pi: 关键: 文本指针永不回退!

5.3 Rabin-Karp

使用滚动哈希，在 O(1) 时间内从 hash(s[i:i+m]) 计算 hash(s[i+1:i+m+1])：

hash(s[i+1:i+m+1]) = (hash(s[i:i+m]) - s[i] * d^{m-1}) * d + s[i+m]

应用：多模式匹配、抄袭检测（对文档的 n-gram 做哈希）。

---

6. 图算法进阶

6.1 强连通分量（SCC）— Kosaraju 算法

1. 对原图做 DFS，按完成时间（Black 顺序）记录节点
2. 反转图中所有边的方向
3. 按步骤 1 的逆序，在反转图上做 DFS
   → 每次 DFS 遍历到的节点构成一个 SCC

直觉：按完成时间逆序，保证每次从"汇集 SCC"（没有出边的 SCC）开始探索。

6.2 Tarjan 算法（单次 DFS 求 SCC）

与 Kosaraju 不同，Tarjan 只需一次 DFS，使用 dfn（发现时间）和 low（能回溯到的最早节点）。

6.3 最大流 — Ford-Fulkerson & Edmonds-Karp

残差网络 + 增广路径：
1. 初始化流量为 0
2. 在残差网络中找一条从 s 到 t 的增广路径
3. 沿路径推送瓶颈流量
4. 重复直到没有增广路径 → 得到最大流

Ford-Fulkerson: DFS 找增广路，O(E·|f_max|)（容量为整数时）
Edmonds-Karp:   BFS 找增广路，O(VE²)
Dinic:          O(V²E)，实际更快

应用：二分图匹配、网络吞吐量、任务分配、图像分割。

6.4 最小生成树理论补充

	Kruskal	Prim
策略	全局排序，从小到大加边	局部生长，每次加最近节点
数据结构	并查集	优先队列
复杂度	$O(E\log E)$	$O(E\log V)$
稠密图	劣	优
稀疏图	优	劣
分布式	天然支持	难

---

7. NP 完全性

7.1 问题复杂度分类

P: 多项式时间可解         → 排序、最短路径、最小生成树
NP: 多项式时间可验证       → 数独（验证快）、哈密顿回路
NP-Complete: NP 中最难的   → 3-SAT、旅行商、子集和
NP-Hard: 至少和 NP 一样难  → 停机问题（不可判定）

P vs NP：尚未证明 $P\ne NP$ 或 $P=NP$，但多数计算机科学家相信 $P\ne NP$。

7.2 经典 NP 完全问题

问题	描述
3-SAT	第一个被证明为 NP 完全的问题（Cook-Levin）
子集和	给定整数集，是否存在子集和为 0？
旅行商（TSP）	访问所有城市一次，最短路径
哈密顿回路	访问所有顶点一次的环
顶点覆盖	用 k 个顶点覆盖所有边
图着色	用 k 种颜色给图着色

7.3 面对 NP 完全问题的策略

1. 小规模穷举（n<20）
2. 近似算法：不保证最优，但保证与最优的比值（TSP 的 Christofides 算法 ≤ 1.5× 最优）
3. 参数化算法：对某个参数 k，运行时间 $O(f(k)\cdot n^c)$
4. 启发式搜索：遗传算法、模拟退火、蚁群
5. 限制问题：在特殊子类上多项式可解（如树上的 TSP）

---

8. 多线程算法

8.1 性能度量

度量	符号	含义
工作量（Work）	$T_1$	单处理器总时间
跨度（Span）	$T_{\mathrm{\infty }}$	无限处理器下的关键路径长度
并行度	$T_1/T_{\mathrm{\infty }}$	理论最大加速比

8.2 并行归并排序的 Work & Span

归并排序：
  T₁(n) = Θ(n log n)
  T∞(n) = T∞(n/2) + Θ(log² n) = Θ(log³ n)  ← 并行 merge 的 span
  并行度 = Θ(n / log² n)

---

参考

• CLRS《算法导论》第 4 版
• MIT 6.046 算法设计与分析
• Stanford CS161 算法设计与分析
• Hello 算法 — 中文入门教程