分治法

原理：将大问题转换为一个或多个子问题，知道问题可以轻易解决，最后将子问题的结果进行合并

策略：对于一个规模为n的问题，若该问题可以容易的解决(比如规模n较小)则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各个子问题的解合并得到原问题的解。

分治法使用场景

1. 该问题的规模缩小到一定的程度就可以容易的解决。
2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3. 利用该问题分解出的子问题的解可以合并为该问题的解。
4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

第一条特征是绝大多数问题可以满足的，问题的复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提。它是大多数问题可以满足的，此特征反映了递归思想的应用。第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条，而不具备第三条特征，则可以考虑使用贪心法或者动态规划法。第四条关系到分治法的效率，如果各个子问题是不独立的则分治法要做寻多不必要的工作，重复的解决公共的子问题，此时虽然可用分治法，但一般使用动态规划法较好。

分治法的基本步骤

• 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
• 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
• 合并：将各个子问题的解合并为原问题的解

分治法的复杂性分析

一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。设分解阈值

，且最小子解规模为1的问题消耗一个单位时间。设将原问题分解为k个子问题以及用merge将K个子问题的解合并为原问题的解需用f(n)个单位时间，用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间：

可以使用分治法求解的一些经典问题

1. 二分搜索
2. 大整数乘法
3. Strassen矩阵乘法
4. 棋盘覆盖
5. 合并排序
6. 快速排序
7. 线性时间选择
8. 最接近点对问题
9. 循环赛日程表
10. 汉诺塔