分治法

分治法求解的思想是将整个问题分成若干小问题后分而治之。通常，由分治法多得到的小问题与原问题具有相同的类型。并且在求出了这些子问题的解之后，还要找到适当的方法把它们合并成整个问题的解。基于此思想，使用递归描述这类（使用分治策略设计的）算法是一个很自然的选择。（当然，之后将递归再转为迭代，进一步优化是另一个话题。）

引用维基百科的一段话来帮助理解分治和递归的关系。

It is by definition that divide-and-conquer creates subproblems of the same form as the initial problem - these subproblems are continually broken down until some base case is reached, and the number of divisions correlates with the size of the input. Recursion is a natural choice for this kind of problem.

Or

In computer science, divide and conquer is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.

列举一些典型的可以使用分治策略设计的算法：

【二分检索】

二分检索时间复杂度

成功检索 最好： O(1)； 平均：Ｏ(logn)； 最坏：Ｏ(logn)

不成功检索：最好，最坏，平均均为Ｏ(logn)

*****通过数学论证可知，任何一种以比较为基础的检索算法，其最坏情况时间都不可能低于O(logn).二分检索是解决检索问题的最优的最坏情况算法。

【找最大和最小元素】

*****当A(1:n)中的元素是多项式、向量、非常大的数或者字符串是，一次元素比较所用的时间比其他运算的时间要多得多。因为当分析这类算法的时间复杂度时，只需要将元素比较次数求出即可。

*****估算递归算法空间复杂度：递归级数*每次递归需要保留到栈中的元素大小

【归并排序】使用分治策略设计的排序算法。

*****任何以关键字比较为基础的排序算法，其最坏情况的时间下界都为O(nlogn)。

【快速排序】详情参考 快排

引申：几种典型排序算法的详细比较 参考 几种排序算法的总结和比较

【选择第k小问题】借助快排思想，划分，递归

备注：文中*****表示一些平时没有注意到的重要结论。

引用：

Divide and conquer algorithm

几种排序算法的总结和比较