入门：分治三步、适用条件与三大范式辨析
基于通用算法概念 · 核于 2026-07
速查
- 定义：分治（Divide and Conquer）是把原问题拆成若干规模更小、结构相同的子问题，递归求解子问题后再合并子问题的解得到原问题解的方法论——核心是三步「分（Divide）/ 治（Conquer）/ 合（Combine）」。
- 三步详解：分解——把原问题切成 a 个规模约为 n/b 的同构子问题；解决——递归求解每个子问题，规模足够小（如 n≤阈值）时直接算；合并——把 a 个子问题的解拼装成原问题的解。
- 递推关系：
T(n) = a·T(n/b) + f(n)——其中a是子问题个数、n/b是子问题规模、f(n)是分解+合并的代价；主定理据此给出闭式解。 - 适用条件：①问题能切成同构子问题（结构相同）；②子问题之间相互独立（无依赖、可并行）；③子问题的解能高效合并；④递归有自然边界（规模小到直接可解）。
- 分治 vs DP：分治的子问题独立（不重叠，如归并排序的左右两半互不相干）；DP 的子问题重叠（被反复求解，如斐波那契 f(n-1) 与 f(n-2) 都依赖 f(n-3)）——重叠时朴素分治会指数级重复计算，必须加记忆化升级为 DP。
- 分治 vs 贪心：分治自顶向下「分而治之」，不要求局部最优即全局最优；贪心每步取局部最优，需严格证明「局部最优 ⇒ 全局最优」。贪心更轻量但适用面窄，分治/DP 是保底解。
- 分治 vs 减治：减治（Decrease and Conquer）每次只把问题缩小一个常量（如插入排序每次处理一个元素）或减半（如二分查找每次砍一半）——减治是分治 a=1 的特例，没有「合并」步骤。
- 复杂度来源：分治总代价 = 各层分解合并代价之和；由主定理，当
f(n)与n^(log_b a)同阶时总复杂度为O(n^(log_b a) · log n)，归并排序即此例O(n log n)。 - 代码模板：
solve(问题)→ 若足够小直接返回 → 否则subs = divide(问题)→res[i] = solve(subs[i])→return combine(res)。 - 递归深度：每次规模除以 b 时深度为
log_b n，这是分治栈空间 O(log n) 的来源；每次只减 1（如朴素递归）深度为 n，易栈溢出。 - 进阶顺序：分治三步与主定理 → 经典分治应用 → 参考。
一、分治三步：分、治、合
分治的全部精髓浓缩在三个动作里。以「对 n 个元素排序」为例：
┌─────────────────────────────────────────────┐
│ 原问题：排序 [38, 27, 43, 3, 9, 82, 10] │
└──────────────────┬──────────────────────────┘
分 Divide │ 从中间切成两半
┌───────────────┴────────────────┐
▼ ▼
[38,27,43,3] [9,82,10]
│ 治 Conquer（递归） │ 治 Conquer（递归）
▼ ▼
[3,27,38,43] [9,10,82]
└───────────────┬────────────────┘
合 Combine │ 双指针归并两个有序序列
┌───────────────┴────────────────┐
▼ ▼
[3,9,10,27,38,43,82] ← 原问题的解- 分解（Divide）：把原问题切成若干规模更小、结构相同的子问题。归并排序里是「从中间一刀切成左右两半」，每半约 n/2 个元素。关键是子问题与原问题同构（都是「排序」），只是规模变小。
- 解决（Conquer）：递归地求解每个子问题。规模足够小时（如只剩 1 个元素，天然有序）直接返回——这是递归的边界条件。
- 合并（Combine）：把子问题的解拼装成原问题的解。归并排序里是「双指针归并两个有序序列」，代价 O(n)。合并的代价往往决定整个算法的复杂度。
代码模板（背下来）
js
function solve(problem) {
if (isSmallEnough(problem)) { // 边界：足够小直接算
return solveDirectly(problem);
}
const subs = divide(problem); // 1. 分
const results = subs.map(solve); // 2. 治（递归）
return combine(results); // 3. 合
}这个模板适用于几乎所有分治算法——归并排序、快排、最近点对、Karatsuba、Strassen 都只是 divide/combine 的具体实现不同。
二、适用条件：什么时候用分治
分治不是万能的，它对问题有四个要求：
- 可分解为同构子问题：问题能自然地切成结构相同的更小子问题。排序、查找、矩阵乘法都满足；但「求图的最短路」难以切成同构子问题（子图的最短路不一定拼成全图最短路），所以分治不适用。
- 子问题相互独立：子问题之间没有依赖、不共享状态，可以并行求解。这是分治区别于 DP 的核心——归并排序的左右两半互不相干，而 DP 的子问题互相重叠。
- 子问题的解可高效合并：合并代价
f(n)不能太大，否则总复杂度退化。归并的合并是 O(n)，所以总 O(n log n)；若合并退化到 O(n²)，整体就 O(n² log n) 比暴力还差。 - 有自然递归边界：规模小到某个阈值（如 n=1）时问题可直接求解，保证递归能终止。
一句话判断：「能切成同构、独立的子问题，且合并不贵 → 分治」。
三、递推关系与复杂度直觉
分治算法的复杂度由递推关系刻画：
T(n) = a · T(n/b) + f(n)
│ │ │
│ │ └── 分解 + 合并的代价（如归并是 O(n)）
│ └────── 子问题规模（每次除以 b）
└────────────── 子问题个数（每次切成 a 个）a：每层把问题切成几个子问题（归并 a=2，快排平均 a=2，二分 a=1，Strassen a=7）。b：每个子问题的规模是原问题的 1/b（通常 b=2）。f(n)：分解与合并的总代价（归并 f(n)=O(n)，二分 f(n)=O(1)）。
直觉：递归树共有 log_b n 层，第 i 层有 a^i 个子问题、每个规模 n/b^i；总代价是各层代价之和。关键看「子问题数量的增长 a^i」与「单个子问题代价的下降 (n/b^i)^k」谁主导——这正是主定理要解决的事（详见分治三步与主定理）。
| 算法 | a | b | f(n) | T(n) |
|---|---|---|---|---|
| 二分查找 | 1 | 2 | O(1) | O(log n) |
| 归并排序 | 2 | 2 | O(n) | O(n log n) |
| 快速排序（平均） | 2 | 2 | O(n) | O(n log n) |
| Karatsuba 大整数 | 3 | 2 | O(n) | O(n^1.585) |
| Strassen 矩阵 | 7 | 2 | O(n²) | O(n^2.807) |
四、分治 vs DP：独立 vs 重叠
这是最高频的辨析点。两者都「把大问题拆成小问题」，区别在于子问题是否重叠：
分治（子问题独立）： DP（子问题重叠）：
排序[1..n] fib(n)
/ \ / \
排序[1..n/2] 排序[n/2..n] fib(n-1) fib(n-2)
（两半无交集） /\ /\
... fib(n-3) ... ← fib(n-3) 被算两遍！- 归并排序（分治）：左右两半元素完全不重叠，子问题独立，无需记忆化。
- 朴素递归求斐波那契（坏的分治）：
fib(n)=fib(n-1)+fib(n-2)，fib(n-1)和fib(n-2)都依赖fib(n-3)，子问题大量重叠——朴素分治是 O(2ⁿ)，加记忆化（即升级为 DP）后降到 O(n)。
判据：子问题不重叠 → 分治；子问题重叠 → DP（记忆化/递推填表）。这也是为什么 DP 被称为「带记忆化的分治」。
五、分治 vs 贪心 vs 减治
| 范式 | 核心思想 | 子问题关系 | 典型 |
|---|---|---|---|
| 分治 | 切成同构子问题再合并 | 独立、并行 | 归并排序、最近点对 |
| 减治 | 每次缩小一个常量或一半 | 无合并（a=1 特例） | 二分查找、插入排序 |
| DP | 重叠子问题 + 记忆化 | 重叠 | 背包、LCS、斐波那契 |
| 贪心 | 每步取局部最优 | 无回溯 | 哈夫曼编码、Dijkstra |
- 分治 vs 贪心：分治自顶向下「分而治之」，不假设局部最优即全局最优；贪心每步只看眼前，必须严格证明局部最优能推出全局最优（否则会得到错误解）。贪心更轻量但适用面窄，能用贪心优先用贪心，分治/DP 是保底。
- 分治 vs 减治：减治（Decrease and Conquer）是分治的退化——
a=1，每次只留一个子问题，没有「合并」步骤。二分查找是减治的典型（每次砍一半，无合并），常被归入分治的广义范畴，严格说是「减治特例」。
下一步
理解了分治三步与适用条件后，下一步是用主定理精确分析分治算法的复杂度——它是求解 T(n)=aT(n/b)+f(n) 的万能公式，见分治三步与主定理。