分治

分治法

基本介绍

分治法，即“分而治之”，对于一个难以解决的大问题，将其分解成k个相同或相似的规模更小的子问题，一直分解直到问题足够小，极容易求解为止。

解题步骤

分治法建模的大概流程可以分为三步：

1.分解：将大问题分解成多个更小的独立且相同或相似子问题，直到子问题容易容易求解
2.解决：递归解决子问题
3.合并：将子问题的解一层一层合并，直到最终合并成原问题的解

题目特征

一般能用分治法求解的题目有以下特征：

1.最优子结构：该问题可分解为若干个规模较小的子问题，并且子问题规模缩小到一定程度就能够容易解决，同时子问题的解能够合并为该问题的解
2.平衡子问题：子问题规模大致相同，能将原问题划分为k个大小差不多相等的子问题。一般子问题规模相等的处理效率，相较规模不等的处理效率更高。
3.独立子问题：子问题之间相互独立，子问题之间不包含公共的子问题。这是区别于dp的根本特征。在dp中，子问题之间是相互联系的。

算法优势(时间效率)

分治法解决大规模的问题时，会将问题分为k个子问题分别求解。一般\(k=2\)，即分成两个规模相同的子问题求解。

对于分治，不仅能使问题更容易理解，常常也能大大优化时间复杂度。一般体现就是把时间复杂度为\(O(n)\)的某个操作优化为\(O(\log n)\)。

这是根据分治的局部优化，有利于全局的特点，将解决一个子问题的影响力扩大到了全局，最终优化时间复杂度。

基本应用

分治法应用广泛，二分、归并排序、快速排序等算法都是基于分治衍生的。
可以用分治解决的经典问题：
1.二分搜索
2.大整数乘法
3.Strassen矩阵乘法
4.棋盘覆盖
5.归并排序
6.快速排序
7.线性时间选择
8.最近点对问题
9.循环赛日程表
10.汉诺塔
下面是一个简单的算法应用清单(实时更新)：
1.二分查找、二分答案
2.归并排序、快速排序
3.双向搜索(折半搜索)

参考资料：百度、oiwiki、算法竞赛(罗勇军、郭卫斌著)