算法设计与分析(霍红卫)-第2章-分治法

第2章分治法2.1递归与递归方程2.2分治法2.3分治法应用实例2.1递归与递归方程2.1.1递归的概念递归(recursion)是数学与计算机科学中的基本概念。程序设计语言中的递归程序可被简单地定义为对自己的调用。递归程序不能总是自我调用，否则就会永不终止。此外，递归程序必须有终止条件。尽管递归程序在执行时间上往往比非递归程序要付出更多的代价，但有很多问题的数学模型或算法设计方法本来就是递归的，用递归过程来描述它们不仅非常自然，而且证明该算法的正确性要比相应的非递归形式容易得多，因此递归不失为一种强有力的程序设计方法。

例2.1斐波那契(Fibonacci)序列。无穷数列1，1，2，3，5，8，13，21，34，…可定义为斐波那契数列。递归形式为从这一数学定义可以自然地导出递归的斐波那契过程F(n)。F(n)1Ifn≤12

thenreturn13return

F(n-1)+F(n-2)图2-1斐波那契算法的递归结构(n=6)

例2.2欧几里得(Euclid)算法。欧几里得算法是两千年来最著名的算法之一：已知两个非负整数m，n，且m>n>0，求这两个数的最大公因子。欧几里得得出本算法基于这样一种观察，两个整数m和n的最大公因子等于n与mmodn的公因子。欧几里得算法如下：GCD(m，n)1if

n=02thenreturnm3returnGCD(n，mmodn)图2-2欧几里得算法的例子

例2.3汉诺塔(Hanoi)问题。设有三个塔座X、Y、Z，n个圆盘。这些圆盘大小互不相同，初始时，这些编号为1，2，…，n的圆盘从大到小依次放在塔座X上。最底下为最大圆盘。要求将该塔座上的圆盘移到另一个塔座Z上，并按照同样顺序放置。圆盘移动时，满足以下规则：①一次只能移动一个圆盘；②任何时刻不允许将大的圆盘放在小的圆盘之上；③圆盘可以放在X、Y和Z的任一塔座上。我们可以用递归解决这个问题。其中递归是基于这样的一个想法：当n=1时，只要将编号为1的圆盘从塔座X直接移到塔座Z上即可；当n>1时，利用Z作中间塔座，依照上述规则，将编号为n的圆盘上的n-1个圆盘从塔座X移到塔座Y上，再将X上编号为n的圆盘直接移到塔座Z上，最后，以X作中间塔座，将塔座Y上的n-1个圆盘从塔座Y移到塔座Z上。而对于n-1个圆盘的移动是一个和原问题具有相同特征的子问题，可用同样方法求解。因此，规模为n的Hanoi塔算法如下：HANOI(n，X，Y，Z)1ifn=12thenMOVE(X，1，Z)3elseHANOI(n-1，X，Z，Y)4MOVE(X，n，Z)5HANOI(n-1，Y，X，Z)

HANOI(n，X，Y，Z)表示将塔座X上编号为1~n的n个圆盘按照规则移到塔座Z上，以Y作中间塔座。HANOI(n-1，X，Z，Y)表示将塔座X上编号为1~n-1的n-1个圆盘按照规则移到塔座Y上，以Z作中间塔座。HANOI(n-1，Y，X，Z)表示将塔座Y上编号为1~n-1的n-1个圆盘按照规则移到塔座Z上，以X作中间塔座。MOVE(X，n，Z)表示将编号为n的圆盘从塔座X移到塔座Z上。递归过程在实现时，可用一个等价的递归栈实现过程的嵌套调用。递归的深度就是在整个计算中过程嵌套调用的最大程度。通常，深度取决于输入规模。因此，对于大型问题，栈所需的空间可能妨碍我们使用递归方法求解。图2-3表示n=4时汉诺塔算法的运行过程。图2-3汉诺塔的执行过程(n=4)汉诺塔算法的时间复杂度为指数级的复杂度。以下做一简要证明。假设汉诺塔算法的时间复杂度为T(n)，由递归算法可得n=1n>1不失一般性，设n为2的幂。由数学归纳法容易得出，该递归方程的解为2n-1，即O(2n)。

从上述例子可见，当算法包含调用自身的过程时，其运行时间可用递归方程(recurrenceequation)描述。本节介绍三种求解递归方程的方法。这三种方法分别是替换方法(substitutionmethod)、递归树方法(recursiontreemethod)和主方法(mastermethod)。2.1.2替换方法

例2.4利用替换方法解递归方程T(n)=2T(［n/2］)+n。

解我们猜测其解为T(n)=O(nlbn)。假设这个界限对于［n/2］成立，即存在某个常数c，T(［n/2］)≤c(［n/2］)lb(［n/2］)成立。现在要证明T(n)≤cnlbn。将假设代入递归方程可得：T(n)=2T(n/2)+n

≤2(c［n/2］lb［n/2］)+n

=cnlbn/2+n

=cnlbn-cnlb2+n

=cn

lbn-cn+n

=cnlbn-(c-1)n

≤cnlbn

最后一步在c≥1时成立。下面证明猜测对于边界条件成立，即证明对于选择的常数c，T(n)≤cnlbn对于边界条件成立。这个要求有时会产生一些问题。假设T(1)=1是递归方程的惟一边界条件，那么对于n=1，T(1)≤c·1·lb1=0与T(1)=1发生矛盾。因此，归纳法中的归纳基础不成立。我们可以很容易解决这个问题。利用这样一个事实：渐近表示法只要求对n≥n0，T(n)≤cn

lbn成立，其中n0是一个可以选择的常数。由于对于n>3，递归方程并不直接依赖T(1)，因此可设n0=2，选择T(2)和T(3)作为归纳证明中的边界条件。由递归方程可得T(2)=4和T(3)=5。此时只要选择c≥2，就会使得T(2)≤c·2·lb2和T(3)≤c·3·lb3成立。因此，只要选择n0=2和c≥2，则有T(n)≤cn

lbn成立。不幸的是，并不存在一般的方法来猜测递归方程的正确解。这种猜测需要经验，有时需要创造性。有时，一些看上去非常陌生的递归方程，在经过一些简单代数变换之后，就可以变为我们较熟悉的形式。例2.5解递归方程。

解设n=2m

或者m=lbn，则递归方程变为T(2m)=2T(2m/2)+1再做一次替换，设S(m)=T(2m)，则递归方程变为S(m)=2S(m/2)+1该方程的解为S(m)=Θ(m)。换成T，可得T(2m)=Θ(m)。将n=2m代入，得T(n)=Θ(lbn)。

2.1.3递归树方法

尽管替换方法提供了证明递归方程解的简要证明方法，但要猜测一个好的解却比较困难。以下介绍基于递归树的方法，通过这种方法，可以更好地猜测一个问题的解，并用替换方法证明这个猜测。图2-4表明了如何解递归方程T(n)=3T(n/4)+cn2。假设n为4的幂。图2-4递归树的构造过程现在，我们确定树中每一层的开销。每一层的结点数是上一层结点数的两倍，因此，第i层的结点数为3i。由于每一层子问题规模为上一层的1/4，由根向下，深度为i(i=0，1，…，log4n-1)的每个结点的开销为c(n/4i)2，那么第i层上结点的总开销为3ic(n/4i)2=(3/16)icn2

i=0，1，…，log4n-1深度为log4n的最后一层有 个结点，每个结点的开销为T(1)，该层总开销为 ，即 。将所有层的开销相加得到整棵树的开销：现在利用替换方法证明我们的猜测是正确的。假设这个界限对于n/4成立，即存在某个常数d，T(n/4)≤d(n/4)2成立。代入递归方程可得只要选取d≥(16/13)c，最后一步成立。2.1.4主方法

主方法(mastermethod)为我们提供了解如下形式递归方程的一般方法。其中a≥1，b>1为常数，f(n)是渐近正函数。递归方程(2.1)描述了算法的运行时间，算法将规模为n的问题划分成a个子问题，每个子问题的大小为n/b，其中a、b是正常数。求解这a个子问题，每个所需时间为T(n/b)。函数f(n)表示划分子问题与组合子问题解的开销。例如，对于递归方程T(n)=3T(n/4)+cn2，a=3，b=4，f(n)=Θ(n2)。

每个子问题n/b未必为整数，但用T(n/b)代替T(［n/b］)和T(［n/b］)并不影响递归方程的渐近行为，因此我们在表达这种形式的分治算法时将略去向下取整函数和向上取整函数。T(n)=aT(n/b)+f(n)(2.1)

定理2.1设a≥1，b>1为常数，f(n)为一函数。T(n)由以下递归方程定义：其中n为非负整数，则T(n)有如下的渐近界限：(1)若对某些常数ε>0，有f(n)=O(nlogba-ε)，那么T(n)=Θ(nlogba)。(2)若f(n)=Θ(nlogba)，那么T(n)=Θ(nlogbalbn)。(3)若对某些常数ε>0，有f(n)=Ω(nlogba+ε)，且对常数c<1与所有足够大的n，有af(n/b)≤cf(n)，那么T(n)=Θ(f(n))。在运用该定理之前，我们先来分析它的含义。在上述的每一种情况下，我们都把函数f(n)与函数nlogba进行比较，递归方程的解由这两个函数中较大的一个决定。例如，在第一种情形中，函数nlogba比函数f(n)更大，则解为T(n)=Θ(nlogba)在第二种情形中，这两个函数一样大，则解为T(n)=Θ(nlogbalbn)=Θ(f(n)lbn)在第三种情形中，f(n)是较大的函数，则解为T(n)=Θ(f(n))我们可用图2-5表示方程(2.1)，从另一个角度解释主定理。图2-5主定理的图示树中叶子结点数为对于第一种情形，从根到叶结点开销的权重呈几何级数增加，T(n)=f(n)+af(n/b)+a2f(n/b2)+…+

nlogba

T(1)=Θ(nlogba)叶结点占有整个权重的恒定比例。对于第二种情形，每一层的权重大致相同，T(n)=f(n)+af(n/b)+a2f(n/b2)+…+

nlogba

T(1)=Θ(nlogba1bn)对于第三种情形，从根到叶结点开销的权重呈几何级数减小，T(n)=f(n)+af(n/b)+a2f(n/b2)+…+

nlogba

T(1)=Θ(f(n))

例2.6解递归方程T(n)=4T(n/2)+n。

解由递归方程可得，a=4，b=2且f(n)=n。因此，nlogba-ε=nlb4-ε=n2-ε。选取0<ε<1,则f(n)=O(n2-ε)=O(nlogba-ε)递归方程满足主定理的第一种情形，因此T(n)=Θ(nlogba)=Θ(nlb4)=Θ(n2)

例2.7解递归方程T(n)=4T(n/2)+n2。

解由递归方程可得，a=4，b=2,且f(n)=n2。因此，nlogba

=nlb4=n2，则f(n)=O(n2)=O(nlogba)递归方程满足主定理的第二种情形，因此T(n)=Θ(nlogba

1bn)=Θ(nlb41bn)=Θ(n21bn)

例2.8解递归方程T(n)=4T(n/2)+n3。

解由递归方程可得，a=4，b=2,且f(n)=n3。因此，nlogba+ε

=nlb4+ε=n2+ε。选取0<ε<1，则

f(n)=O(n2+ε)=O(nlogba+ε)递归方程满足主定理的第三种情形。还需证明af(n/b)≤cf(n)。选择1/2≤c，则(1/2)n3≤cn3

成立，即4(n/2)3≤cn3成立，也即4f(n/2)≤cf(n)成立，因此选择c，满足1/2<c<1，则T(n)=Θ(f(n))=Θ(n3)。2.2分治法2.2.1分治法的基本思想

对于一个规模为n的问题，若该问题可以容易地解决(比如说规模n较小)，则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并，得到原问题的解。这种算法设计策略叫做分治法(divideandconquer)。分治法在每一层递归上由三个步骤组成：(1)划分(divide)：将原问题分解为若干规模较小、相互独立、与原问题形式相同的子问题。(2)解决(conquer)：若子问题规模较小，则直接求解；否则递归求解各子问题。(3)合并(combine)：将各子问题的解合并为原问题的解。它的一般算法设计范型如下：

DIVIDE&CONQUER(P)1if|P|≤c2thenreturn(DSOLVE(P))3elsedividePintokintoP1,P2,…,Pk

subproblems

4for

i←1tok5do

si←DIVIDE&CONQUER(Pi)6S←COMBINE(s1,s2,…,

sk)7returnS从分治法的一般设计模式可以看出，直接用它设计出的算法是一个递归算法。我们可用递归方程描述递归算法的运行时间。设T(n)表示用分治法求解规模为n的问题所需的计算时间，如果问题规模足够小，比如n≤c，则可直接求解问题，T(n)=Θ(1)。假定将原问题分为k个子问题，每一个子问题规模是原问题的1/m，若分解该问题和合并该问题的时间分别为D(n)和C(n)，则算法的计算时间T(n)可表示为如下的递归方程：n≤c

n>c

如果n为m的幂，分解该问题和合并该问题的时间为f(n)，则该递归方程的解为2.2.2二叉查找算法

已知一个按照非降序排列的n个元素列表a1，a2，…，an，要求判定某个给定元素v是否在该表中出现。如果元素v在表中出现，则找出v在表中的位置，表示查找成功；否则返回位置0，表示查找不成功。二叉查找(binarysearch)算法的基本思想是将n个元素分成大致相等的两部分，取A(［n/2］)与v进行比较，如果相等，则找到v，返回v所在位置，算法终止；如果v<A(［n/2］)，则在数组的左半部分继续查找v；如果v>A(［n/2］)，则在数组的右半部分继续查找v。当所查找的区间为0时，表示v不在数组中，返回查找不成功标志0。算法ITERATIVEBINARYSEARCH描述了上述思想。ITERATIVEBINARYSEARCH(A,v,low,high)1while

low≤high

2do

mid←［(low+high)/2］3if

v=A［mid］4thenreturn

mid

5elseifv>A［mid］6thenlow←mid+17else

high←mid-18returnNIL算法第1行检查待查找的区间，第2行计算待比较的元素位置。如果第3行中的Ｄ条件为真，则表示查找成功，返回元素所在位置；否则，或者在左半部分继续进行查找(执行第6行)，或者在右半部分进行查找(执行第7行)。如果第1行的while循环条件为假，则执行第8行，返回查找不成功标志0。算法ITERATIVEBINARYSEARCH在运行过程中，维持以下循环不变式：如果待查找的元素在数组中，则待查找元素必然在子数组中。在循环迭代开始时，子数组为输入原数组，循环不变式为真。在随后的各循环迭代步中，下一迭代步中是当前子数组中去掉不含v的那半部分数组后所剩余的部分，如果v在原数组中，则v必在下一迭代步中将要查找的子数组中，因此，在每一循环步中，不变式总为真。在每次迭代中，当A［mid］=v时，将返回下标mid；否则，子数组长度将减少一半多。因为原数组有有限个元素，循环必定在有限步内终止。因而，若算法终止于while循环(第4行)，则返回下标mid，循环不变式为真。若算法在第8行终止，则返回NIL，即待查找的元素不在原数组中。图2-6二叉判定树(n=12)为了理解二叉查找算法的运行过程，我们把它的执行想象成一棵二叉判定树(binarydecisiontree)的执行。下面以A=〈5，7，12，25，34，37，43，46，58，80，92，105〉为例来说明，如图2-6所示(图中n=12)。树中每一个结点表示一个元素在数组中的位置，也是算法运行过程中所有可能的mid值，结点外面的数值表示该元素的值。算法中所做的第一个元素比较是与A［6］进行的比较，如果待查找元素比A［6］小，则算法沿着左子树与A［3］比较；如果待查找元素比A［6］大，则算法沿着右子树与A［9］比较。通常称这种表示查找过程的二叉树为判定树。从判定树可见，查找元素25的过程恰好是走了一条从根结点到结点4的路径，和给定值25进行比较的元素个数为该路径上的结点数或结点4在判定树上的层数。因而，找到数组中任一元素的过程就是走了一条从根结点到该元素的路径，和给定值比较的元素个数恰为该结点在判定树上的层数。因此，二叉查找在查找成功时进行比较的元素个数最多不超过树的深度，而具有n个结点的判定树深度为［lbn］+1，所以，二叉查找在查找成功时进行比较的元素个数至多为［lbn］+1。如果在所有结点的空指针域上增加一个指向方形结点的指针，并称这些方形结点为判定树的外部结点，其中的数值表示待查找的元素可能值的范围，如58~80表示待查找的元素值在(58，80)之内，如图2-7所示，那么，二叉查找不成功的过程就是走了一条从根结点到外部结点的路径，和给定值进行比较的元素个数等于该路径上内部结点的个数，例如查找50的过程即为走了一条从根结点到结点46~58的过程。因此，二叉查找不成功时和给定元素比较的元素个数也至多为［lbn］+1。图2-7加上外部结点的二叉判定树假定在A中查找元素25、50，这分别是一次成功和一次不成功的查找。表2-1给出算法执行时变量low，high和mid的值。由表2-1可以得出，查找25进行3次元素比较，查找成功，返回元素在数组中的位置4。查找50进行4次元素比较，查找不成功，返回NIL。表2-1变量low，high和mid的运行轨迹我们对上述实例作进一步分析。如果以元素比较作为衡量算法的运行效率，由图2-7可知，查找12个元素中的每一个元素所需的比较次数如表2-2所示。表2-2元素的比较次数要找到一个元素至少要比较1次，至多比较4次。对找到所有12项的比较次数取平均值，可得到每一次成功查找的比较次数为37/12≈3.08。不成功查找的终止方式取决于v的值，总共有13种可能的情况，即v<A［1］，A［1］<v<A［2］，A［2］<v<A［3］，A［3］<v<A［4］A［4］<v<A［5］，A［5］<v<A［6］，A［6］<v<A［7］，A［7］<v<A［8］A［8］<v<A［9］，A［9］<v<A［10］，A［10］<v<A［11］，A［11］<v<A［12］因此，一次不成功查找元素所需的比较次数为假定有序表的长度为n=2h-1，则二叉查找判定树是深度为h的满二叉树。树的第i层有2i-1个结点。假设数组中每个元素的查找概率相等(Pi=1/n)，则查找成功时，二叉查找的平均查找长度ASL(AverageSearchLength)为因此，ASL=O(lbn)。

由此可见，二叉查找的效率比顺序查找高，但二叉查找只适用于有序表，且限于顺序存储结构。2.3分治法应用实例2.3.1找最大值与最小值

在含有n个不同元素的集合中同时找出它的最大值和最小值(maximum&minimum)的最简单方法是将元素逐个进行比较。算法中用max和min分别表示最大值和最小值。算法描述如下：MAXMIN(A)1max←min←A［1］2for

i←2to

n

3 doif

A［i］>max

4then

max←A［i］5elseif

A［i］<min

6then

min←A［i］7return

max&min

如果数组中元素按照递增的次序排列，则找出最大值和最小值所需的元素比较次数为n-1，这是最佳的情况。如果数组中元素按照递减的次序排列，则找出最大值和最小值所需的元素比较次数为2(n-1)，这是最坏情况。在平均情况下，A中将有一半元素使得第3行的比较为真，找出最大值和最小值所需的元素比较次数为3(n-1)/2。如果我们将分治策略用于此问题，每次将问题分成大致相等的两部分，分别在这两部分中找出最大值与最小值，再将这两个子问题的解组合成原问题的解，就可得到该问题的分治算法。算法描述如下：REC-MAXMIN(i，j，fmax，fmin)1ifi=j

2

thenfmax←fmin←A［i］3if

i=(j-1)4thenif

A［i］>A［j］5then

fmax←A［i］6

fmin←A［j］7else

fmax

←A［j］8

fmin←A［i］9else

mid←［(i+j)/2］10REC-MAXMIN(i，mid，gmax，gmin)11REC-MAXMIN(mid+1，j，

hmax，hmin)12

fmax←max{gmax，hmax}13

fmin←min{gmin，hmin}设T(n)表示算法所需的元素比较次数，则可得算法的递归方程为n=1n=2n>2假设n为2的幂，化简T(n)可得n=1n=2n>2T(n)=2T(n/2)+2=2(2T(n/4)+2)+2=4T(n/4)+4+2……=2k-1T(2)+=2k-1+2k-2=3n/2-2这表明算法的最坏、平均以及最好情况的元素比较次数为3n/2-2。事实上，至多进行3［n/2］次比较是找出最小值和最大值的充分条件。策略是维持到目前为止找到的最小值和最大值。我们并不将每个元素与最大值和最小值都进行比较，因为这样每个元素需要进行两次比较。下面我们成对处理元素。首先，输入元素成对相互进行比较，并将较小者与当前最小值比较，较大者与当前最大值比较。这样每两个元素进行三次比较。设置当前最小元素和最大元素的初始值，与n的奇偶性有关。当n为奇数时，我们将最小值和最大值都设为第一个元素，然后，将其余元素成对处理；当n为偶数时，我们在前两个元素之间进行一次比较，决定最大值和最小值的初始值，然后，将其余元素成对处理。以下分析上述算法的比较次数。如果n为奇数，那么需进行3［n/2］次比较；如果n为偶数，我们首先在前两个元素之间进行一次比较，然后进行3(n-2)/2次比较，总共进行3n/2-2次比较。因此，不论在哪一种情况下，比较的次数至多为3［n/2］可以证明，任何基于比较的找最大值和最小值的算法，其元素比较次数下界为［3n/2］-2［18］。在这种意义下，算法REC-MAXMIN是最优的。但是REC-MAXMIN也有其不足之处，它所要求的存储空间较大，即算法中的每次递归调用都需要保留i，j，fmax，fmin的值及返回地址。2.3.2Strassen矩阵乘法矩阵乘法是科学计算中最基本的问题之一。设A和B是两个n×n的矩阵，它们的乘积C=AB也是一个n×n的矩阵。其中乘积矩阵中的元素cij定义为由此可得，计算矩阵C中的每个元素需要n次乘法和n-1次加法。因此，计算矩阵C的n2个元素所需的时间为O(n3)。假设n为2的幂，运用分治策略，将矩阵分成4块大小相等的子矩阵，每个子矩阵 的方阵。矩阵乘积C=AB可重写为其中：C11=A11B11+A12B21

C12=A11B12+A12B22

C21=A21B11+A22B21

C22=A21B12+A22B22如果子矩阵的规模大于2，则可以继续划分这些子矩阵，直至每个矩阵变成2×2的矩阵。对于2×2的矩阵的计算，只需8次乘法和4次减法，计算时间为O(1)。设T(n)表示两个n×n矩阵相乘所需的计算时间，则由Cij(i，j=1，2)的计算可以看出，可将T(n)的计算转化为计算8个 的矩阵相乘和4个矩阵相加，而计算 矩阵加法所需时间为O(n2)，可得n=2n>2该递归方程符合主定理的第一种情形，其解为T(n)=O(nlb8)=O(n3)。因此，直接的分治策略并没有降低算法的计算复杂度。1969年，Strassen经过对问题的分析，在分治策略的基础上，通过数学技巧，使算法的计算复杂度从O(n3)降到了O(n2.81)。当此结果第一次发表时，震动了数学界。在Strassen矩阵相乘(Strassenmatrtrixmultiplication)算法中，只用了7个 的矩阵相乘，但增加了10个矩阵加、减法运算。这7个矩阵乘法是：P=(A11+A22)(B11+B22)Q=(A21+A22)B11

R=A11(B12-B22)S=A22(B21-B11)T=(A11+A12)B22

U=(A21-A11)(B11+B12)V=(A12-A22)(B21+B22)然后，再通过8个矩阵的加、减法运算来计算Cij的值(i，j=1，2)。C11=A11B11+A12B21=P+S-T+V

C12=A11B12+A12B22=R+T

C21=A21B11+A22B21=Q+S

C22=A21B12+A22B22=P+R-Q+U

在Strassen的分治算法中，用了8个的矩阵相乘和4个 矩阵相加。因此，算法所需的计算时间满足如下递归方程：n=2n>2该递归方程仍然符合主定理的第一种情形，其解为T(n)=O(nlb7)≈O(n2.81)。因此，Strassen矩阵乘法的计算时间较之前面讨论的矩阵乘法有所改进。继Strassen算法之后，许多科研人员致力于该问题的研究，希望对此结果有所改进。但J.E.Hopcroft和L.R.Kerr［19］已经证明了两个2×2矩阵相乘必须用7次乘法，因此，要进一步改进矩阵相乘的时间复杂度，就要考虑3×3或4×4等更大一级的分块，或者采用新的设计思想。2.3.3整数相乘

两个n位整数相乘(integermultiplication)的标准算法所需计算时间为Θ(n2)。算法是如此的自然，以至于我们可能会觉得没有更好的算法了。在这里，我们却要通过分治策略向大家展示一种确实存在的更好的算法。采用分治法，将x和y都分成两部分：x=10n/2a+b,y=10n/2c+d，那么x与y的乘积可表示为如下的式子：xy=10nac+10n/2(ad+bc)+bd假设两个n/2位的整数相乘不进位，如果按照上式计算xy的乘积，要做4次两个n/2位的乘法，即ac、ad、bc和bd，此外还要做2次移位(对应于式中的10n和10n/2)和3次不超过2n位的整数加法，所有这些移位和加法所需计算时间为O(n)。

设T(n)表示两个n位的整数相乘所需的计算时间，则n=1n>1其中，4T(n/2)表示需要解4个规模为n/2的子问题，O(n)表示利用移位和加法将子问题解组合成原问题解的时间。该递归方程符合主定理的第一种情形，其解为T(n)=O(nlb4)=O(n2)不幸的是，算法效率仍然没有得到提高。这里的关键是分割产生的4个子问题有些多。能否像在Strassen算法中所做的那样，通过一些技巧，或者说通过提高计算的效率，减少子问题的数量。答案是肯定的。不需分别计算ad和bc，而只需计算它们的和ad+bc。注意下式：(a+b)(c+d)=(ad+bc)+(ac+bd)如果计算出ac、bd和(a+b)(c+d)，那么可以从(a+b)(c+d)减去ac和bd得到ac+bd的值，即ac+bd=(a+b)(c+d)-ac-bd。当然，增加了一些加法运算，但却使得计算规模为n/2的子问题的乘法减少了一个。递归方程为n=1n>1上述描述的整数相乘算法可用于小数相乘和二进制乘法。我们用下面的例子说明这个方法。设x=3141，y=5927，则a=31，b=41，c=59，d=27u=(a+b)(c+d)=72×86=6192v=ac=31×59=1829w=bd=41×27=1107xy=18290000+(6192-1829-1107)×100+1107=18616707xy中的第一项是将v的小数位置右移4位得到的，中间项是将u-v-w的小数位置右移2位得到的。2.3.4归并排序

归并排序(mergesorting)是分治法应用的另一个实例，由以下三步组成：(1)划分：将待排序n个元素的序列划分成两个规模为n/2的子序列。(2)解决：用归并排序递归地对每一子序列排序。(3)合并：归并两个有序序列，得到排序结果。当划分的子序列规模为1时，递归结束。因为一个元素的序列被认为是有序的。

1．归并算法及其运行时间

归并排序的关键操作是归并两个已排序的子序列的过程。用过程MERGE(A，p，q，r)表示归并两个有序序列A［p..q］和A［q+1..r］。当过程MERGE(A，p，q，r)执行完成后，A［p..r］中包含的元素有序。过程MERGE(A，p，q，r)描述如下：MERGE(A,p,q,r)1n1←q-p+12n2←r-q

3createarraysL［1..n1+1］andR［1..n2+1］4fori←1to

n1

5do

L［i］←A［p+i-1］6for

j←1to

n2

7do

R［j］←A［q+j］8L［n1+1］←∞9R［n2+1］←∞//设置观察哨10i←111j←112for

k←p←to

r

13doif

L［i］<R［j］14then

A［k］←L［i］15i←i+116elseA［k］←R［j］17j←j+1现在需要证明，在第12~17行的for循环开始执行之前，这个循环不变式成立，并在循环的每次迭代过程中，循环不变式保持。当循环终止时，循环不变式还可以提供证明算法正确性的有用性质。·初始：在循环的第一次迭代之前，k=p，子数组A［p..k-1］为空。空数组包含k-p(=0)个L和R中的最小元素。由于i=j=1，因此L［i］和R［j］分别是各自数组中还未拷贝到A中的最小元素。·维持：为证明每次迭代过程维持不变式，我们首先假定L［i］≤R［j］。L［i］是没有拷贝到A中的最小元素。因为A［p..k-1］包含k-p个最小元素，在执行第14行后，L［i］被拷贝到A［k］，子数组A［p..k］包含k-p+1个最小元素。在for循环更新中k增加，执行第15行时i增加，重新建立下一次迭代的循环不变式。如果L［i］>R［j］，那么第16~17行执行维持循环不变式的相应行为。·终止：终止时，k=r+1。由循环不变式，子数组A［p..k-1］，即A［p..r］，包含L［1..n1+1］和R［1..n2+1］中的k-p=r-p+1个最小元素，且有序。数组L和R共有n1+n2+2=r-p+3个元素。除了L和R中两个最大的元素，其他所有元素都已拷贝到A中。这两个元素是观察哨。现在分析MERGE算法的时间复杂度。第1~3行和第8~11行需要常量时间，第4~7行的for循环需要Θ(n1+n2)=Θ(n)时间。第12~17行的for循环需要n次迭代，每次花费常量时间。因此MERGE过程的运行时间为Θ(n)。

2．归并算法示例

图2-8表示归并过程MERGE作用于子数组〈2,4,5,7,1,2,3,6〉上执行第10~17行的过程。调用归并过程MERGE时，参数p、q和r的值分别为9、12和16。图2-8调用MERGE(A,9,12,16)时第10~17行的运行过程图2-8调用MERGE(A,9,12,16)时第10~17行的运行过程3．归并排序算法我们将利用MERGE作为排序算法的子过程，利用MERGE-SORT对子数组A［p..r］中的元素进行排序。如果p≥r，则子数组至多有一个元素，因而有序；否则第2行计算下标q，将数组A［p..r］划分成两个子数组A［p..q］和A［q+1..r］，它们分别包含［n/2］和［n/2］个元素。MERGESORT(A,p,r)1ifp<r

2thenq←［(p+r)/2］3MERGE-SORT(A,p,q)4MERGE-SORT(A,q+1,r)5MERGE(A,p,q,r)算法通过两个长为1的子序列形成长为2的有序序列，再通过两个长为2的有序序列形成长为4的有序序列，直到通过两个长为n/2的有序序列形成长为n的有序序列。初始时调用MERGE-SORT(A,1,length［A］)，其中length［A］=n。设A=〈5,2,4,7,1,3,2,6〉，图2-9说明了MERGE-SORT排序的过程。MERGESORT(〈5,2,4,7,1,3,2,6〉,1,8)MERGESORT(〈5,2,4,7〉,1,4)MERGESORT(〈5,2〉,1,2)MERGESORT(〈5〉,1,1)MERGESORT(〈2〉,2,2)MERGE(〈2,5〉,1,1,2)MERGESORT(〈4,7〉,3,4)MERGESORT(〈4〉,3,3)MERGESORT(〈7〉,4,4)MERGE(〈4,7〉,3,3,4)MERGE(〈2,4,5,7〉,1,2,4)MERGESORT(〈1,3,2,6〉,5,8)MERGESORT(〈1,3〉,5,6)MERGESORT(〈1〉,5,5)MERGESORT(〈3〉,6,6)MERGE(〈1,3〉,5,5,6)MERGESORT(〈2,6〉,7,8)MERGESORT(〈2〉,7,7)MERGESORT(〈6〉,8,8)MERGE(〈2,6〉,7,7,8)MERGE(〈1,2,3,6〉,5,6,8)MERGE(〈1,2,2,3,4,5,6,7〉,1,4,8)图2-9MERGE-SORT排序的过程

4．归并排序算法的复杂度分析

设T(n)表示规模为n的问题的运行时间，为了简化以下对于递归方程的分析，设n为2的幂。归并排序每次的划分步产生规模为n/2的两个子问题。对于一个元素排序需要常量时间Θ(1)。按照分治算法的三个步骤，归并排序分为(1)划分：划分步计算数组的中点，这需要常量时间Θ(1)。(2)解决：递归求解两个规模为n/2的子问题，运行时间为2T(n/2)。(3)组合：组合过程对两个规模为n/2的子问题进行归并，时间为Θ(n)。由以上分析可知n=1n>1(2.2)该递归方程符合主定理的第二种情形，即Θ(nlogba)=Θ(nlb2)=Θ(n)=f(n)，其解为T(n)=Θ(nlb2lbn)=Θ(nlbn)由于对数函数要比线性函数增长慢，因此，归并排序最坏情况下的时间复杂度Θ(nlbn)要优于冒泡排序最坏情况下的时间复杂度Θ(n2)。图2-10递归树构造(T(n)=2T(n/2)+cn)2.3.5快速排序1．快速排序算法

快速排序就像归并排序一样，基于分治算法设计范型，由以下三步组成：(1)划分：将数组A［p..r］划分成两个子数组A［p..q-1］和A［q+1..r］(其中之一可能为空)，满足数组A［p..q-1］中的每个元素值不超过数组A［q+1..r］中的每个元素。计算下标q作为划分过程的一部分。(2)解决：递归调用快速排序算法，对两个子数组A［p..q-1］和A［q+1..r］进行排序。(3)组合：由于子数组中元素已被排序，无需组合操作，整个数组A［p..r］有序。以下是实现快速排序的QUICKSORT过程。QUICKSORT(A,p,r)1if

p<r

2thenq←PARTITION(A,p,r)3QUICKSORT(A,p,q-1)4QUICKSORT(A,q+1,r)初始时，调用QUICKSORT(A,1,length［A］)。算法的关键之处在于划分过程PARTITION，如果不计所用栈的空间，快速排序所需空间为O(1)。PARTITION(A,p,r)1x←A［r］//最右端元素作为枢轴元素2i←p-13for

j←p

to

r-14doif

A［j］≤x

5then

i←i+16exchangeA［i］A［j］7exchangeA［i+1］A［r］8returni+1图2-11显示了8个元素的PARTITION运行过程。PARTITION总是选择元素x=A［r］作为枢轴元素(pivotelement)，对数组A［p..r］进行划分。当过程运行时，数组被划分成4个区域(可能为空)。图2-11PARTITION运行过程在第3~6行循环的每次迭代的开始，对于任一下标k，(1)如果

p≤k≤i，那么A［k］≤x；(2)如果i+1≤k≤j-1，那么A［k］>x；(3)如果k=r，那么A［k］=x。图2-12划分的四个区域对于子数组A［p..r］，在A［p..i］中的值小于等于x，在A［i+1..j-1］中的值大于x，A［r］=x。A［j..r-1］可取任意值。我们证明循环不变式在第一次迭代之前成立，在循环的每次迭代中保持，并利用循环不变式证明算法终止时的正确性。·初始：在循环的第一次迭代之前，i=p-1，j=p。p和i之间没有值，i+1和j-1之间没有值，因此循环前两个条件平凡成立。第1行的赋值满足性质(3)。·维持：参照图2-13，考虑两种情况。与第4行的判断条件有关。图2-13(a)表示A［j］>x

的情况，循环中惟一要做的是使变量j增加。变量j值增加后，条件(2)对A［j-1］成立。所有其它元素保持不变。图2-13(b)表示A［j］≤x的情况，变量i增加，交换A［i］和A［j］，然后j增加。由于交换，使得A［i］≤x成立，条件(1)得到满足。类似地，由循环不变式，被交换进入A［j-1］的项大于x，即A［j-1］>x。图2-13过程PARTITION迭代的两种情况·终止：终止时，j=r。于是，数组中的每个元素位于不变式描述的三个集合之一，并把数组中的元素值划分成三个集合，即小于等于x的集合，大于x的集合，只含x的孤集。过程PARTITION的最后两行将枢轴元素与最左边大于x的元素交换，将其放在数组的中间。PARTITION的输出满足划分步给出的规范。它在数组A［p..r］上的运行时间为Θ(n)，其中n=r-p+1。证明留作习题。快速排序的运行时间与划分是否平衡有关，而是否平衡又取决于所用的划分元素。如果划分平衡，算法的渐近运行时间与归并排序一样；如果划分不平衡，则它的运行时间和冒泡排序一样，都为O(n2)。以下研究三种不同划分的情况下快速排序算法的性能。

2．快速排序最坏情况分析

当划分过程产生的两个子问题规模分别为n-1和0时，快速排序出现最坏的情况。假设每次递归调用时产生这种不平衡的情况。划分的时间复杂度为Θ(n)，因为对规模为0的数组的递归调用只会返回，T(0)=Θ(1)，递归方程的运行时间为T(n)=T(n-1)+T(0)+Θ(n)=T(n-1)+Θ(n)直觉地，如果我们对递归每一层的开销求和，就得到一个算术级数，其和为Θ(n2)。也可以利用替换方法证明递归方程T(n)=T(n-1)+Θ(n)的解为Θ(n2)。因而，如果划分在算法的每一层递归上产生最大不平衡，则运行时间为Θ(n2)。因此，快速排序最坏情况下的运行时间不比冒泡排序的运行时间好，而最坏情况是在输入已经完全有序(升序)时出现的。

3．快速排序最好情况分析

在大多数均匀划分的情况下，PARTITION产生两个规模不超过n/2的子问题，其中一个规模为［n/2］，另一个规模为［n/2］-1。在这种情况下，快速排序运行更快。此时，递归方程为T(n)≤2T(n/2)+Θ(n)由主定理的第2种情形，a=2，b=2，nlogba=nlb2=Θ(n)=f(n)，可知递归方程的解为T(n)=O(nlbn)。因此，如果划分在算法的每一层递归上产生两个相同规模的问题，则得快速排序算法的最佳情况。

4．快速排序平均情况分析

快速排序算法的平均情况分析更类似于最佳情况分析，关键在于要理解平衡划分是如何反映描述运行时间的递归方程的。假定划分算法总是产生9∶1的划分比例，这似乎是相当不平衡的。快速排序的递归方程表示如下：T(n)≤T(9n/10)+T(n/10)+cn图2-14表示这个递归方程的递归树。图2-14划分比例为99∶1时的快速排序递归树当我们在随机输入数组上运行快速排序时，每一次的划分并不总是一样的。我们期望某些划分合理地平衡，然而某些划分却相当不平衡。例如，大约80%的PARTITION过程产生平衡大于9∶1，而大约20%的PARTITION过程产生平衡小于9∶1。在平均情况下，PARTITION过程产生的划分既有“好”也有“坏”。在PARTITION过程平均情况执行的递归树中，好坏的情况随机地分布在递归树中。假定好坏的情况在树中交替出现，并且好的情况就是最佳情况，坏的情况就是最坏情况。图2-15表示递归树中两个连续层的划分。在树根结点，划分开销为n，产生两个规模分别为n-1和0的划分，这是一种最坏情况。在下一层，对规模为n-1的子数组进行最佳划分，产生两个规模分别为(n-1)/2和(n-1)/2的子数组。假设规模为0的子数组，其边界条件开销为1。图2-15快速排序的两层递归树椭圆形区域表示子问题的划分开销，都为Θ(n)。在图2-15(a)中所剩下要解的子问题(方形阴影区域)不会大于图2-15(b)中所剩下要解的子问题。在图2-15(a)中，将划分产生的三个规模分别为0、(n-1)/2-1、(n-1)/2的子数组组合，总开销为Θ(n)+Θ(n-1)=Θ(n)肯定地说，这种情况不会比图2-15(b)中的平衡划分坏，即产生两个规模为(n-1)/2的某层划分，其开销为Θ(n)。而后者的情形是平衡的！从直觉上来看，坏的划分Θ(n-1)可以被吸收进好划分的Θ(n)中，导致最终划分结果是好的。因此，快速排序的运行时间，当好的划分与坏的划分在树的层次间交替进行时，就像都是好的划分结果一样，仍然为O(nlbn)，但是隐含在大O中的常数因子较大。2.3.6线性时间选择

1．期望线性时间的选择

一般的选择问题要比找最小值问题更难，然而令人惊讶的是这两个问题具有相同的渐近运行时间O(n)。我们仍然利用分治策略解决选择问题。我们利用前面提到的PARTITION过程，但需要做一些修改，这是因为PARTITION过程假定所有输入元素的排列出现概率相同，但在实际情况中这种假定并不总是能够成立。我们在算法中引入随机化，以便更好地研究选择问题平均情况下的性能。修改后的划分过程如下：RANDOMIZEDPARTITION(A,p,r)1i←RANDOM(p,r)2exchangeA［r］A［i］3returnPARTITION(A,p,r)RANDOMIZED-SELECT利用过程RANDOMIZED-PARTITION作为子过程。以下过程RANDOMIZED-SELECT返回数组A［p..r］中的第i个最小元素。RANDOMIZED-SELECT(A,p,r,i)1ifp=r

2thenreturnA［p］3q←RANDOMIZED-PARTITION(A,p,r)4k←q-p+15ifi=k//枢轴元素为所求结果6thenreturn

A［q］7elseif

i<k

8thenreturnRANDOMIZED-SELECT(A,p,q-1,i)9elsereturnRANDOMIZED-SELECT(A,q+1,r,i-k)设T(n)表示RANDOMIZEDSELECT算法在输入为A［p..r］时的运行时间，这是一个随机变量。我们以下导出E［T(n)］的上界。过程RANDOMIZED-PARTITION以等概率返回任一元素作为枢轴元素。因此，对于满足1≤k≤n的每个k，子数组A［p..q］有k个元素(都小于等于枢轴元素)概率为1/n。对于k=1,2,…,n，我们定义指示器随机变量Xk为Xk=I{子数组A［p..q］只有k个元素}且E［Xk］=1/n

当我们调用RANDOMIZED-SELECT并选择A［q］作为枢轴元素时，预先并不知道是否可以很快以正确解终止，在子数组A［p..q-1］上递归，还是在子数组A［q+1..r］上递归是与枢轴元素A［q］有关的。假设T(n)单调递增，我们分析在最大可能输入的情况下递归调用所需的时间。换句话说，就是得到一个上界。第i个元素总是在具有最大个数的那个划分中。对于给定的调用RANDOMIZED-SELECT，指示器随机变量Xk在只有一个k值时为1；其他所有k值时则为0。当Xk=1时，我们可能递归调用的两个子数组大小分别为k-1和n-k。因此，递归方程为两边取期望值，则得其中Xk和T(max(k-1,n-k))是独立的随机变量。考虑表达式max(k-1,n-k)，则有如果n为偶数，在求和算式中，从T(［n/2］)到T(n-1)中的每一项只出现两次；如果n为奇数，所有这些项出现两次，T(［n/2］)出现一次。因此，用替换方法解此方程。假设对于满足递归方程初始条件的某些常数c，T(n)≤cn,且当n≤n0时，T(n)=O(1)，其中n0为足够小的整数。我们稍后选择这个常数n。同时，还要选择式(2.3)中O(n)项隐含的常数a，使得对于所有n>0，O(n)≤an。利用归纳假设需要证明，对于足够大的n，最后的表达式至多为cn，或cn/4-c/2-an≥0。该不等式两边加上c/2且提出公因子n，可得n(c/4-a)≥c/2。只要选择常数c满足c/4-a>0，即c>4a，我们用c/4-a去除两边，得因此，选择c>4a，n0=2c/(c-4a)。假设当n≤n0时，T(n)=O(1)，可得T(n)=O(n)。因此，对于任意顺序统计量，尤其是中值的计算，平均情况下线性即可决定。2．最坏情况线性时间的选择

以下介绍一种最坏情况下运行时间为O(n)的选择算法SELECT。算法SELECT是一递归算法，基本思想是对数组划分时，保证产生好的分割。算法中仍然用快速排序中使用过的确定划分算法PARTITION，但用划分元素作为输入参数。SELECT算法描述如下：

SELECT1将n个输入元素分成［n/5］个组，每组5个元素，另一组由剩余的nmod5个元素组成。2利用插入排序算法对［n/5］个组进行排序，并找出每组元素的中值。3对于第2步中找出的［n/5］个中值，利用SELECT递归算法找出这［n/5］个中值的中值x。4利用修改的PARTITION过程，以中值的中值x作为划分元素，对输入数组进行划分。设k是划分后左半部分元素数再加上1。因此，x是第k个最小元素，且右半部分有n-k个元素。5如果i=k，则返回x；如果i<k，则利用SELECT在划分的左半部分找第i个最小元素；如果i>k，则在右半部分找第i-k个最小元素。为了分析SELECT的运行时间，我们首先确定大于划分元素x的元素个数。图2-16可视化说明了划分元素的选择过程。小圆圈表示n个元素。每列表示一组，每组中的中值用浅灰色表示，中值的中值已标示出。箭头表示从大元素到小元素，由此可见，x右边的5个元素的每个组中，每组有3个元素大于x，x左边的5个元素的每个组中，每组有3个元素小于x。阴影背景中的元素比x大。图2-16SELECT算法分析在算法SELECT第2步所找到的中值中，至少有一半大于x。因此，［n/5］组中至少有一半的小组有3个元素大于x，除了元素不足5个的组(如果n不能被5整除)以及包括x自身的那个组。减去这两个组，则大于x的元素个数至少为类似地我们可