📕 算法导论 · 定理库
25 个定理 · 来自 CLRS 第4版
📊 25 个定理
📐 8 个主题领域
📖 Ch4–35 覆盖范围
🧮 基础与排序 (Part I-II)
🔴 数据结构 (Part III)
红黑树高度定理
含 n 个内部节点的红黑树高度不超过 2lg(n+1)
红黑树扩张定理
数据结构扩张四步法保持红黑性质的充分条件
B 树高度定理
包含 n 个关键字的 B 树高度 O(log n)，磁盘 I/O 最优
按秩合并与路径压缩定理
并查集 m 次操作总时间 O(m α(n))，反阿克曼函数近乎常数
🎯 算法设计策略 (Part IV-V)
Huffman 最优前缀码定理
Huffman 算法产生期望编码长度最小的最优前缀码
欧拉定理
k^φ(n) ≡ 1 (mod n) 当 gcd(k,n)=1，RSA 的理论基础
RSA 正确性定理
证明 RSA 加解密过程的数学正确性与唯一可逆性
🕸️ 图算法基础 (Part VI)
括号定理
DFS 时间戳区间完全嵌套或不相交，与括号结构对应
拓扑排序正确性定理
DFS 完成时间递减排序 ⇔ 图为 DAG
安全边定理
跨越割的轻边是 MST 安全边的充要条件
Kruskal 正确性定理
按权值增量选边 + 并查集检测环 → 生成最小生成树
Prim 正确性定理
每次将轻边连接的顶点加入集合 A 保持 MST 切分性质
🔀 高级图与网络流
Dijkstra 正确性定理
非负权图中贪心选择最近未确定顶点的松弛策略正确
Bellman-Ford 正确性定理
n-1 轮松弛后正确计算单源最短路径（无负权回路）
Floyd-Warshall 正确性定理
DP 逐点扩展中间结点集，正确计算所有结点对最短路径
最大流最小割定理
流网络中 max flow = min cut capacity（Ford-Fulkerson 方法核心）
Hall 婚姻定理
二部图存在完美匹配 ⇔ 任意子集邻域 ≥ |子集|
Berge 定理
匹配 M 最大 ⇔ 无 M 增广路径；增广路迭代终止于最优
König-Egerváry 定理
二部图中最大匹配数 = 最小顶点覆盖数