第3章：决策树（Decision Trees）
一、导读
1.1 本章学习目标
第3章探讨决策树这一基本计算模型。决策树是分析算法下界的核心工具——通过证明任何算法都对应一棵决策树，然后用信息论方法计算决策树的最小深度，就能得到算法复杂度的下界。
本章核心学习目标：
- 理解决策树模型：算法的每次比较对应树的一个内部节点
- 掌握信息论下界：log₂(n!) 次比较是排序的下界
- 理解比较排序的最优算法：归并排序和堆排序达到 O(n log n)
- 学会用决策树分析搜索算法：二分搜索的最优性证明
1.2 为什么本章如此重要
决策树提供了分析算法下界的通用方法。当你想知道"这个问题最快能有多快"时，决策树和信息论就是答案。
1.3 核心问题引导
为什么基于比较的排序算法至少需要 Ω(n log n) 次比较？
信息论如何给出算法复杂度的下界？
决策树模型有什么局限性？
二、核心概念详解
2.1 决策树模型
决策树:
- 每个内部节点代表一次比较（如 aᵢ : aⱼ）
- 每个分支代表比较的结果（<, =, >）
- 每个叶节点代表一个输出（算法的结果）
示例: 在 3 个数中找最大值
a:b
/ | \
< = >
/ | \
b:c a:c a:c
/ \ / \ / \
< > < > < >
c b a c b a
b c b a c
决策树深度 = 最坏情况比较次数 = 22.2 排序的下界
定理: 任何基于比较的排序算法在最坏情况下至少需要 ⌈log₂(n!)⌉ 次比较
证明:
1. n 个元素有 n! 种排列
2. 排序算法必须区分所有 n! 种排列
3. 决策树的叶节点数 ≥ n!
4. 二叉树深度 d 的叶节点数 ≤ 2ᵈ
5. 所以 2ᵈ ≥ n! → d ≥ log₂(n!)
Stirling 近似:
log₂(n!) = n log₂ n - n log₂ e + O(log n)
= n log₂ n - 1.443n + O(log n)
≈ Θ(n log n)
具体值:
n=3: log₂(6) = 2.58 → 至少 3 次比较
n=5: log₂(120) = 6.91 → 至少 7 次比较
n=10: log₂(3628800) = 21.79 → 至少 22 次比较
n=100: log₂(100!) ≈ 525 → 至少 525 次比较2.3 最优排序算法
归并排序:
- 最坏情况: n⌈log₂ n⌉ - 2^(⌈log₂ n⌉) + 1 次比较
- 接近下界 n log₂ n
堆排序:
- 最坏情况: 2n log₂ n 次比较
- 常数因子比归并排序大
Ford-Johnson 算法 (1959):
- 平均情况: n log₂ n - 1.414n 次比较
- 非常接近理论下界
- 但实际中很少使用（复杂度高，常数大）三、实战案例
3.1 案例一：5 个元素排序的最优决策树
5 个元素排序:
理论下界: ⌈log₂(120)⌉ = 7 次比较
Knuth 给出的最优算法:
Step 1: 比较 a:b → 假设 a < b
Step 2: 比较 c:d → 假设 c < d
Step 3: 比较 a:c → 假设 a < c (现在 a 是最小的候选)
Step 4: 比较 b:e
Step 5: 比较 b:d (或 c:e，取决于 Step 4 的结果)
...
总共 7 次比较即可完成排序
（恰好达到理论下界）四、本章小结
决策树是分析算法下界的基本工具
排序下界为 Ω(n log n)，由信息论给出
归并排序在实际中接近最优
五、思考与练习
思考题
非比较排序（如计数排序）为什么能突破 O(n log n) 下界？
决策树模型能否用于分析非比较操作（如加法、移位）？
编程练习
为 4 个元素排序设计一棵最优决策树（5 次比较）。
实现归并排序，统计实际比较次数并与理论下界对比。