1.分治算法的基本思想

将一个规模为N的问题，分解成K个规模较小的子问题，这些子问题相互独立且月原问题性质相同。

求解出子问题的解，合并得到原问题的解。

2.分治算法特征分析

分治法能解决的问题一般具有以下几个特征：

1) 该问题的规模缩小到一定程度就可以容易的解决；

2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；

3) 利用该问题分解出子问题的解，可以合并为该问题的解；

4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题；

分治算法大多采用递归实现，第二条特征就反应了递归思想的引用。

如果满足了第一条特征和第二条特征，不满足第三条特征，可以考虑用贪心法或动态规划法。

如果不满足第四条特征，也可以用分治法，但是要做很多不必要的工作，重复的解公共的子问题，所以一般用动态规划法比较好。

3.实际应用场景

二分查找，阶乘计算，归并排序，堆排序、快速排序、傅里叶变换都用了分治法的思想。

4.依据分治法设计程序的思维过程

实际上类似数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。

1) 一定是先找到最小问题规模时的求解方法

2) 然后考虑随着问题规模增大时的求解方法

3) 找到求解的递归函数后，设计递归程序即可。

关键字:互联网 大数据 算法与数据挖掘

注:图片是北京某羽毛球馆