经典算法专栏 #07：分治与贪心

分治和贪心是两种截然不同的设计哲学：分治信任递归——把问题拆小、解决、合并；贪心信任局部——每步做最优选择、不回头。本文不止给代码，重点讲清为什么这样做是对的。对应《算法导论》第 4、5、16 章。

目录

分治思想

三步框架

分解（Divide）  ：将原问题拆分为若干规模更小的同类子问题
解决（Conquer） ：递归解决子问题（规模足够小时直接求解）
合并（Combine） ：将子问题的解合并为原问题的解

核心直觉：为什么拆分能提速

问题：对 n 个元素排序，暴力两两比较是 O(n²)，分治为何能到 O(nlogn)？

关键在于合并两个已排序数组只需 O(n)，而不是重新排序的 O(n²)：

暴力排序 [8,3,1,5,2,7,4,6]：
  任意两元素都可能比较 → O(n²) 次比较

分治排序：
  左半 [8,3,1,5] 排好 → [1,3,5,8]
  右半 [2,7,4,6] 排好 → [2,4,6,7]
  合并两个有序数组：只需线性扫描 → O(n)
  两个子问题各是原来的一半 → 递推 T(n) = 2T(n/2) + n → Θ(nlogn)

本质：分治利用了"已有的结构（子数组已排序）来减少合并时的比较次数"。这是分治比暴力快的根本原因——不是递归本身，而是递归后合并时信息量的减少。

适用条件

归并排序：分治的教科书

完整例题：排序 [38, 27, 43, 3, 9, 82, 10]

graph TD
    A["[38,27,43,3,9,82,10]"] --> B["[38,27,43,3]"]
    A --> C["[9,82,10]"]
    B --> D["[38,27]"]
    B --> E["[43,3]"]
    C --> F["[9,82]"]
    C --> G["[10]"]
    D --> D1["[38]"]
    D --> D2["[27]"]
    E --> E1["[43]"]
    E --> E2["[3]"]
    F --> F1["[9]"]
    F --> F2["[82]"]

    D1 & D2 --> DM["合并→[27,38]"]
    E1 & E2 --> EM["合并→[3,43]"]
    F1 & F2 --> FM["合并→[9,82]"]
    DM & EM --> BM["合并→[3,27,38,43]"]
    FM & G --> CM["合并→[9,10,82]"]
    BM & CM --> AM["合并→[3,9,10,27,38,43,82]"]

合并步骤详解（以最后一步 [3,27,38,43] + [9,10,82]）：

左指针 i=0, 右指针 j=0, 结果数组 res=[]

比较 3 vs 9  → 取 3, i=1,  res=[3]
比较 27 vs 9 → 取 9, j=1,  res=[3,9]
比较 27 vs 10→ 取 10, j=2, res=[3,9,10]
比较 27 vs 82→ 取 27, i=2, res=[3,9,10,27]
比较 38 vs 82→ 取 38, i=3, res=[3,9,10,27,38]
比较 43 vs 82→ 取 43, i=4, res=[3,9,10,27,38,43]
左指针耗尽，追加右侧剩余 [82]
res=[3,9,10,27,38,43,82] ✅

void mergeSort(int[] a, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;       // 防溢出写法，等价于 (l+r)/2
    mergeSort(a, l, mid);
    mergeSort(a, mid + 1, r);
    merge(a, l, mid, r);
}

void merge(int[] a, int l, int mid, int r) {
    int[] tmp = Arrays.copyOfRange(a, l, r + 1);
    int i = 0, j = mid - l + 1, k = l;
    while (i <= mid - l && j <= r - l)
        a[k++] = tmp[i] <= tmp[j] ? tmp[i++] : tmp[j++];  // <= 保证稳定性
    while (i <= mid - l) a[k++] = tmp[i++];
    while (j <= r - l)   a[k++] = tmp[j++];
}
// T(n) = 2T(n/2) + n → Θ(nlogn)，空间 O(n)，稳定排序

扩展：用归并排序统计逆序对

逆序对：数组中满足 i < j 但 a[i] > a[j] 的下标对 (i,j)。统计逆序对数是衡量数组"无序程度"的指标。

暴力法：两重循环，O(n²)。

分治优化：在 merge 阶段统计——当右半部分的元素 a[j] 被选入结果（因为 a[j] < a[i]），此时左半部分 i 到 mid 的所有剩余元素都构成逆序对：

long mergeCount(int[] a, int l, int r) {
    if (l >= r) return 0;
    int mid = l + (r - l) / 2;
    long count = mergeCount(a, l, mid) + mergeCount(a, mid + 1, r);
    // 在 merge 中额外统计跨越中点的逆序对
    int[] tmp = Arrays.copyOfRange(a, l, r + 1);
    int i = 0, j = mid - l + 1, k = l;
    while (i <= mid - l && j <= r - l) {
        if (tmp[i] <= tmp[j]) {
            a[k++] = tmp[i++];
        } else {
            // tmp[i..mid-l] 都大于 tmp[j]，共 (mid-l-i+1) 个逆序对
            count += (mid - l - i + 1);
            a[k++] = tmp[j++];
        }
    }
    while (i <= mid - l) a[k++] = tmp[i++];
    while (j <= r - l)   a[k++] = tmp[j++];
    return count;
}
// 总时间 Θ(nlogn)，逆序对统计"免费"附带在排序过程中

思路精髓：分治不仅排序，顺手把"跨越中点的逆序对"数出来——这是分治思想的典型扩展：在合并阶段提取额外信息。

快速幂：指数折半的威力

从 O(n) 到 O(logn)

朴素计算 x^n：连乘 n 次，O(n)。

分治思路：

x^n = x^(n/2) · x^(n/2)           若 n 是偶数
x^n = x^(n/2) · x^(n/2) · x      若 n 是奇数

T(n) = T(n/2) + O(1) → Θ(logn)

迭代版（实际工程用这个，无递归栈开销）：

long quickPow(long x, long n, long mod) {
    long result = 1;
    x %= mod;
    while (n > 0) {
        if ((n & 1) == 1)          // n 的二进制最低位是 1
            result = result * x % mod;
        x = x * x % mod;           // x → x², x⁴, x⁸...
        n >>= 1;                    // n 右移，逐位处理
    }
    return result;
}

完整例题：计算 3^13 mod 1000

n=13 = 1101₂（二进制）

初始：result=1, x=3

轮1: n=13（奇）→ result=1×3=3,   x=3²=9,   n=6
轮2: n=6（偶） → result=3,       x=9²=81,  n=3
轮3: n=3（奇） → result=3×81=243, x=81²=561, n=1
                （81² = 6561, 6561 mod 1000 = 561）
轮4: n=1（奇） → result=243×561=627, x=561²=..., n=0
                （243×561 = 136323, 136323 mod 1000 = 323）

答案：3^13 mod 1000 = 323 ✅
验证：3^13 = 1594323, 1594323 mod 1000 = 323 ✅

矩阵快速幂：线性递推的利器

斐波那契数列 F(n) 通项可用矩阵快速幂 O(logn) 求解：

[F(n+1)]   [1 1]^n   [F(1)]
[F(n)  ] = [1 0]   × [F(0)]

只需对矩阵 [[1,1],[1,0]] 做 n 次方，
用矩阵快速幂：O(2³ × logn) = O(logn)
vs 迭代递推：O(n)

当 n = 10^18 时，迭代递推需要 10^18 步，矩阵快速幂只需 约 60 步。

Strassen 矩阵乘法

为什么 7 次比 8 次快得多

普通 2×2 矩阵乘法：8 次乘法、4 次加法。

Strassen 用 7 次乘法、18 次加减法替代：

定义 7 个辅助矩阵（每个只需 1 次子矩阵乘法）：
M₁ = (A₁₁ + A₂₂)(B₁₁ + B₂₂)
M₂ = (A₂₁ + A₂₂)B₁₁
M₃ = A₁₁(B₁₂ - B₂₂)
M₄ = A₂₂(B₂₁ - B₁₁)
M₅ = (A₁₁ + A₁₂)B₂₂
M₆ = (A₂₁ - A₁₁)(B₁₁ + B₁₂)
M₇ = (A₁₂ - A₂₂)(B₂₁ + B₂₂)

C₁₁ = M₁ + M₄ - M₅ + M₇
C₁₂ = M₃ + M₅
C₂₁ = M₂ + M₄
C₂₂ = M₁ - M₂ + M₃ + M₆

复杂度递推：T(n) = 7T(n/2) + O(n²)

p = log₂7 ≈ 2.807
f(n) = n² = O(n^(2.807 - 0.807))  → 情况 1
T(n) = Θ(n^log₂7) ≈ Θ(n^2.807)
对比普通 O(n³)，当 n=1000：n^2.807 ≈ 200,000 vs n³ = 10^9

工程现实：Strassen 在 n < 几百时因常数项（18 次加法）反而更慢；现代 BLAS 库在大矩阵时确实应用类似思想，但还结合了 cache 局部性优化。

贪心思想

贪心选择性质

贪心选择性质：问题的全局最优解，可以通过一系列局部最优选择来构建——当前的贪心选择必定出现在某个全局最优解中。

这个性质不是显然的，必须严格证明，否则贪心可能是错的。

反例：背包问题

物品 A（重 10kg，价值 60）、B（重 6kg，价值 40）、C（重 4kg，价值 30），背包容量 10kg。

贪心策略"优先选单位重量价值最高的物品"：

• A：6/kg，B：6.67/kg，C：7.5/kg
• 贪心选 C（30）再选 B（40），总价值 70
• 最优解：选 A，价值 60
• 贪心选 C+B = 70 > 60，这次贪心对了

但若容量改为 8kg：

• 贪心选 C（4kg，30）再选 B（6kg，但只剩 4kg 放不下），选 A 也放不下
• 贪心得到 30，而最优是选 C+B = 70
• 0/1 背包的贪心策略是错的，必须用 DP

分数背包可以贪心（物品可分割），0/1 背包不行——这就是贪心选择性质需要严格验证的原因。

两种证明方法

① 交换论证（Exchange Argument）

假设存在某个最优解 OPT 不包含贪心的第一个选择 g，证明可以把 OPT 中对应的元素换成 g，得到的解不比 OPT 差。

② 贪心领先（Greedy Stays Ahead）

证明贪心算法在每个阶段都不劣于任意其他算法的对应阶段，从而整体不劣于最优解。

活动选择：贪心的经典证明

问题定义

n 个活动，活动 i 的时间段为 [sᵢ, fᵢ)。两个活动兼容当且仅当时间不重叠（fᵢ ≤ sⱼ 或 fⱼ ≤ sᵢ）。求最大兼容活动子集的大小。

贪心策略

每次选结束时间最早的、与已选活动兼容的活动。

完整例题

按结束时间排序：a₁(4), a₂(5), a₃(6), a₄(7), a₅(9), a₆(9), a₇(10), a₈(11), a₉(12), a₁₀(14)

贪心执行：

选 a₁（结束=4），lastFinish=4
a₂ 开始=3 < 4，冲突，跳过
a₃ 开始=0 < 4，冲突，跳过
选 a₄（开始=5 ≥ 4），lastFinish=7
a₅ 开始=3 < 7，跳过
a₆ 开始=5 < 7，跳过
选 a₇（开始=6 < 7），跳过
选 a₈（开始=8 ≥ 7），lastFinish=11

结果：{a₁, a₄, a₈}，共 3 个活动 ✅

int activitySelection(int[] s, int[] f) {
    // 假设已按结束时间排序
    int count = 1, lastFinish = f[0];
    for (int i = 1; i < s.length; i++) {
        if (s[i] >= lastFinish) {
            count++;
            lastFinish = f[i];
        }
    }
    return count;
}
// O(nlogn)（含排序），空间 O(1)

正确性证明（交换论证）

命题：贪心算法产生的解是最优解。

证明：

设贪心选出的活动序列为 G = {g₁, g₂, ..., gₖ}（按开始时间序），其中 g₁ 是结束时间最早的活动。

设 A = {a₁, a₂, ..., aₘ} 是任意最优解（m ≥ k），同样按开始时间序。

第一步：证明可以将 A 中的 a₁ 替换为 g₁ 而不减少活动数：

由贪心策略，f(g₁) ≤ f(a₁)（g₁ 是结束最早的）

构造 A' = (A - {a₁}) ∪ {g₁}：
  g₁ 结束更早，g₁ 与 a₂ 兼容（因为 a₁ 与 a₂ 兼容，f(a₁) ≤ s(a₂)，
  而 f(g₁) ≤ f(a₁) ≤ s(a₂)）
  因此 A' 也是兼容的活动集合，|A'| = |A| = m

第二步：对子问题 [f(g₁), ∞) 内的活动重复上述论证。

归纳结论：贪心算法选出的每个活动，都可以出现在某个最优解中，因此最终贪心解的大小 = 最优解大小。∎

Huffman 编码：贪心构造最优前缀树

问题定义

给定字符集 C = {c₁,...,cₙ}，各字符出现频率 f(cᵢ)，构造一棵前缀编码树（叶节点是字符，编码是根到叶的路径），使总编码长度 B(T) = Σ f(cᵢ)·d(cᵢ) 最小，其中 d(cᵢ) 是字符 cᵢ 的编码长度（树中深度）。

手动构建过程

字符频率：a=45, b=13, c=12, d=16, e=9, f=5

步骤一：初始化最小堆，每个字符是一个叶节点：

堆（按频率排序）：f=5, e=9, c=12, b=13, d=16, a=45

步骤二：反复取出两个最小节点，合并为新节点（频率=两者之和）：

graph TD
    subgraph 第1次合并
        N1["14"] --> f1["f:5"]
        N1 --> e1["e:9"]
    end
    subgraph 第2次合并
        N2["25"] --> c2["c:12"]
        N2 --> b2["b:13"]
    end
    subgraph 第3次合并
        N3["30"] --> d3["d:16"]
        N3 --> N1b["14"]
    end
    subgraph 第4次合并
        N4["55"] --> N2b["25"]
        N4 --> N3b["30"]
    end
    subgraph 最终树
        ROOT["100"] --> a_f["a:45"]
        ROOT --> N4c["55"]
        N4c --> N2c["25"]
        N4c --> N3c["30"]
        N2c --> c_f["c:12"]
        N2c --> b_f["b:13"]
        N3c --> d_f["d:16"]
        N3c --> N1c["14"]
        N1c --> f_f["f:5"]
        N1c --> e_f["e:9"]
    end

编码结果（左=0，右=1）：

总编码长度 = 45+36+39+48+20+36 = 224 bits

定长编码（3 位）总长 = 100 × 3 = 300 bits → Huffman 节省 25%。

正确性直觉：最低频字符一定在最深处

引理 1：在任意最优编码树中，频率最低的两个字符，编码长度是最长的（在树中最深），且它们是兄弟节点。

证明思路（反证）：

设 x,y 是频率最低的两个字符，假设最优树 T 中 x 不在最深处，
而最深处是字符 z（f(z) ≥ f(x)）。

交换 x 和 z 的位置，得到新树 T'：
  B(T) - B(T') = f(x)·d_T(x) + f(z)·d_T(z)
               - f(x)·d_T(z) - f(z)·d_T(x)
               = (f(z) - f(x))·(d_T(z) - d_T(x))
               ≥ 0  （因为 f(z)≥f(x)，d_T(z)≥d_T(x)）

所以 B(T') ≤ B(T)，T' 不比 T 差
→ 存在 x 在最深处的最优解 ✅

HuffmanNode buildHuffman(int[] freq, char[] chars) {
    PriorityQueue<HuffmanNode> pq =
        new PriorityQueue<>(Comparator.comparingInt(n -> n.freq));
    for (int i = 0; i < freq.length; i++)
        pq.offer(new HuffmanNode(chars[i], freq[i]));

    while (pq.size() > 1) {
        HuffmanNode left  = pq.poll();   // 最小频率
        HuffmanNode right = pq.poll();   // 次小频率
        HuffmanNode merge = new HuffmanNode('\0', left.freq + right.freq);
        merge.left  = left;
        merge.right = right;
        pq.offer(merge);
    }
    return pq.poll();
}
// 时间 O(nlogn)：每次 poll/offer O(logn)，共 2n-1 次

贪心在图算法中的体现

Dijkstra 的贪心本质

Dijkstra 维护一个集合 S（已确定最短路的节点）：

贪心选择：每次从 V-S 中选择当前 dist 最小的节点 u 加入 S。

贪心选择性质的证明（反证）：假设选出 u 时 dist[u] 不是最短路。则存在一条路径经过 V-S 中某个节点 v（dist[v] > dist[u]）先到达 u——但这条路径经过 v 时已 ≥ dist[v] > dist[u]，矛盾。

限制：Dijkstra 要求非负边权——若存在负权边，贪心选择性质不成立（选出的"当前最短"可能因负权被更新）。

Prim 和 Kruskal 的贪心本质

Prim：每步选择连接生成树与剩余节点的最小权边——贪心选择性质由"切割性质"保证：对任意将图切割为两部分的切割，切割中权最小的边一定在某棵 MST 中。

Kruskal：按边权从小到大加入不成环的边——同样由切割性质保证正确性。

三范式对比与选型

flowchart TD
    A["问题有最优子结构？"] -->|否| B["暴力枚举 / 其他"]
    A -->|是| C{"子问题是否大量重叠？"}
    C -->|否，子问题独立| D["分治<br/>归并排序、快速幂、Strassen"]
    C -->|是| E{"是否满足贪心选择性质？<br/>（需严格证明）"}
    E -->|是| F["贪心<br/>活动选择、Huffman、Dijkstra"]
    E -->|否| G["动态规划<br/>背包、LCS、编辑距离"]

    style D fill:#dae8fc,stroke:#6c8ebf
    style F fill:#d5e8d4,stroke:#82b366
    style G fill:#fff2cc,stroke:#d6b656
    style B fill:#f8cecc,stroke:#b85450

最容易犯的错：看到求"最大/最小"就用贪心，不验证贪心选择性质。0/1 背包、硬币找零（非标准面值）、最长递增子序列——这些看起来像贪心，但必须用 DP。

参考资料

• 《算法导论》（CLRS）第 3 版 — 第 2、4、16 章
• 《算法设计》— Kleinberg & Tardos，第 4 章贪心、第 5 章分治
• 算法复杂度分析（主定理对分治递推式的完整推导）
• 动态规划（贪心 vs DP 的边界：0/1 背包为何不能贪心）
• 基础数据结构（Huffman 树中最小堆的 O(logn) 操作支撑）