# 五.分治算法
概念
将一个难以直接解决的大问题，分割成一个规模较小的相同问题，以便各个击破，分而治之。
思想策略
对于一个规模为 n 的问题，若该问题可以容易的解决（比如说规模 n 较小）则直接解决，否则将其分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各子问题的解合并得到原问题的解。
特征
- 1.该问题的规模缩小到一定的程度就可以容易地解决
- 2.该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
- 3.利用该问题分解出的子问题的解可以合并为该问题的解
- 4.利用该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题
第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加
第二条特性是应用分治法的前提它也是大多数问题可以满足的，此特性反映了递归思想的应用
第三条特性是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。
第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
基本步骤
- 1.分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
- 2.解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
- 3.合并：将各个子问题的解合并为原问题的解
适用分治法求解的经典问题
- 1.二分搜索
- 2.大整数乘法
- 3.Strassen 矩阵乘法
- 4.棋盘覆盖
- 5.合并排序
- 6.快速排序
- 7.线性时间排序
- 8.最接近点对问题
- 9.循环赛日程表
- 10.汉诺塔