分治法（Divide and Conquer）
1. 核心思想
把规模为 $n$ 的问题分解为 $k$ 个规模较小的相互独立的子问题，递归求解后再把子问题的解合并成原问题的解。
三个阶段：
- 划分（Divide）：将原问题划分为若干规模更小的同类子问题。
- 求解（Conquer）：递归求解各子问题；若子问题规模足够小（到达递归出口）则直接求解。
- 合并（Merge）：将子问题的解合并为原问题的解。
2. 适用条件
- 问题可缩小到一定规模后容易直接求解；
- 问题具有最优子结构，即可以分解为若干规模较小的相同问题；
- 子问题的解可以合并为原问题的解；
- 各子问题相互独立，不包含公共子问题（否则应改用动态规划）。
3. 复杂度分析方法
分治法的时间复杂度满足递推式：
$$ T(n) = aT(n/b) + f(n) $$三种求解方式：
- 代入法：猜出解的形式，用数学归纳法验证。
- 递归树法：逐层展开，累加每层代价。
- 主定理（Master Theorem）：比较 $f(n)$ 与 $n^{\log_b a}$ 的量级：
| 情形 | 条件 | 解 |
|---|---|---|
| 1 | $f(n) = O(n^{\log_b a - \varepsilon})$ | $T(n) = \Theta(n^{\log_b a})$ |
| 2 | $f(n) = \Theta(n^{\log_b a})$ | $T(n) = \Theta(n^{\log_b a}\log n)$ |
| 3 | $f(n) = \Omega(n^{\log_b a + \varepsilon})$ 且满足正则条件 | $T(n) = \Theta(f(n))$ |
4. 典型问题
| 问题 | 划分方式 | 合并代价 | 复杂度 |
|---|---|---|---|
| 归并排序 | 从中间二分 | $O(n)$ | $O(n\log n)$ |
| 快速排序 | 按基准值分区 | $O(n)$ | 平均 $O(n\log n)$ |
| 二分查找 | 从中间二分，只递归一侧 | $O(1)$ | $O(\log n)$ |
| 最大子段和 | 从中点二分，跨中点单独求 | $O(n)$ | $O(n\log n)$ |
| 大整数乘法 | 按位二分（Karatsuba） | $O(n)$ | $O(n^{1.585})$ |
| 棋盘覆盖 | 四分，特殊方格所在块递归 | $O(1)$ | $O(4^k)$ |
| 循环赛日程表 | 二分，右下角等于左上角 | $O(n^2)$ | $O(n^2)$ |
5. 与其他策略的对比
- 分治 vs 动态规划：分治的子问题相互独立、不重复；动态规划的子问题相互重叠，需要存表避免重复计算。
- 分治 vs 减治：分治通常要处理全部子问题再合并；减治（如二分查找、快速选择）每层只递归处理其中一个子问题。
评论