分治法

• 设计步骤：

  1. 分解：将原问题分解为若干规模较小的子问题。
  2. 求解：递归求解子问题（若规模够小则直接解）。
  3. 合并：将子问题的解合并为原问题的解。

• 经典算法：

  • 归并排序：$T(n)=2T(n/2)+O(n)\to O(n\log n)$。
  • 快速排序：虽然也是分治，但在 查找与排序 中详细复习。
  • 大整数乘法：将 $O(n^2)$ 优化为 $O(n^{1.59})$。
  • Strassen矩阵乘法：将 $O(n^3)$ 优化为 $O(n^{2.81})$。

• 主定理 (Master Theorem) (用于解递归方程 $T(n)=aT(n/b)+f(n)$)：

  • 比较 $n^{{\log }_{b}a}$ 与 $f(n)$ 的增长速率：
  • 若 $n^{{\log }_{b}a}>f(n)$，则 $T(n)=O(n^{{\log }_{b}a})$。
  • 若相等，则 $T(n)=O(n^{{\log }_{b}a}\log n)$。
  • 若小于，则 $T(n)=O(f(n))$。