1500字范文 > 分治法( Divide and Conquer)

分治法( Divide and Conquer)

时间：2021-10-30 17:38:20

分治法也称为分解法、分治策略等。分治法算法思想如下：

(1) 将一个问题划分为同一类型的若干子问题，子问题最好规模相同。

(2) 对这些子问题求解（一般使用递归方法，但在问题规模足够小时，有时也会利用另一个算法）。

(3) 有必要的话，合并这些子问题的解，以得到原始问题的答案。

当子问题足够大时，需要递归求解时，我们称之为递归情况（Recursive Case）。当子问题变得足够小，不再需要递归时，表示递归已经“触底”，进入了基本情况（Base Case）。

以将一个问题划分为两个较小子问题为例，分治法的流程如下图所示：

递归式与分治

递归式与分治方法紧密相关。因为使用递归式可以很自然地刻画分治算法的运行时间。一个递归式（Recurrence）就是一个等式或不等式，它通过更小的输入上的函数值来描述一个函数。如使用递归式表示归并排序(Merge Sort)的最坏运行时间T(n)T(n)T(n)：

T(n)=O(1)(n=1)T(n) = O(1) (n=1)T(n)=O(1)(n=1)

T(n)=2T(n/2)+O(n)(n>1)T(n) = 2T(n/2) + O(n) (n>1)T(n)=2T(n/2)+O(n)(n>1)

其中O(1)O(1)O(1)表示在常数级别求解问题。

《算法导论》给出三种求解递归式方法，即得出算法的“O”的渐近界的方法。他们是：(1)代入法：猜测一个界，然后用数学归纳法证明这个界是正确的；(2)递归树法：将递归式转换为一棵树，其其结点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式；(3)主方法：可求解公式的递归式的界。

代入法

代入法也称代换法。代入法先猜测界的形式，然后使用数学归纳法证明这个界是正确的。本质上是数学归纳法在递归式求解的应用。实现步骤如下：

(1) 根据经验（如对比、类比、分类等等）等方式，猜测解的形式；

(2) 用数学归纳法求出解中的常数，并证明解是正确的。

之所以将其称为代入法，是因为需要将猜测的解代入函数。注意，不存在通用的方法来猜测递归式的正确解，猜测解要靠经验，偶尔还需要创造力。但是，有一些启发式方法帮助成为好的猜测者。如将当前问题和之前处理过的问题做类比、对比；先证明较宽松的上界和下界，然后缩写不确定的范围。

递归树法

可以使用递归树表示递归式。在递归树中，每一个结点表示一个单一子问题的代价，子问题对应某次递归函数调用。我们将树中每层中的代价求和，得到每层代价，然后将所有层的代价求和，得到所有层次的递归调用总代价。

递归树最适合用来生成好的猜测，然后可用代入法来验证猜测是否正确。当使用递归树来生成好的猜测时，常常要忍受一点儿“不精确”，因为关注的是如何寻找解的一个上界。使用递归树生成好的猜测的步骤如下：

(1) 分析问题，得出递归式

(2) 基于递归式创建递归树

(3) 计算递归树的代价

(4) 对代价进行“不精确处理”，推导出猜测

主方法

主方法仅适用于分治法的递归式。主方法依赖主定理。在介绍主方法前，先介绍下主定理。假设我们有递推关系式：

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

其中，nnn为问题的规模、aaa为递推下子问题的数量，n/bn/bn/b为每个子问题的规模，f(n)f(n)f(n)为递推后做的额外工作。

(1) 若存在常量ϵ>0\epsilon>0ϵ>0，使得f(n)=O(nlogb(a)−ϵ)f(n) = O(n^{log_b^{(a)-\epsilon}})f(n)=O(nlogb(a)−ϵ)，则T(n)=θ(nlogba)T(n) = θ(n^{log_b^a})T(n)=θ(nlogba)。

(2) 若存在常量k>0k>0k>0，使得f(n)=θ(nlogbalogkn)f(n)= θ(n{log_b^alog^kn})f(n)=θ(nlogbalogkn)，则T(n)=θ(nlogbalogk+1n)T(n)= θ(n{log_b^alog^{k+1}n})T(n)=θ(nlogbalogk+1n)。

(3) 若存在常数ϵ>0\epsilon>0ϵ>0，有f(n)=Ω(nlogb(a)+ϵ)f(n)=Ω(n{log_b^{(a) + \epsilon}})f(n)=Ω(nlogb(a)+ϵ)，同时存在常数c<1，以及充分大的n满足af(n/b)≤cf(n)af(n/b)≤cf(n)af(n/b)≤cf(n)，那么T(n)=θ(f(n))T(n)=θ(f(n))T(n)=θ(f(n))。

主定理的证明可以参考《算法导论》证明主定理一节。

在使用主定理前，先理解下其含义。首先将函数f(n)f(n)f(n)与函数nlogban{log_b^a}nlogba进行比较。如果函数f(n)f(n)f(n)小于函数nlogban{log_b^a}nlogba，则T(n)=θ(nlogba)T(n) = θ(n^{log_b^a})T(n)=θ(nlogba)。注意，这里是多项式意义上的小于。如果函数f(n)f(n)f(n)大于函数nlogban{log_b^a}nlogba，则T(n)=θ(f(n))T(n)=θ(f(n))T(n)=θ(f(n))。注意，这里同样是多项式意义上的大于。

注意，这三种情况并未覆盖f(n)f(n)f(n)的所有可能性。情况1和情况2之间有一定间隙，f(n)f(n)f(n)可能小于nlogban{log_b^a}nlogba，但不是多项式意义上的小于。类似的，情况2和情况3之间也有一定间隙，f(n)f(n)f(n)可能大于nlogban{log_b^a}nlogba，但不是多项式意义上的大于。如果f(n)f(n)f(n)落在上述两个间隙中，就不能使用主方法来求解递归式。

接下来介绍如何使用主方法。使用主方法很简单，只需要确定主定理哪种情况成立，即可得到解。具体步骤如下：

(1) 根据递推式获得a, b, f(n)f(n)f(n)的值;

(2) 计算nlogban{log_b^a}nlogba;

(3) 基于nlogban{log_b^a}nlogba表示f(n)f(n)f(n)，并明确ε，进而明确对应的情况（考虑间隙问题）

(4) 获取代价

经典使用场景

接下来将从实践出发，在实际场景中使用分治算法。

归并排序

归并排序，默认指二路归并排序。归并排序是使用分治法实现的排序之一。假设初始序列含有n个元素，则可看成n个有序的子序列，每个子序列的长度是1。然后将前后相邻的两个有序序列归并为一个有序序列。这与分治法**将一个问题划分为同一类型的若干子问题，对这些子问题求解，合并这些子问题的解的思路是一致的。更多相关介绍可以参考归并排序一文。

快速排序

和归并排序一样，快速排序也是基于分治技术实现的算法。与归并排序按照元素在列表中的位置进行划分不同，快速排序是按照元素的值进行划分。快速排序的基本思想是，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。更多相关介绍可以参考快速排序一文。