返回：0400 算法设计与分析总目录 · 上一章：0404 Chap4 贪心算法 · 下一章：0406 Chap6 动态规划

1、学习目标

分治把大问题拆成若干规模更小的同类问题，分别求解后再合并。它的关键是：拆分要降低规模，合并不能太贵。

模块 要掌握的内容
分治框架 divide、conquer、combine
复杂度分析 递推式、递归树
典型算法 归并排序、快速排序、逆序数
几何问题 最近点对
高阶算法 大整数乘法、矩阵乘法、FFT

2、分治框架

1
2
3
4
5
6
Solve(P):
    if P 足够小:
        直接求解
    split P into P1, P2, ...
    分别求解子问题
    合并子问题答案

复杂度常写为：

1
T(n) = aT(n/b) + f(n)

其中 a 是子问题个数，n/b 是子问题规模，f(n) 是拆分和合并代价。

3、归并排序

归并排序：

  1. 把数组分成两半。
  2. 分别排序。
  3. 合并两个有序数组。

递推式：

1
T(n) = 2T(n/2) + O(n)

复杂度 O(n log n)，空间 O(n)，稳定。

1
2
3
4
5
6
7
void mergeSort(vector<int>& a, int l, int r) {
    if (r - l <= 1) return;
    int m = (l + r) / 2;
    mergeSort(a, l, m);
    mergeSort(a, m, r);
    merge(a, l, m, r);
}

归并排序也是很多分治问题的模板：两个子问题独立求解，跨边界信息在合并阶段处理。

4、逆序数

逆序对：

1
i < j 且 a[i] > a[j]

直接枚举是 O(n^2)。分治做法借助归并排序：

  1. 左半内部逆序数。
  2. 右半内部逆序数。
  3. 跨左右逆序数。

合并时如果右半元素小于左半当前元素，则它小于左半剩余所有元素。

1
count += mid - i

总复杂度 O(n log n)。

5、最近点对

平面上给定 n 个点，求最近两点距离。

分治思路：

  1. 按 x 坐标排序。
  2. 分成左右两半，分别求最近距离 d_left、d_right。
  3. 令 d = min(d_left, d_right)。
  4. 只检查中线附近宽度 2d 的条带。
  5. 条带内按 y 排序，每个点只需检查常数个后继点。

关键是条带检查能控制在 O(n)，总复杂度为 O(n log n)。

6、大整数乘法

普通乘法把两个 n 位数相乘，需要 O(n^2) 位运算。

Karatsuba 思路：

1
2
3
x = a * 10^m + b
y = c * 10^m + d
xy = ac * 10^(2m) + (ad+bc) * 10^m + bd

朴素需要 ac、ad、bc、bd 四次乘法。Karatsuba 用：

1
ad + bc = (a+b)(c+d) - ac - bd

只需三次规模减半乘法：

1
T(n) = 3T(n/2) + O(n)

复杂度约为 O(n^1.585)。

7、矩阵乘法

普通矩阵乘法复杂度 O(n^3)。Strassen 算法用 7 次子矩阵乘法替代 8 次：

1
T(n) = 7T(n/2) + O(n^2)

复杂度约为 O(n^2.807)。

它的理论意义很大，但工程实现要考虑常数、缓存、数值稳定性和矩阵规模。

8、FFT

多项式乘法如果直接卷积：

1
c_k = sum a_i * b_j，其中 i+j=k

复杂度 O(n^2)。

FFT 的思路：

  1. 系数表示转为点值表示。
  2. 点值逐点相乘。
  3. 逆变换回系数表示。

核心加速来自单位根的对称性，把 DFT 分治为偶数项和奇数项：

1
DFT(n) = 2 * DFT(n/2) + O(n)

复杂度 O(n log n)。

9、分治设计要点

问题 要问自己
怎么拆 子问题是否同类、规模是否下降
怎么合 合并是否比直接做更便宜
跨边界 是否有跨左右子问题的信息需要处理
递推式 子问题个数、规模、合并代价是什么
边界 小规模时如何直接求解

10、易错点

易错点 修正
只会背 O(n log n) 要能写出递推式
逆序数跨区间漏算 合并阶段专门统计
最近点对条带全比较 按 y 排序后只查常数个候选
Karatsuba 仍做四次乘法 关键是用三次乘法
FFT 只记结论 要理解点值表示让乘法变成逐点相乘

11、复盘清单

检查项 状态
能写出分治三步骤 待复盘
能画归并排序递归树 待复盘
能用归并统计逆序数 待复盘
能解释最近点对条带为什么只查常数个点 待复盘
能推导 Karatsuba 的三次乘法 待复盘
能说出 FFT 的三步：求值、相乘、插值 待复盘