分治算法就是先“分”，再“治”，最后“合”。
核心思想
把一个复杂的大问题，拆成若干个结构相同的小问题，分别解决后，再把结果合并，得到原问题的答案。
步骤
- 分解（Divide）：把原问题拆分成若干个规模更小、结构相同的子问题。
- 解决（Conquer）：子问题足够简单时，直接求解；否则递归继续分治。
- 合并（Combine）：将子问题的结果合并，得到原问题的解。
使用场景
- 问题可以清晰拆分
- 子问题相互独立（无过多重叠，否则更适合动态规划）
- 子问题解可以高效合并
经典应用
- 归并排序：把数组切开，分别递归排序，最后合并成有序数组
- 快速排序：选基准将数组分成两部分，分别递归排序，天然有序无需额外合并
- 二分法、三分法
- 大数乘法、矩阵乘法
- 求逆序对、最近点对
常用递推式
T(n)=aT(n/b)+f(n)
- a：子问题个数
- b：每次规模缩小倍数
- f(n)：分解 + 合并的耗时
常见复杂度
- 归并排序：O(nlogn)
- 二分查找：O(logn)
- 快速排序：平均 O(nlogn)，最坏 O(n^2)
与递归、动态规划的对比
分治：子问题独立，不重复计算
动态规划：子问题重叠，用缓存避免重复
递归：只是实现方式，分治常靠递归实现
总结
大事化小，小事解决，结果合并。