第15章 贪心算法 — 章节汇总
章节概览
本章系统介绍贪心算法（Greedy Algorithms）——一种通过一系列局部最优选择来构造全局最优解的算法设计范式。与动态规划不同，贪心算法在每个决策点做出当前看来最好的选择，而不需要先求解子问题。本章通过4个经典问题（活动选择、贪心策略要素、哈夫曼编码、离线缓存）逐步展示贪心算法的设计方法学和正确性证明技术。
15.1 活动选择问题
| 小节 | 核心主题 | 关键结论 |
|---|---|---|
| 15.1 活动选择问题 | 区间调度、贪心选择最早结束 | （已排序） |
核心思路：从动态规划的视角出发（ 子问题、 递推），发现只需考虑一个选择——选择最早结束的活动 。Theorem 15.1 证明贪心选择总是安全的。递归算法 RECURSIVE-ACTIVITY-SELECTOR 可转化为迭代算法 GREEDY-ACTIVITY-SELECTOR，时间 。
15.2 贪心策略要素
| 小节 | 核心主题 | 关键结论 |
|---|---|---|
| 15.2 贪心策略要素 | 贪心选择性质、最优子结构、贪心 vs DP | 方法论 |
核心思路：贪心算法的两个关键性质——贪心选择性质（局部最优→全局最优）和最优子结构（与DP共享）。贪心与DP的本质区别：贪心先选择后求解（自顶向下），DP先求解后选择（自底向上）。0-1 背包 vs 分数背包的对比揭示何时贪心适用、何时必须用DP。
15.3 哈夫曼编码
| 小节 | 核心主题 | 关键结论 |
|---|---|---|
| 15.3 哈夫曼编码 | 最优前缀码、最小优先队列 |
核心思路：利用贪心策略构造最优前缀码。每次合并频率最低的两个字符/子树，用最小优先队列实现。Lemma 15.2（贪心选择性质，交换论证）和 Lemma 15.3（最优子结构，反证法）保证正确性。编码代价 。
15.4 离线缓存
| 小节 | 核心主题 | 关键结论 |
|---|---|---|
| 15.4 离线缓存 | furthest-in-future 策略、缓存替换 | 最优离线策略 |
核心思路：在已知完整请求序列的前提下，最小化缓存未命中次数。furthest-in-future 策略驱逐下次使用最远的块。Theorem 15.5 通过复杂的归纳证明（四性质构造法）证明其最优性。该策略由 Belady 于1966年提出，是在线缓存算法的竞争比基准。
本章核心知识点
贪心算法复杂度汇总
| 问题 | 贪心选择 | 时间复杂度 | 数据结构 |
|---|---|---|---|
| 活动选择 | 最早结束的活动 | （已排序） | 数组 |
| 哈夫曼编码 | 频率最低的两个节点 | 最小优先队列 | |
| 离线缓存 | 下次使用最远的块 | （朴素） | — |
| 分数背包 | 单位价值最高的物品 | （排序） | 排序 |
贪心 vs 动态规划
| 特性 | 贪心算法 | 动态规划 |
|---|---|---|
| 求解顺序 | 先选择，后求解（自顶向下） | 先求解，后选择（自底向上） |
| 子问题依赖 | 不依赖子问题的解 | 依赖子问题的解 |
| 选择数量 | 每步只考虑一个选择 | 考虑所有可能的选择 |
| 适用条件 | 贪心选择性质 + 最优子结构 | 最优子结构 + 重叠子问题 |
| 典型问题 | 活动选择、Huffman、MST | LCS、矩阵链乘法、背包 |
贪心正确性证明技术
| 证明方法 | 适用场景 | 本章实例 |
|---|---|---|
| 替换论证（Exchange Argument） | 证明贪心选择是最优解的一部分 | Theorem 15.1、Lemma 15.2 |
| 反证法 | 证明最优子结构 | Lemma 15.3 |
| 归纳法（四性质构造） | 复杂策略的正确性 | Theorem 15.5 |
| 剪切-粘贴（Cut-and-Paste） | 证明最优子结构 | 15.1节最优子结构 |
与前序章节的知识关联
| 前序章节 | 关联方式 |
|---|---|
| 第14章 动态规划 | 贪心与DP共享最优子结构，但贪心额外需要贪心选择性质；15.1从DP视角引入贪心 |
| 第6章 堆排序 | Huffman算法使用最小优先队列（6.5节），BUILD-MIN-HEAP初始化 |
| 第11章 散列表 | 散列表的缓存行为是离线缓存问题的实际背景 |
| 第12章 BST | Huffman编码树是二叉树（但非BST），满二叉树性质 |
学习路线
第15章学习路径：
15.1 活动选择问题（DP视角→贪心选择→Theorem 15.1→递归→迭代→Θ(n)）
→ 15.2 贪心策略要素（贪心选择性质→最优子结构→贪心vs DP→0-1背包vs分数背包→6步设计法）
→ 15.3 哈夫曼编码（前缀码→编码代价→HUFFMAN算法→Lemma 15.2/15.3→Theorem 15.4→O(n lg n)）
→ 15.4 离线缓存（缓存模型→furthest-in-future→最优子结构→Theorem 15.5→LRU对比）
学习建议
本章是算法设计部分的第二个核心范式（继第14章DP之后）。15.1 是贪心的入门，重点理解”从DP到贪心的思维转换”——为什么只需要考虑一个选择。15.2 是方法论总结，重点掌握贪心选择性质的”替换论证”证明技术和0-1背包 vs 分数背包的对比。15.3 Huffman编码是贪心的经典应用，重点理解交换论证（Lemma 15.2）和反证法（Lemma 15.3）。15.4 离线缓存的Theorem 15.5证明较为复杂，建议先理解策略直觉，再逐步消化归纳证明。学完本章后，回顾第14章，对比DP和贪心在适用条件和设计方法上的异同。