分治法的基本思想

对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

如果原问题可分割成k个子问题，1

分治法所能解决的问题一般具有以下几个特征：

1、该问题的规模缩小到一定的程度就可以容易地解决

2、该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3、利用该问题分解出的子问题的解可以合并为该问题的解；

4、该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。它的一般的算法设计模式如下：

divide-and-conquer(P)
{
if(|P|<=n0) adhoc(P);
divide P into smaller subinstances P1,P2,...,Pk;
for(i=1;i<=k;i++)
yi=divide-and-conquer(Pi);
return merge(y1,...,yk);
}
其中，|P|表示问题P的规模。n0为一阀值，表示当问题P的规模不超过n0时，问题已容易解出，不必再继续分解。adhoc(P)是该分治法中的基本子算法，用于直接解小规模的问题P。当P的规模不超过n0时，直接算法adhoc(P)求解。算法merge(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1,P2,...,Pk的解y1,y2,...,yk合并为P的解。

根据分治法的分割原则，应把原问题分为多少个子问题才比较适宜？每个子问题是否规模相同或怎样才为适当？这些问题很难给予肯定的回答。但人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡(banlancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。

从分治法的一般设计模式可以看出，用它设计出的算法一般是递归算法。因此，分治法的计算效率通常可以用递归方程来进行分析。一个分治法将规模为n的问题分成m个规模为n/m的子问题，其中k(k<=m)个子问题需要求解。为方便起见，设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。另外再设将原问题分解为k个问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。如果用T(n)表示该分治法divide-and-conquer(P)解规模为|P|=n的问题所需的计算时间，则有：
http://image211.poco.cn/mypoco/myphoto/20090409/00/52556927200904090035023505767135836_002.jpg

下面来讨论如何解这个与分治法有密切关系的递归方程。通常可以用展开递归式的方法来解这类递归方程，反复代入求解得：

http://image211.poco.cn/mypoco/myphoto/20090409/00/52556927200904090035023505767135836_001.jpg

注意，递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果T(n)足够平滑，由n等于m的方幂时T(n)的值估计T(n)的增长速度。通常，可以假定T(n)单调上升。
另一个需要注意的问题是，在分析分治法的计算效率是，通常得到的是递归不等式：

http://image211.poco.cn/mypoco/myphoto/20090409/00/52556927200904090035023505767135836_000.jpg

在讨论最坏情况下的计算时间复杂度，用等号(=)还是用小于等于号(<=)是没有本质区别的。

概念：在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础。
精髓：
分--将问题分解为规模更小的子问题;
治--将这些规模更小的子问题逐个击破;

合--将已解决的子问题合并，最终得出"母"问题的解;

设计思想及策略：
思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
策略：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
如果原问题可分割成k个子问题，1