一、什么是分治
分治（Divide and Conquer） 将一个问题递归地分解为若干个规模更小的同类子问题，分别求解后再合并结果。
三步曲：
- Divide：将问题拆成若干子问题。
- Conquer：递归解决子问题（足够小时直接求解）。
- Combine：将子问题的解合并为原问题的解。
Mermaid · 渲染中（下方为源码）
graph TD P[原问题 n] --> D1[子问题 n/2] P --> D2[子问题 n/2] D1 --> S1[子问题 n/4] D1 --> S2[子问题 n/4] D2 --> S3[子问题 n/4] D2 --> S4[子问题 n/4] S1 --> M[合并结果] S2 --> M S3 --> M S4 --> M
与 DP 的区别：分治的子问题互不重叠；DP 的子问题大量重叠。
二、分治的适用条件
| 条件 | 说明 |
|---|---|
| 可分解 | 问题能拆成规模更小的同类问题 |
| 子问题独立 | 子问题之间无公共子子问题（否则用 DP） |
| 可合并 | 子问题的解能高效合并为原问题的解 |
| 递归基 | 存在足够小的基本情况可直接求解 |
三、主定理（Master Theorem）
分治算法的复杂度通常满足递推：
[T(n) = a \cdot T(n/b) + O(n^d)]