分治法（一）

参考  　　算法设计与分析 　　第四章 　　分治法

这篇文章将讨论：

1）　　分治策略的思想和理论

2）　　几个分治策略的例子：合并排序，快速排序，折半查找，二叉遍历树及其相关特性。

说明：这几个例子在前面都写过了，这里又拿出来，从算法设计的策略的角度把它们放在一起来比较，看看分治是如何实现滴。
由于内容太多，我将再花一篇文章来写4个之前没有写过的分治算法：1，大整数乘法   2，矩阵乘法的分治策略   3，最近点对  4，凸包问题，请见下一篇。

好了，切入正题。

---------------------------------------------------------------------------------------------------------------------------------------------------


分治算法是按照下列方案来工作的：

1）将问题的实例划分为几个较小的实例，最好具有相等的规模（事实上，一般来说就是这样来分的）

2）对这些较小的实例求解（一般使用递归的方法，但在问题规模足够小的时候也可以采用采用另一个算法（停止递归））

3）如果有必要的话，合并这些较小问题的解，以得到原始问题的解（事实上，一个分治算法的精华就在于合并解的过程）