分治算法

将问题分解为独立子问题 → 递归求解 → 合并子问题的解。

三阶段

1. 分解：拆分为相同形式的子问题
2. 解决：递归求解（足够小时直接解）
3. 合并：整合子问题的解

复杂度分析

递推式 ，通过主定理求解：

• 若 ，则
• 若 ，则
• 若 且 ，则

典型应用

归并排序、快速排序、二分查找、汉诺塔。