分治法

分治法可能是最著名的通用算法设计技术了。很多非常有效的算法实际上是这个通用算法的特殊实现。分治法是按照以下方案工作的：

将问题的实例划分为同一个问题的几个较小的实例，最好拥有同样的规模。
对这些较小的实例求解（一般使用递归方法，也会使用一些其他方法）。
必要的话，合并这些较小问题的解，以得到原始问题的解。

分治法的流程参见图4.1，该图描述的是将一个问题划分为两个较小子问题的例子。

作为一个例子，我们假设待解决问题是计算n个数字a0,…,an-1的和。如果n > 1,计算前[n/2]个数字的和以及计算后[n/2]个数字的和。一旦这两个和都被计算出来了（通过递归应用上述方法），就可以把这两个和相加，来得到原始问题的答案：

求和的例子显示了分治法的最典型应用：问题规模为n的实例被划分为两个规模为n/2的实例。但不会比简单地顺序相加效率更高。下面我们分析分治法的效率。

一般的情况下，规模为n的实例划分为若干个规模为n/b的实例，其中a个实例需要求解。为了简化分析，我们假设n是b的乘方，对于算法的运行时间，我们有下列递推式：

T(n) = aT(n/b) + f(n). (4.1)

f(n)表示将问题分解为小问题和将结果合并起来所消耗的时间。递推式4.1为通用分治递推式.T(n)de增长次数取决于常量a和b的值，以及函数f(n)的增长次数。在分析许多分治算法的效率时可以应用下列定理简化我们的工作。

主定理 如果在递推式4.1中f(n)∈Θ(n^d)，其中d≧0，那么：

对于上面的分治求和算法，当输入规模为n＝2^k时，加法运算次数A(n)可以用下面的递推式表示：

A(n) = 2A(n/2) + 1

对上面的例子，a=2,b=2,d=0;这样一来，a > b^d,

通过这个定理，无需对递推式求解，就可以知道该算法的效率类型。

小结

分治法是一种一般性的算法设计技术，它将问题的实例划分为若干个较小的实例（最好拥有同样的规模），对这些较小的实例递归求解，然后合并这些解，以得到原始问题的解。许多高效的算法都是基于这种技术的，虽然有时候它的适应性和效率并不如一些更简单的算法。
许多分治算法的时间效率T(n)满足方程T(n)＝aT(n/b)+f(n).主定理确定了该方程解的增长次数。
合并排序是一种分治排序算法。它把一个输入数组一分为二，并对它们递归排序，然后把这两个排好序的子数组合并为原数组的一个有序排列。在任何情况洗，这个算法的时间效率都是Θ(nlogn),而且它的键值比较次数非常接近理论上的最小值。它的主要缺点是需要相当大的额外存储空间。
快速排序是一种分治排序算法，它根据元素值和某些事先确定的元素的比较结果，来对输入元素进行分区。快速排序十分有名，这不仅因为对于随机排列的数组，它是一种较为出众的nlogn效率算法，而且因为它的最差夏绿是平方级的。
折半查找是一种对有序数组进行查找O(logn)算法。它是应用分治技术的一个非典型案例，因为在每次迭代中，它只需要解决两个问题的一个。
二叉树的经典遍历算法——前序，中序，后序和其他类似的算法都需要递归调用左右两棵子树，它们都可以当作是分治技术的例子。用一些特定的外部顶点来替代给定树的空子树，有助于对这些算法进行分析。
有一种处理两个n位整数相乘的分治算法，大约需要做n^1.585次一位数乘法。
Strassen算法只需要做7次乘法就能计算出两个2阶方阵的积，但比基于定义的算法要做更多次的加法。利用分治技术，该算法计算两个n阶方阵的乘法时需要做n^2.807次乘法。
分治技术可以成功地应用于两个重要的计算几何问题：最近对问题和凸包问题。