第 4 章分治策略 (Divide-and-Conquer)

核心结论

分治范式 (Divide-and-Conquer)：把问题分解为同类但更小的子问题（Divide）、递归求解（Conquer）、合并子问题的解（Combine）。本章给出三个分治算法：最大子数组、矩阵乘法（朴素 + Strassen）。
最大子数组问题 (Maximum Subarray)：找数组中和最大的连续子数组；暴力 Θ(n²)；分治 Θ(n lg n)（FIND-MAX-CROSSING-SUBARRAY + 递归）。
Strassen 矩阵乘法：把 2×2 矩阵乘法的 8 次乘法降到 7 次，递归展开后得 Θ(n^lg 7) ≈ Θ(n^2.81)，打破「矩阵乘法必 Θ(n³)」的下界。
递归式三种解法：代入法（猜 + 归纳）、递归树法（画树逐层求和）、主定理（cookbook 公式）。代入法严格、递归树直观、主定理快速。
主定理 (Master Theorem)：对 \(T(n) = aT(n/b) + f(n)\)，比较 \(f(n)\) 与 \(n^{\log_b a}\)：\(f\) 多项式小 → Θ(n^log_b a)；同阶 → Θ(n^log_b a lg n)；多项式大且规则 → Θ(f(n))。

本章主旨

本章深化第 2 章的「分治思想」：用最大子数组（线性合并 + 递归）和矩阵乘法（Strassen 的减乘法策略）展示分治算法的设计；用 4.3–4.5 三节系统解决「如何解递归式」的问题——代入法用于严格证明，递归树用于猜测，主定理用于快速求解。3.2 节给出主定理的完整证明（基于递归树的精确求和）。

一、核心概念

本章围绕 5 个核心概念展开：先看分治的两个具体算法（最大子数组、矩阵乘法），再系统学习递归式的三种解法（代入法、递归树、主定理）。

概念	定义 + 重要性	实现提示
最大子数组 (Maximum Subarray)	在含负数的数组中找和最大的连续子数组；分治解法 Θ(n lg n)，后被第 5 章的线性算法超越。	§4.1；FIND-MAX-CROSSING-SUBARRAY 是合并步骤的关键。
Strassen 矩阵乘法	通过构造 7 个子矩阵乘积把 2×2 矩阵乘法从 8 次乘法降到 7 次；递归展开后 Θ(n^lg 7) ≈ Θ(n^2.81)。	§4.2；是「算法改进能突破表面下界」的范例。
代入法 (Substitution Method)	解递归式的两步法：猜解的形式 → 用数学归纳法验证；要求猜测有依据（可用递归树生成）。	§4.3；难点是「归纳假设不够强」——往往需要减去低阶项。
递归树法 (Recursion-Tree Method)	把递归式展开为树，每层求和得总代价；适合生成「好猜测」，再用代入法验证；主定理证明也基于此。	§4.4；图 4.5 (T(n)=3T(n/4)+Θ(n²)) 与图 4.6 (T(n)=T(n/3)+T(2n/3)+cn) 是典型例子。
主定理 (Master Theorem)	对 \(T(n)=aT(n/b)+f(n)\) 的 cookbook：比较 \(f(n)\) 与「临界指数」 \(n^{\log_b a}\)；分三种情形。	§4.5；\(a\) 子问题、每子问题规模 \(n/b\)、合并代价 \(f(n)\)。

概念

定义 + 重要性

实现提示

最大子数组 (Maximum Subarray)

在含负数的数组中找和最大的连续子数组；分治解法 Θ(n lg n)，后被第 5 章的线性算法超越。

§4.1；FIND-MAX-CROSSING-SUBARRAY 是合并步骤的关键。

Strassen 矩阵乘法

通过构造 7 个子矩阵乘积把 2×2 矩阵乘法从 8 次乘法降到 7 次；递归展开后 Θ(n^lg 7) ≈ Θ(n^2.81)。

§4.2；是「算法改进能突破表面下界」的范例。

代入法 (Substitution Method)

解递归式的两步法：猜解的形式 → 用数学归纳法验证；要求猜测有依据（可用递归树生成）。

§4.3；难点是「归纳假设不够强」——往往需要减去低阶项。

递归树法 (Recursion-Tree Method)

把递归式展开为树，每层求和得总代价；适合生成「好猜测」，再用代入法验证；主定理证明也基于此。

§4.4；图 4.5 (T(n)=3T(n/4)+Θ(n²)) 与图 4.6 (T(n)=T(n/3)+T(2n/3)+cn) 是典型例子。

主定理 (Master Theorem)

对 \(T(n)=aT(n/b)+f(n)\) 的 cookbook：比较 \(f(n)\) 与「临界指数」 \(n^{\log_b a}\)；分三种情形。

§4.5；\(a\) 子问题、每子问题规模 \(n/b\)、合并代价 \(f(n)\)。

二、详细笔记

4.1 最大子数组问题 (Maximum Subarray)

What：给定数组 \(A[1{:}n\)]，找和最大的非空连续子数组 \(A[i {:} j\)]。原问题域是股票价格变化（最大利润）。

Why：暴力枚举所有 Θ(n²) 子数组是 Θ(n³)（或 Θ(n²)，如练习 4.1-2）；分治能降到 Θ(n lg n)，第 5 章将给出更优的 Θ(n) 算法。

How：分治解法（§4.1）——把 \(A[low {:} high\)] 分为两半 \(mid = \lfloor (low+high)/2 \rfloor\)，最大子数组必在以下三种位置之一：

完全在左半 \(A[low {:} mid\)]
完全在右半 \(A[mid+1 {:} high\)]
跨越中点（左右各取一段）

FIND-MAX-CROSSING-SUBARRAY（§4.1）：

\[\begin{array}{rl} 1 & left\text{-}sum = -\infty \\ 2 & sum = 0 \\ 3 & \textbf{for } i = mid \textbf{ downTo } low \\ 4 & \quad sum = sum + A[i] \\ 5 & \quad \textbf{if } sum > left\text{-}sum: left\text{-}sum = sum, max\text{-}left = i \\ 6 & right\text{-}sum = -\infty \\ 7 & sum = 0 \\ 8 & \textbf{for } j = mid+1 \textbf{ to } high \\ 9 & \quad sum = sum + A[j] \\ 10 & \quad \textbf{if } sum > right\text{-}sum: right\text{-}sum = sum, max\text{-}right = j \\ 11 & \textbf{return } (max\text{-}left, max\text{-}right, left\text{-}sum + right\text{-}sum) \end{array}\]

跨中点子数组是「以 mid 结尾的最大子数组」+「以 mid+1 开头的最大子数组」的拼接；两边各自 Θ(n) 扫一遍 → FIND-MAX-CROSSING-SUBARRAY 总 Θ(n)。

整体算法 FIND-MAXIMUM-SUBARRAY 递归：

Divide：计算 mid = ⌊(low+high)/2⌋。
Conquer：递归求左半 (left-low, left-high, left-sum) 和右半 (right-low, right-high, right-sum)。
Combine：调用 FIND-MAX-CROSSING-SUBARRAY 得 cross；返回三者中和最大者。

递归式（式 4.7）：

\[T(n) = 2T(n/2) + \Theta(n)\]

主定理情形 2 → \(T(n) = \Theta(n \lg n)\)。

When：当子问题独立、且合并步骤是线性或多项式代价时；当存在「跨边界」的合并子问题时。

Example：股票价格变化数组（§4.1 图 4.3）的最大子数组 = A[8:11] = ⟨18, 20, -7, 12⟩，和 = 43——最大利润对应「day 7 后买入、day 11 后卖出」。

4.2 Strassen 矩阵乘法

What：计算两个 n × n 矩阵的乘积。朴素算法 Θ(n³)；Strassen 通过减乘法次数降到 Θ(n^lg 7) ≈ Θ(n^2.81)。

Why：矩阵乘法是数值计算、图算法、机器学习的核心操作；哪怕常数因子的改进也有巨大实际价值。Strassen 是分治「减问题数」思路的典范。

How：2×2 情形——朴素需要 8 次标量乘法：

\[\begin{pmatrix} r & s \\ t & u \end{pmatrix} = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} e & g \\ f & h \end{pmatrix} = \begin{pmatrix} ae+bf & ag+bh \\ ce+df & cg+dh \end{pmatrix}\]

Strassen 构造 7 个乘积：

\[\begin{aligned} P_1 &= a \cdot (g - h) \\ P_2 &= (a + b) \cdot h \\ P_3 &= (c + d) \cdot e \\ P_4 &= d \cdot (f - e) \\ P_5 &= (a + d) \cdot (e + h) \\ P_6 &= (b - d) \cdot (f + h) \\ P_7 &= (a - c) \cdot (e + g) \end{aligned}\]

然后：

\[r = P_5 + P_4 - P_2 + P_6, \quad s = P_1 + P_2, \quad t = P_3 + P_4, \quad u = P_5 + P_1 - P_3 - P_7\]

7 次乘法 + 18 次加减法（vs 朴素 8 乘 + 4 加）。n × n 情形：递归划分 4 个 n/2 × n/2 子矩阵 → 递归式：

\[T(n) = 7T(n/2) + \Theta(n^2) \quad \text{(式 4.18)}\]

主定理情形 1（\(f(n) = \Theta(n^2) = O(n^{\log_2 7 - \epsilon})\)，ε ≈ 0.81） → \(T(n) = \Theta(n^{\lg 7}) ≈ \Theta(n^{2.81})\)。

When：当常数因子改进值得复杂的代码（数值库、机器学习）；当实际矩阵规模足够大（如 n ≥ 100）让渐近优势盖过常数因子开销（现代实践中 n < 100 时朴素更优）。

Example：2×2 情形手算（练习 4.2-1）：A = 1,3),(7,5，B = 6,8),(4,2 → 用 Strassen 7 乘积验证得 18, 14), (62, 66。

4.3 代入法 (Substitution Method)

What：解递归式的两步法：(1) 猜解的形式（如 \(T(n) = O(n \lg n)\)）；(2) 用数学归纳法证明该形式对某个常数 \(c > 0\) 成立。

Why：代入法提供严格证明——比递归树法更精确；可用来验证其他方法（递归树、主定理）给出的猜测。

How：基本流程（§4.3）：

步骤	操作
1. 猜解	由经验、相似已知递归、递归树启发
2. 代入	假设对所有 m < n，\(T(m) \leq c \cdot g(m)\)；代入递归式右端
3. 化简	整理得到关于 \(T(n)\) 的不等式，看是否能推出 \(T(n) \leq c g(n)\)
4. 边界	验证归纳基础（边界条件）；若失败，调整常数或选更大的 n₀

步骤

操作

1. 猜解

由经验、相似已知递归、递归树启发

2. 代入

假设对所有 m < n，\(T(m) \leq c \cdot g(m)\)；代入递归式右端

3. 化简

整理得到关于 \(T(n)\) 的不等式，看是否能推出 \(T(n) \leq c g(n)\)

4. 边界

验证归纳基础（边界条件）；若失败，调整常数或选更大的 n₀

关键技巧：

减去低阶项：若 \(T(n) \leq cn\) 假设失败（差一个常数），改为 \(T(n) \leq cn - d\)（d ≥ 0）。
放宽边界条件：用 n₀ 而非 1 作为归纳起点——避免边界条件与渐近形式矛盾。
变量替换：把复杂递归式变为已知形式（如 \(T(n) = 2T(\sqrt n) + \lg n\)，令 m = lg n 得 \(S(m) = 2S(m/2) + m\)）。

When：

当主定理不适用（f(n) 不在任何 case）时。
当需要严格证明时。
当递归式有微小扰动（如 \(\lfloor n/2 \rfloor + 17\)）需要证明解不变时。

Example：证明 \(T(n) = 2T(\lfloor n/2 \rfloor) + n\) = O(n lg n)（§4.3）。假设 \(T(m) \leq cm \lg m\)，代入：

\[T(n) \leq 2c\lfloor n/2 \rfloor \lg(\lfloor n/2 \rfloor) + n \leq cn \lg(n/2) + n = cn \lg n - cn + n \leq cn \lg n\]

最后一步要求 \(c \geq 1\)。边界：选 n₀ = 2, 3 作为归纳基础，c ≥ 2 即可。

4.4 递归树法 (Recursion-Tree Method)

What：把递归式 \(T(n)\) 展开为树形结构——根节点是顶层代价；每个内部节点展开为「子问题代价 + 递归子树」；叶节点是基础情形。

Why：递归树直观——能快速生成「好猜测」；也是主定理证明的核心工具。

How：递归树分析的三个步骤（§4.4）：

画树：每层展开一层递归。
求每层代价：第 i 层有 \(a^i\) 个节点，每个节点代价 \(f(n/b^i)\)，本层总代价 = \(a^i \cdot f(n/b^i)\)。
求总和：累加各层代价 = 总 \(T(n)\)。

两种典型情形：

几何级数主导：当每层代价单调减少（如 \(a f(n/b) < c f(n)\) 对某个 c < 1），总代价被根主导 → Θ(f(n))（主定理情形 3）。
每层代价相同：当每层代价 ≈ 同阶（如 \(a f(n/b) = a (n/b) = (a/b) f(n)\)；当 a = b 时为同阶），总代价 = 层数 × 每层 = Θ(f(n) lg n)（主定理情形 2）。

When：

当主定理不适用，需要理解「为什么」时。
当递归式有多个不同子问题规模（如 \(T(n) = T(n/3) + T(2n/3) + cn\)）时。
当需要生成「好猜测」再由代入法验证时。

Example：图 4.6——\(T(n) = T(n/3) + T(2n/3) + cn\)（§4.4）。树高 ≈ log_{3/2} n；每层代价 ≈ cn；总代价 ≈ cn log_{3/2} n = Θ(n lg n)。

4.5 主定理 (Master Theorem)

What：对形如 \(T(n) = aT(n/b) + f(n)\)（\(a \geq 1, b > 1\)）的递归式，给出 cookbook 式的渐近解。关键比较：\(f(n)\) vs 临界指数 \(n^{\log_b a}\)。

Why：分治算法大量产生这种形式的递归式；主定理让求解从「证明」变成「查表」。

How：三种情形（定理 4.1）：

\[T(n) = aT(n/b) + f(n)\]

情形 1：\(f(n) = O(n^{\log_b a - \epsilon})\) 对某 \(\epsilon > 0\) → \(T(n) = \Theta(n^{\log_b a})\)。「f 多项式小于临界指数」——递归代价主导。
情形 2：\(f(n) = \Theta(n^{\log_b a})\) → \(T(n) = \Theta(n^{\log_b a} \lg n)\)。两者同阶——多一个对数因子。
情形 3：\(f(n) = \Omega(n^{\log_b a + \epsilon})\) 对某 \(\epsilon > 0\)，且 \(a f(n/b) \leq c f(n)\) 对某 c < 1（规则性条件）→ \(T(n) = \Theta(f(n))\)。「f 多项式大于临界指数」——顶层代价主导。

注意：

三种情形之间存在「间隙」——f(n) 与临界指数只差对数因子（如 \(T(n) = 2T(n/2) + n \lg n\)）时主定理无法判定。
情形 3 要求「规则性」：\(f(n/b)\) 不能增长太快。

When：

第一选择——递归式符合 \(aT(n/b) + f(n)\) 形式时。
用于最大子数组、归并排序、Strassen 等分治算法的运行时间分析。

Example：

递归式	a	b	f(n)	情形 / 解
\(T(n) = 9T(n/3) + n\)	9	3	n	1（临界 = n²，f = n）→ Θ(n²)
\(T(n) = T(2n/3) + 1\)	1	3/2	1	2（临界 = 1，f = 1）→ Θ(lg n)
\(T(n) = 3T(n/4) + n \lg n\)	3	4	n lg n	3（临界 ≈ n^0.79，f = n lg n）→ Θ(n lg n)
\(T(n) = 2T(n/2) + n \lg n\)	2	2	n lg n	不适用（间隙）
\(T(n) = 2T(n/2) + n\)	2	2	n	2 → Θ(n lg n)
\(T(n) = 8T(n/2) + n^2\)	8	2	n²	1（临界 = n³，f = n²）→ Θ(n³)
\(T(n) = 7T(n/2) + n^2\)	7	2	n²	1（临界 = n^lg7，f = n²）→ Θ(n^lg7)

三、关键图表

核心公式对照表

式编号

内容

式 4.1

归并排序标准递归式：\(T(n) = 2T(n/2) + \Theta(n)\)

式 4.7

最大子数组递归式：\(T(n) = 2T(n/2) + \Theta(n)\)

式 4.17

朴素分治矩阵乘法：\(T(n) = 8T(n/2) + \Theta(n^2)\)

式 4.18

Strassen 矩阵乘法：\(T(n) = 7T(n/2) + \Theta(n^2)\)

式 4.19

含 floor 的变体：\(T(n) = 2T(\lfloor n/2 \rfloor) + n\)

式 4.20

主定理标准形式：\(T(n) = aT(n/b) + f(n)\)

定理 4.1

主定理三种情形

四、思维导图

mindmap
  root((第 4 章 分治策略))
    最大子数组
      暴力Θ(n²)
      跨中点合并
      Θ(n lg n)
    矩阵乘法
      朴素8乘法
      Strassen7乘法
      n^lg7
    代入法
      猜解
      归纳验证
      减低阶项
    递归树
      每层代价
      几何级数
      树高
    主定理
      n^log_b a
      三种情形
      间隙情形
    规则性条件
      af(n/b)≤cf(n)
      情形3验证
    应用
      归并排序
      最大子数组
      Strassen

五、重点与易错点

分治三步：Divide / Conquer / Combine——分治算法的伪代码必须明确分这三步。
跨边界子问题不是「更小的同类问题」：例如最大子数组中跨越 mid 的子问题，其规模与原问题相当——分治时把这类问题归入 Combine 步骤。
最大子数组分治解 = Θ(n lg n)，非最优：第 5 章给出 Θ(n) 的 Kadane 算法——分治不是终点。
Strassen 之前的下界：SQUARE-MATRIX-MULTIPLY = Θ(n³) 看起来很显然——Strassen 证明「明显」的下界也能被突破。
Strassen 的实际可行性：当 n < ~50 时朴素更快（常数因子）；现代线性代数库用 BLAS 优化的 Strassen / 进一步优化（Copper-Viola 等）。
代入法的两个难点：(1) 猜解的形式（靠经验或递归树）；(2) 归纳假设不够强——往往需要「减低阶项」。
递归树的「sloppiness」是允许的：当你只想生成猜测、随后用代入法验证时，可以忽略 floor/ceiling、不精确求和等。
主定理的「间隙」：f(n) 与 n^log_b a 只差对数因子时主定理不适用；需用其他方法（如代入法证明 \(T(n) = 2T(n/2) + n \lg n\) = Θ(n lg² n)）。
主定理的情形 3 需要规则性：\(a f(n/b) \leq c f(n)\)（c < 1）；大多数多项式函数满足，但有些函数（如 f(n) = n lg n 在某些情况下）需要单独验证。
Strassen 的 lg 7 精度：\(2.80 < \lg 7 < 2.81\)——记住这个范围足够；更精确的算法（如 Pan 的 68×68、70×70、72×72 方法）能进一步降低指数。
递归式中 a 与 b 的语义：a = 递归调用次数（子问题数）；b = 子问题规模缩减因子（如 n/b）。这是主定理的核心「参数」。
基础情形可以省略：书写递归式时通常省略 T(1) = Θ(1)，因为只影响常数因子，不改变渐近结果（Theorem 4.1 形式化此断言）。
floor / ceiling 真的不重要吗？：通常不影响渐近界（Theorem 4.1 给出此保证），但少数「边界情形」可能导致常数因子差异——实际工程中要注意。
分治 vs 动态规划：当子问题有重叠时（如 Fibonacci、子集和问题），分治会重复求解——改用动态规划（第 15 章）。
最大子数组的转化：把「价格」转化为「价格变化」（差分数组）后，问题变为「最大子数组」——这种「问题转化」是算法设计中常见的第一步。

第 4 章 分治策略 (Divide-and-Conquer)

核心结论

一、核心概念

二、详细笔记

4.1 最大子数组问题 (Maximum Subarray)

4.2 Strassen 矩阵乘法

4.3 代入法 (Substitution Method)

4.4 递归树法 (Recursion-Tree Method)

4.5 主定理 (Master Theorem)

三、关键图表

四、思维导图

五、重点与易错点

第 4 章分治策略 (Divide-and-Conquer)