算法复杂度：递归树、主定理与摊还分析

复杂度分析是算法设计的基础语言。本文不止于列公式——重点建立直觉：为什么归并排序是 nlogn 而不是 n²？递归树怎么画？摊还分析的"信用"从哪来？ 对应《算法导论》第 3、4、17 章。

目录

章节	说明
渐近符号	Θ/O/Ω 的精确定义与常见误用
复杂度直觉：增长速度意味着什么	从数字感受差距，而不只是符号
递归树法：手推复杂度	画图推导，不靠死记结论
主定理：递归树的快捷方式	三种情况的直觉解释
摊还分析：均摊而非单次最坏	聚合法、记账法、势能法深度推导
下界分析：证明算法已最优	比较排序 Ω(nlogn) 的决策树证明
常见算法复杂度速查	排序、数据结构、图算法一览

渐近符号

精确定义

渐近符号描述 n → ∞ 时函数的增长行为，忽略常数因子和低阶项：

符号	含义	形式定义	数学类比
Θ(g)	紧确界，f 与 g 同阶	∃c₁,c₂,n₀：∀n≥n₀，c₁g(n) ≤ f(n) ≤ c₂g(n)	f = g
O(g)	上界，f 不超过 g	∃c,n₀：∀n≥n₀，f(n) ≤ cg(n)	f ≤ g
Ω(g)	下界，f 不低于 g	∃c,n₀：∀n≥n₀，f(n) ≥ cg(n)	f ≥ g
o(g)	严格上界	∀c>0，∃n₀：∀n≥n₀，f(n) < cg(n)	f < g（严格）
ω(g)	严格下界	∀c>0，∃n₀：∀n≥n₀，f(n) > cg(n)	f > g（严格）

关键区别：O 允许 f=g（≤），o 不允许（<）。例如 n = O(n) 成立，但 n ≠ o(n)。

为什么忽略常数和低阶项是合理的？

f(n) = 3n² + 100n + 500，当 n=10000 时：

3n²    = 300,000,000   占比 99.97%
100n   =   1,000,000   占比  0.03%
500    =         500   可忽略不计

低阶项在 n 足够大时完全被主项淹没。常数因子则取决于硬件、语言、编译器——同一算法在 GPU 上可能快 100 倍，所以用渐近符号剥离硬件差异，只关注算法本质。

常见误用

❌ "快速排序是 O(nlogn)"
✅ "快速排序平均情况 Θ(nlogn)，最坏情况（已排序输入）Θ(n²)"
   O 是上界，说"O(nlogn)" 技术上没错但信息量不足

❌ "A 算法 O(n²) 比 B 算法 O(nlogn) 慢"
✅ 渐近比较要在 n 足够大时才成立：
   若 A = 0.001n²，B = 1000nlogn
   当 n < 10000 时 A 反而更快
   → 小数据量时常数因子比阶数更重要

❌ "二分查找是 O(logn)，所以和 O(1) 差不多"
✅ O(logn) 对 n=10⁹ 只需约 30 步，实践中确实接近 O(1)，
   但这是直觉，不是定义

复杂度直觉：增长速度意味着什么

光看符号没有感觉，用真实数字感受差距。假设每步操作耗时 1 纳秒（10⁻⁹ 秒）：

复杂度	n = 10²	n = 10⁶	n = 10⁹	能做什么
O(1)	1ns	1ns	1ns	哈希表查找
O(logn)	7ns	20ns	30ns	二分查找
O(n)	100ns	1ms	1s	线性扫描
O(nlogn)	700ns	20ms	30s	归并排序
O(n²)	10μs	17分钟	31年	冒泡排序
O(2ⁿ)	10²⁴年	∞	∞	暴力枚举

工程界限（1秒内能完成的 n 上限）：O(n) → 10⁸；O(nlogn) → 10⁷；O(n²) → 10⁴；O(2ⁿ) → 25。

logn 到底有多小？

log₂(10)      ≈ 3.3
log₂(1000)    ≈ 10
log₂(10⁶)     ≈ 20
log₂(10⁹)     ≈ 30
log₂(10¹⁸)    ≈ 60   ← 宇宙中原子数量的数量级

即使 n 是宇宙中的原子数，log₂(n) 也只有 270

这就是为什么二分查找、平衡树在任何实际规模下都是"瞬间完成"的。

递归树法：手推复杂度

为什么需要递归树

主定理只适用于 T(n) = aT(n/b) + f(n) 这种规整形式。遇到不规整的递推式（子问题规模不同、有多个递推项），必须靠递归树。

例 1：归并排序 T(n) = 2T(n/2) + n

画出递归树，每层列出所有子问题及其代价：

graph TD
    A["n<br/>代价 n"] --> B["n/2<br/>代价 n/2"]
    A --> C["n/2<br/>代价 n/2"]
    B --> D["n/4"]
    B --> E["n/4"]
    C --> F["n/4"]
    C --> G["n/4"]
    D --> H["..."]
    E --> H2["..."]
    F --> H3["..."]
    G --> H4["..."]

逐层统计代价：

层数	节点数	每节点代价	本层总代价
0	1	n	n
1	2	n/2	n
2	4	n/4	n
k	2^k	n/2^k	n
logn	n	1	n

关键观察：每层代价恰好都是 n，树高 logn，总代价 = n × logn = Θ(nlogn)。

直觉：递归树每层"合并"的总工作量相等，都是 n。树有 logn 层，所以是 nlogn。

例 2：不规整递推式 T(n) = T(n/3) + T(2n/3) + n

这个主定理无法直接套用（两个子问题规模不同），必须用递归树。

graph TD
    A["n"] --> B["n/3"]
    A --> C["2n/3"]
    B --> D["n/9"]
    B --> E["2n/9"]
    C --> F["2n/9"]
    C --> G["4n/9"]

关键问题：树有多高？左侧（每次取 1/3）最浅，右侧（每次取 2/3）最深：

最浅路径（左侧）：n → n/3 → n/9 → ... → 1    高度 = log₃(n)
最深路径（右侧）：n → 2n/3 → 4n/9 → ... → 1  高度 = log_{3/2}(n)

每层代价：验证每层之和是否仍为 n：

层 0：n
层 1：n/3 + 2n/3 = n
层 2：n/9 + 2n/9 + 2n/9 + 4n/9 = n
...（可以证明每层之和 = n）

结论：层数介于 log₃(n) 和 log_{3/2}(n) 之间，每层代价 = n：

T(n) = Θ(n · log_{3/2}(n)) = Θ(nlogn)

递归树法的步骤总结：① 画出树形展开；② 统计每层节点数和各自代价；③ 求每层总代价；④ 累加所有层。

主定理：递归树的快捷方式

主定理是递归树法的"快捷键"。理解了递归树，主定理就不是死记，而是一目了然。

递推式结构

T(n) = aT(n/b) + f(n)

• a 个子问题，每个规模 n/b，合并代价 f(n)
• 叶节点总数 = n^(log_b a)（记为 n^p）
• 叶节点总代价 = Θ(n^p)（每个叶代价 O(1)，共 n^p 个）

三种情况的直觉

flowchart TD
    Q["f(n) 与 n^p 谁主导？"] --> C1["f(n) 远小于 n^p<br/>叶节点主导"]
    Q --> C2["f(n) 与 n^p 同阶<br/>每层代价相等"]
    Q --> C3["f(n) 远大于 n^p<br/>根节点主导"]
    C1 --> R1["T(n) = Θ(n^p)<br/>情况 1"]
    C2 --> R2["T(n) = Θ(n^p · logn)<br/>情况 2"]
    C3 --> R3["T(n) = Θ(f(n))<br/>情况 3"]

    style R1 fill:#dae8fc,stroke:#6c8ebf
    style R2 fill:#fff2cc,stroke:#d6b656
    style R3 fill:#d5e8d4,stroke:#82b366

情况	条件	直觉	结论
情况 1	f(n) = O(n^(p-ε))	递归树底层（叶节点）代价主导，根和中间层可忽略	T(n) = Θ(n^p)
情况 2	f(n) = Θ(n^p · logᵏn)	每层代价相等，logn 层，乘以多一个 log	T(n) = Θ(n^p · log^(k+1)n)
情况 3	f(n) = Ω(n^(p+ε))	根节点（合并代价）主导，叶节点可忽略	T(n) = Θ(f(n))

完整推导示例：归并排序

T(n) = 2T(n/2) + n

① a=2, b=2, f(n)=n
② p = log₂2 = 1，即 n^p = n¹ = n
③ 比较 f(n)=n 与 n^p=n：
   f(n) = Θ(n^p · log⁰n)，情况 2（k=0）
④ 结论：T(n) = Θ(n · log¹n) = Θ(nlogn) ✅

主定理的盲区（需改用递归树）

❌ 子问题规模不等：T(n) = T(n/3) + T(2n/3) + n
❌ 子问题规模相减：T(n) = T(n-1) + n（链式展开，不是树形）
❌ f(n) 与 n^p 差距不够大：T(n) = 2T(n/2) + n/logn（卡在两种情况边界）

主定理应用速查

算法	递推式	p	f(n)	情况	结论
归并排序	2T(n/2)+n	1	n=Θ(n¹)	2(k=0)	Θ(nlogn)
二分查找	T(n/2)+1	0	1=Θ(n⁰)	2(k=0)	Θ(logn)
Strassen	7T(n/2)+n²	2.81	n²<n^2.81	1	Θ(n^2.81)
三路归并	3T(n/3)+n	1	n=Θ(n¹)	2(k=0)	Θ(nlogn)
4叉树建堆	4T(n/4)+n	1	n=Θ(n¹)	2(k=0)	Θ(nlogn)

摊还分析：均摊而非单次最坏

为什么需要摊还分析

有些数据结构操作代价极不均匀：大多数操作很快，偶尔一次很慢。如果只看最坏单次，会严重高估总体性能。

错误分析：

动态数组 append n 次
最坏单次 = O(n)（触发扩容时复制所有元素）
→ n 次操作 = O(n²)？

实际是 O(n)，差了一个 logn。摊还分析告诉你真正的均摊代价。

聚合法：直接数总代价

思路：算清 n 次操作的总代价上界，再除以 n。

例：动态数组 append n 次

扩容发生在 size = 1, 2, 4, 8, ..., 2^k 时，每次复制代价分别为 1, 2, 4, ..., n/2：

总扩容代价 = 1 + 2 + 4 + ... + n/2 = n - 1 < n
总 append 代价（不含扩容）= n

总代价 < 2n
均摊代价 = 2n/n = O(1) ✅

例：栈的 MULTIPOP 操作序列

操作序列：若干次 PUSH / POP / MULTIPOP(k)，分析 n 次操作的总代价：

关键观察：每个元素最多被 PUSH 一次、POP（或 MULTIPOP 弹出）一次
→ 所有 POP 类操作的总代价 ≤ PUSH 次数 ≤ n
→ 总代价 ≤ 2n
均摊代价 = O(1)/次 ✅

记账法：预存信用

思路：给每次操作预存一定"信用"，实际代价高时从信用中支取。关键：信用余额始终 ≥ 0。

例：动态数组 append

设计信用分配：每次 append 收取 3 个单位代价（摊还代价 = 3）：

• 1 个单位：支付本次 append 的实际代价
• 2 个单位：存入"信用账户"，专为未来扩容准备

验证信用不透支：

扩容前，数组已满，size = capacity = m
信用账户中存了多少？
  从上次扩容（size=m/2）到现在，共 append 了 m/2 次
  每次存入 2 个单位
  信用余额 = 2 × (m/2) = m 个单位

扩容时需要复制 m 个元素，代价 = m
信用账户恰好够支付 ✅，信用余额不会为负

势能法：最严格的工具

思路：定义势能函数 Φ（反映数据结构"蓄积的潜力"），摊还代价 = 实际代价 + ΔΦ。

设计原则：

• 操作便宜时，Φ 增大（蓄积势能）
• 操作昂贵时，Φ 大幅减小（释放势能抵消代价）
• 必须保证 Φ ≥ Φ₀（初始势能），否则摊还代价可能为负

例：动态数组，令 Φ = 2·size - capacity

验证势能函数合法性：

初始（size=0, capacity=1）：Φ = 2×0 - 1 = -1
但初始后第一次 append：size=1, cap=1，Φ = 2×1 - 1 = 1
为了统一，设 Φ₀ = 0，只要 Φ ≥ 0 时才开始计

Case 1：不触发扩容（size < capacity）

实际代价 = 1
ΔΦ = (2(size+1) - cap) - (2·size - cap) = 2
摊还代价 = 1 + 2 = 3

Case 2：触发扩容（size = capacity = m）

实际代价 = m + 1（复制 m 个 + 新 append）
扩容后：size = m+1，capacity = 2m
ΔΦ = (2(m+1) - 2m) - (2m - m) = 2 - m
摊还代价 = (m+1) + (2-m) = 3

两种情况摊还代价都是 3 = O(1) ✅

三种方法的选用：

• 聚合法：最直接，但需要能算出精确总代价
• 记账法：直觉好，适合"预付费"场景
• 势能法：最通用，适合复杂数据结构（斐波那契堆、伸展树）

下界分析：证明算法已最优

上面都是分析算法有多快（上界）。有时候需要证明没有任何算法能做得更好（下界）。

比较排序的 Ω(nlogn) 下界

问题：为什么所有基于比较的排序算法都至少需要 Ω(nlogn) 次比较？

证明工具：决策树

任何比较排序算法可以表示为一棵二叉决策树：

• 每个内部节点：aᵢ ≤ aⱼ?（一次比较）
• 每条从根到叶的路径：一种排序执行过程
• 每个叶节点：一种排列结果（n! 种可能）

graph TD
    A["a₁ ≤ a₂?"] -->|是| B["a₂ ≤ a₃?"]
    A -->|否| C["a₁ ≤ a₃?"]
    B -->|是| D["a₁,a₂,a₃"]
    B -->|否| E["a₁ ≤ a₃?"]
    C -->|是| F["a₂,a₁,a₃"]
    C -->|否| G["..."]
    E -->|是| H["a₁,a₃,a₂"]
    E -->|否| I["a₃,a₁,a₂"]

推导：

叶节点数 ≥ n!（必须覆盖所有 n! 种排列）
二叉树高度 h 满足：2^h ≥ n!

两边取对数：
h ≥ log₂(n!)

Stirling 近似：log₂(n!) ≈ nlog₂n - n/ln2 = Ω(nlogn)

因此任意比较排序的最坏比较次数 h = Ω(nlogn)

推论：归并排序和堆排序的 Θ(nlogn) 在渐近意义上已经最优。计数排序、基数排序之所以能突破 nlogn，是因为它们不是基于比较——利用了元素的数值结构。

常见算法复杂度速查

排序算法

算法	平均	最坏	最好	空间	稳定	下界最优？
冒泡	Θ(n²)	Θ(n²)	Θ(n)	O(1)	✅	❌
插入	Θ(n²)	Θ(n²)	Θ(n)	O(1)	✅	❌（但小数组最快）
归并	Θ(nlogn)	Θ(nlogn)	Θ(nlogn)	O(n)	✅	✅
快速	Θ(nlogn)	Θ(n²)	Θ(nlogn)	O(logn)	❌	✅（期望）
堆排	Θ(nlogn)	Θ(nlogn)	Θ(nlogn)	O(1)	❌	✅
计数	Θ(n+k)	Θ(n+k)	Θ(n+k)	O(k)	✅	N/A（非比较）
基数	Θ(d(n+k))	Θ(d(n+k))	—	O(n+k)	✅	N/A（非比较）

数据结构操作

结构	查找	插入	删除	特殊操作	推导来源
数组	O(n)	O(n)	O(n)	随机访问 O(1)	线性扫描
链表	O(n)	O(1)*	O(1)*	—	*已知位置
哈希表	O(1) avg	O(1) avg	O(1) avg	—	均匀分布假设
二叉堆	O(n)	O(logn)	O(logn)	取最值 O(1)	树高 logn
BST	O(h)	O(h)	O(h)	—	h≤logn 均衡时
红黑树	O(logn)	O(logn)	O(logn)	—	黑高保证
并查集	O(α(n))	O(α(n))	—	—	路径压缩+按秩

图算法

算法	时间	空间	推导关键点
BFS/DFS	O(V+E)	O(V)	每条边访问 2 次
Dijkstra（堆）	O((V+E)logV)	O(V)	每次 extract-min O(logV)，共 V 次
Bellman-Ford	O(VE)	O(V)	松弛 V-1 轮，每轮 O(E)
Floyd-Warshall	O(V³)	O(V²)	三重循环，DP
Kruskal	O(ElogE)	O(V)	排序 O(ElogE)，并查集 O(Eα(V))
拓扑排序	O(V+E)	O(V)	本质是 BFS/DFS

参考资料

• 《算法导论》（CLRS）第 3 版 — 第 3、4、8.1、17 章
• 《算法》（Sedgewick）— 第 1 章分析框架
• 基础数据结构（红黑树黑高如何保证 O(logn)、并查集 α(n) 的来源）
• 并查集（O(α(n)) 的来由、路径压缩和按大小合并）
• 分治与贪心（主定理在归并排序、Strassen 中的完整推导）