FANGT

分治算法（Divide and Conquer）

作者：

fangys

分治算法就是先“分”，再“治”，最后“合”。

核心思想

把一个复杂的大问题，拆成若干个结构相同的小问题，分别解决后，再把结果合并，得到原问题的答案。

步骤

  1. 分解（Divide）：把原问题拆分成若干个规模更小、结构相同的子问题。
  2. 解决（Conquer）：子问题足够简单时，直接求解；否则递归继续分治。
  3. 合并（Combine）：将子问题的结果合并，得到原问题的解。

使用场景

  • 问题可以清晰拆分
  • 子问题相互独立（无过多重叠，否则更适合动态规划）
  • 子问题解可以高效合并

经典应用

  1. 归并排序：把数组切开，分别递归排序，最后合并成有序数组
  2. 快速排序：选基准将数组分成两部分，分别递归排序，天然有序无需额外合并
  3. 二分法、三分法
  4. 大数乘法、矩阵乘法
  5. 求逆序对、最近点对

常用递推式

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

  • a：子问题个数
  • b：每次规模缩小倍数
  • f(n)：分解 + 合并的耗时

常见复杂度

  • 归并排序：O(nlogn)
  • 二分查找：O(logn)
  • 快速排序：平均 O(nlogn)，最坏 O(n^2)

与递归、动态规划的对比

分治：子问题独立，不重复计算

动态规划：子问题重叠，用缓存避免重复

递归：只是实现方式，分治常靠递归实现

总结

大事化小，小事解决，结果合并。