算法分析与设计 第3讲 — 分治策略（Divide and Conquer）
课程：0A002 算法分析与设计 讲师：北京大学 屈婉玲 来源：田浩然上传的资料 页数：53 页
一、分治策略的基本思想
核心三步
- 划分（Divide）：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题
- 求解子问题（Conquer）：递归地解各子问题，直到子问题小到可以直接求解
- 综合解（Merge/Combine）：将子问题的解合并为原问题的解
算法框架
Divide-and-Conquer(P)
1. if |P| ≤ c then return S(P) // 小规模直接求解
2. divide P into P₁, P₂, …, P_k // 划分子问题
3. for i = 1 to k
4. yᵢ = Divide-and-Conquer(Pᵢ) // 递归求解
5. return Merge(y₁, y₂, …, y_k) // 合并解
分治法适用条件（四大特征）
| 特征 | 说明 |
|---|---|
| 可分解 | 问题可以分解为若干个相同的子问题 |
| 可直接解 | 问题规模缩小到一定程度可以直接求解 |
| 可合并 | 子问题的解可以组合为原问题的解 |
| 子问题独立 | 各子问题之间相互独立（无重叠子问题） |
平衡原则
子问题划分越均匀，效率越高。典型对比：
- 插入排序：子问题不均衡 → W(n) = W(n-1) + n-1 → O(n²)
- 归并排序：子问题均衡 → W(n) = 2W(n/2) + n-1 → O(n log n)
二、递推方程与求解方法
分治策略的算法分析工具是递推方程。
两类递推方程
| 类型 | 形式 | 求解方法 |
|---|---|---|
| 第一类 | f(n) = Σaᵢf(n-i) + g(n) | 公式法（特征根） |
| 第二类 | f(n) = a·f(n/b) + d(n) | 迭代法、递归树、Master定理 |
Master 定理（第二类递推方程核心工具）
对于 T(n) = a·T(n/b) + f(n)：
当 d(n) 为常数时：
- a ≠ 1 → T(n) = O(n^(log_b a))
- a = 1 → T(n) = O(log n)
当 d(n) = cn（线性）时：
- a < b → T(n) = O(n)
- a = b → T(n) = O(n log n)
- a > b → T(n) = O(n^(log_b a))
记忆口诀：子问题增长速度 vs 额外开销增长速度，谁大听谁的；相等时乘一个 log n。
三、经典实例分析
实例1：芯片测试
问题：n=2ᵏ 块芯片，好芯片至少比坏芯片多1片，从中挑出一片好芯片。两两测试规则：
| A报告 | B报告 | 结论 |
|---|---|---|
| B是好的 | A是好的 | A,B都好或都坏 |
| B是好的 | A是坏的 | 至少一片坏 |
| B是坏的 | A是好的 | 至少一片坏 |
| B是坏的 | A是坏的 | 至少一片坏 |
分治算法：
- 将芯片两两分组测试
- 两片都好 → 任留一片；否则两片同丢
- 递归处理剩下的芯片
- k=3 时特殊处理（2片测试，1好1坏取没测的）
复杂度：W(n) = W(n/2) + O(n) → O(n)
实例2：快速幂运算（计算 aⁿ）
传统算法：依次相乘 → Θ(n)
分治法：
- n 为偶数：aⁿ = a^(n/2) × a
- n 为奇数：aⁿ = a^((n-1)/2) × a^((n-1)/2) × a
T(n) = T(n/2) + Θ(1) → Θ(log n)
推广：Fibonacci 数也可以用矩阵快速幂在 Θ(log n) 时间内求解。
实例3：位乘问题（Karatsuba 算法）
问题：两个 n 位二进制数相乘，n=2ᵏ
传统算法：逐位相乘 → O(n²)
朴素分治：X = A·2^(n/2) + B, Y = C·2^(n/2) + D
- XY = AC·2ⁿ + (AD + BC)·2^(n/2) + BD
- 4 次子问题乘法 → W(n) = 4W(n/2) + cn → 仍然 O(n²)
Karatsuba 代数变换优化（减少子问题个数）：
AD + BC = (A-B)(D-C) + AC + BD
- 只需要 3 次乘法（AC、BD、(A-B)(D-C)）
- W(n) = 3W(n/2) + cn → O(n^log₂3) ≈ O(n^1.59)
思想精髓：通过代数变换，把子问题个数从 4 个减到 3 个，用加法换乘法。
更优结果：快速傅里叶变换（FFT）可做到 O(n log n)。
实例4：Strassen 矩阵乘法
问题：两个 n 阶矩阵相乘，n=2ᵏ
传统算法：三重循环 → O(n³)
朴素分治：分块矩阵乘法
- 8 次子矩阵乘法 + 4 次子矩阵加法
- W(n) = 8W(n/2) + cn² → 仍然 O(n³)
Strassen 算法：用 7 次乘法代替 8 次
- M₁ = A₁₁(B₁₂-B₂₂)
- M₂ = (A₁₁+A₁₂)B₂₂
- M₃ = (A₂₁+A₂₂)B₁₁
- M₄ = A₂₂(B₂₁-B₁₁)
- M₅ = (A₁₁+A₂₂)(B₁₁+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₇
- W(n) = 7W(n/2) + 18n² → O(n^log₂7) ≈ O(n^2.807)
下界：Hopcroft & Kerr (1971) 证明 2×2 矩阵乘法至少需要 7 次乘法。 当前最好上界：O(n^2.376)（Coppersmith-Winograd 及后续改进）。
实例5：平面最近点对
问题：n 个平面点，求距离最小的点对
暴力算法：C(n,2) 个点对 → O(n²)
一维分治：
- 按中位数划分左右
- 递归求左右最小距离 δ
- 求跨越中线的最小距离（只需比较中线两侧最近两点）
- T(n) = 2T(n/2) + O(n) → O(n log n)
二维分治算法：
- 按 x 坐标排序，选中线划分 PL（左半）和 PR（右半）
- 递归求 δ_L（PL 最小距离）和 δ_R（PR 最小距离），δ = min(δ_L, δ_R)
- 跨越中线处理：中线两侧 δ 范围内的点，按 y 坐标排序，每个点只需与后面最多 6 个点比较（鸽巢原理证明）
- 更新 δ
关键结论：每个点最多比较 6 个点 → 跨越步 O(n) 时间。
复杂度分析：
- 每次排序 O(n log n) → T(n) = 2T(n/2) + O(n log n) → O(n log²n)
- 预排序优化：预先排好 X、Y 数组，递归时只需 O(n) 划分子集 → T(n) = 2T(n/2) + O(n) → O(n log n)
思想精髓：把排序从递归内部提到外部作为预处理，降低一层 log n。
实例6：快速排序（QuickSort）
算法：
- 选首元素 x 作为划分基准
- 双指针 i, j 从两端向中间扫描，交换逆序对
- 最终 j 为基准的正确位置
- 递归排序左右两部分
复杂度：
| 情况 | 递推方程 | 复杂度 |
|---|---|---|
| 最坏（逆序或已排序） | W(n) = W(n-1) + n-1 | O(n²) |
| 最好（均匀划分） | T(n) = 2T(n/2) + n-1 | O(n log n) |
| 均衡划分（9:1） | T(n) = T(9n/10) + T(n/10) + n | O(n log n) |
| 平均情况 | nT(n) = (n+1)T(n-1) + 2n-2 | O(n log n) |
平均情况推导关键：用积分估计调和级数和 → T(n)/(n+1) = O(log n)
实例7：选择问题（第 k 小元素）
7.1 选最大 / 最小
- 顺序比较 → n-1 次比较
7.2 同时找最大和最小
锦标赛分组法：两两分组，组内比较得较大/较小，再分别找最大/最小
- 比较次数：⌊n/2⌋ + 2⌈n/2⌉ - 2 = ⌈3n/2⌉ - 2
7.3 找第二大
锦标赛法（类似淘汰赛）：
- 两两比较晋级，最大元素产生
- 第二大一定在与最大比较过的元素中（共 ⌈log n⌉ 个）
- 总比较次数：n + ⌈log n⌉ - 2
7.4 一般选择问题（Select 算法 / BFPRT 算法）
算法步骤：
- 将 n 个元素 5 个一组，共 ⌈n/5⌉ 组
- 每组找中位数，得到中位数集合 M（大小 ⌈n/5⌉）
- 递归找 M 的中位数 m*（作为划分基准）
- 用 m* 将 S 划分为 S₁（小于 m*）和 S₂（大于 m*）
- 若 k = |S₁|+1 返回 m*；否则递归在 S₁ 或 S₂ 中找
最坏情况分析：
- 至少有 3n/10 个元素 < m*，至少 3n/10 个 > m*
- 子问题最大规模 ≈ 7n/10
- 递推：W(n) ≤ W(n/5) + W(7n/10) + cn
- 因为 1/5 + 7/10 = 9/10 < 1 → 级数收敛 → W(n) = O(n)
为什么是 5 个一组？ 因为 5 是保证子问题比例之和 < 1 的最小奇数。3 个一组时 1/3 + 2/3 = 1，无法收敛。
应用：用中位数做快速排序的划分基准 → 最坏 O(n log n)
实例8：多项式求值（FFT 雏形）
问题：给定 n-1 次多项式 A(x)，对所有 2n 次单位根求值
| 算法 | 思路 | 复杂度 |
|---|---|---|
| 暴力 | 逐项计算求和 | O(n³) |
| 递推（Horner法则） | A(x) = a₀ + x(a₁ + x(a₂ + …)) | O(n²) |
| 分治（FFT思想） | 按奇偶拆分 A(x) = A_even(x²) + x·A_old(x²) | O(n log n) |
分治原理：
- x 是 1 的 2n 次根 → x² 恰好是 1 的 n 次根
- 递归计算 A_even 和 A_old 在 n 次根处的值
- O(n) 时间组合出 2n 次根的全部结果
- T(n) = 2T(n/2) + O(n) → O(n log n)
这就是快速傅里叶变换（FFT） 的核心思想。
四、降低分治复杂度的两条途径
途径1：代数变换 —— 减少子问题个数
- 位乘：4次乘法 → 3次乘法（Karatsuba）
- 矩阵乘：8次乘法 → 7次乘法（Strassen）
- 关键：用加法/减法换取乘法次数减少
途径2：预处理 —— 减少递归内部操作
- 平面点对：预排序 X、Y 数组，递归内部只需 O(n) 划分
- 把排序从递归内提到递归外，复杂度从 O(n log²n) 降到 O(n log n)
五、本讲要点总结
- 分治三步骤：划分 → 求解子问题 → 合并解
- 四大适用条件：可分解、可直接解、可合并、子问题独立
- 两大分析工具：递推方程 + Master 定理
- 八大经典实例：芯片测试、快速幂、位乘(Karatsuba)、矩阵乘(Strassen)、平面点对、快速排序、选择(BFPRT)、多项式求值(FFT)
- 两大优化途径：代数变换减子问题数、预处理减递归内操作
- 核心思想：平衡划分效率高、用便宜运算换昂贵运算、预处理技术
关联笔记
- 算法分析与设计 第2讲 — 数学基础（递推方程求解、求和技术、Master定理）
- 《算法导论》-Introduction to Algorithms-第3版-CLRS（第7章快速排序、第9章选择、第4章分治策略）
- 《SICP》-计算机程序的构造和解释-第二版（第1章过程与抽象，高阶函数与递归）