引言

凡治众如治寡，分数是也。                        ----孙子兵法

思想

对k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。

然后将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治与递归

由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。

分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

分治与其他算法

采用分治思想的算法有很多，例如：二分查找、快速排序、合并排序、矩阵乘法等等

分治算法的应用

分治算法的具体应用请用请参考：二分查找、快速排序、合并排序、矩阵乘法等相关知识点。

written by 金磊，隔日更新一发，转载请注明出处。