算法設計與分析(霍紅衛(wèi))-第2章-分治法

第2章分治法2.1遞歸與遞歸方程2.2分治法2.3分治法應用實例2.1遞歸與遞歸方程2.1.1遞歸的概念遞歸(recursion)是數(shù)學與計算機科學中的基本概念。程序設計語言中的遞歸程序可被簡單地定義為對自己的調(diào)用。遞歸程序不能總是自我調(diào)用，否則就會永不終止。此外，遞歸程序必須有終止條件。盡管遞歸程序在執(zhí)行時間上往往比非遞歸程序要付出更多的代價，但有很多問題的數(shù)學模型或算法設計方法本來就是遞歸的，用遞歸過程來描述它們不僅非常自然，而且證明該算法的正確性要比相應的非遞歸形式容易得多，因此遞歸不失為一種強有力的程序設計方法。

例2.1斐波那契(Fibonacci)序列。無窮數(shù)列1，1，2，3，5，8，13，21，34，…可定義為斐波那契數(shù)列。遞歸形式為從這一數(shù)學定義可以自然地導出遞歸的斐波那契過程F(n)。F(n)1Ifn≤12

thenreturn13return

F(n-1)+F(n-2)圖2-1斐波那契算法的遞歸結(jié)構(gòu)(n=6)

例2.2歐幾里得(Euclid)算法。歐幾里得算法是兩千年來最著名的算法之一：已知兩個非負整數(shù)m，n，且m>n>0，求這兩個數(shù)的最大公因子。歐幾里得得出本算法基于這樣一種觀察，兩個整數(shù)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上，并按照同樣順序放置。圓盤移動時，滿足以下規(guī)則：①一次只能移動一個圓盤；②任何時刻不允許將大的圓盤放在小的圓盤之上；③圓盤可以放在X、Y和Z的任一塔座上。我們可以用遞歸解決這個問題。其中遞歸是基于這樣的一個想法：當n=1時，只要將編號為1的圓盤從塔座X直接移到塔座Z上即可；當n>1時，利用Z作中間塔座，依照上述規(guī)則，將編號為n的圓盤上的n-1個圓盤從塔座X移到塔座Y上，再將X上編號為n的圓盤直接移到塔座Z上，最后，以X作中間塔座，將塔座Y上的n-1個圓盤從塔座Y移到塔座Z上。而對于n-1個圓盤的移動是一個和原問題具有相同特征的子問題，可用同樣方法求解。因此，規(guī)模為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個圓盤按照規(guī)則移到塔座Z上，以Y作中間塔座。HANOI(n-1，X，Z，Y)表示將塔座X上編號為1~n-1的n-1個圓盤按照規(guī)則移到塔座Y上，以Z作中間塔座。HANOI(n-1，Y，X，Z)表示將塔座Y上編號為1~n-1的n-1個圓盤按照規(guī)則移到塔座Z上，以X作中間塔座。MOVE(X，n，Z)表示將編號為n的圓盤從塔座X移到塔座Z上。遞歸過程在實現(xiàn)時，可用一個等價的遞歸棧實現(xiàn)過程的嵌套調(diào)用。遞歸的深度就是在整個計算中過程嵌套調(diào)用的最大程度。通常，深度取決于輸入規(guī)模。因此，對于大型問題，棧所需的空間可能妨礙我們使用遞歸方法求解。圖2-3表示n=4時漢諾塔算法的運行過程。圖2-3漢諾塔的執(zhí)行過程(n=4)漢諾塔算法的時間復雜度為指數(shù)級的復雜度。以下做一簡要證明。假設漢諾塔算法的時間復雜度為T(n)，由遞歸算法可得n=1n>1不失一般性，設n為2的冪。由數(shù)學歸納法容易得出，該遞歸方程的解為2n-1，即O(2n)。

從上述例子可見，當算法包含調(diào)用自身的過程時，其運行時間可用遞歸方程(recurrenceequation)描述。本節(jié)介紹三種求解遞歸方程的方法。這三種方法分別是替換方法(substitutionmethod)、遞歸樹方法(recursiontreemethod)和主方法(mastermethod)。2.1.2替換方法

例2.4利用替換方法解遞歸方程T(n)=2T(［n/2］)+n。

解我們猜測其解為T(n)=O(nlbn)。假設這個界限對于［n/2］成立，即存在某個常數(shù)c，T(［n/2］)≤c(［n/2］)lb(［n/2］)成立。現(xiàn)在要證明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時成立。下面證明猜測對于邊界條件成立，即證明對于選擇的常數(shù)c，T(n)≤cnlbn對于邊界條件成立。這個要求有時會產(chǎn)生一些問題。假設T(1)=1是遞歸方程的惟一邊界條件，那么對于n=1，T(1)≤c·1·lb1=0與T(1)=1發(fā)生矛盾。因此，歸納法中的歸納基礎不成立。我們可以很容易解決這個問題。利用這樣一個事實：漸近表示法只要求對n≥n0，T(n)≤cn

lbn成立，其中n0是一個可以選擇的常數(shù)。由于對于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成立。不幸的是，并不存在一般的方法來猜測遞歸方程的正確解。這種猜測需要經(jīng)驗，有時需要創(chuàng)造性。有時，一些看上去非常陌生的遞歸方程，在經(jīng)過一些簡單代數(shù)變換之后，就可以變?yōu)槲覀冚^熟悉的形式。例2.5解遞歸方程。

解設n=2m

或者m=lbn，則遞歸方程變?yōu)門(2m)=2T(2m/2)+1再做一次替換，設S(m)=T(2m)，則遞歸方程變?yōu)镾(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遞歸樹的構(gòu)造過程現(xiàn)在，我們確定樹中每一層的開銷。每一層的結(jié)點數(shù)是上一層結(jié)點數(shù)的兩倍，因此，第i層的結(jié)點數(shù)為3i。由于每一層子問題規(guī)模為上一層的1/4，由根向下，深度為i(i=0，1，…，log4n-1)的每個結(jié)點的開銷為c(n/4i)2，那么第i層上結(jié)點的總開銷為3ic(n/4i)2=(3/16)icn2

i=0，1，…，log4n-1深度為log4n的最后一層有 個結(jié)點，每個結(jié)點的開銷為T(1)，該層總開銷為 ，即 。將所有層的開銷相加得到整棵樹的開銷：現(xiàn)在利用替換方法證明我們的猜測是正確的。假設這個界限對于n/4成立，即存在某個常數(shù)d，T(n/4)≤d(n/4)2成立。代入遞歸方程可得只要選取d≥(16/13)c，最后一步成立。2.1.4主方法

主方法(mastermethod)為我們提供了解如下形式遞歸方程的一般方法。其中a≥1，b>1為常數(shù)，f(n)是漸近正函數(shù)。遞歸方程(2.1)描述了算法的運行時間，算法將規(guī)模為n的問題劃分成a個子問題，每個子問題的大小為n/b，其中a、b是正常數(shù)。求解這a個子問題，每個所需時間為T(n/b)。函數(shù)f(n)表示劃分子問題與組合子問題解的開銷。例如，對于遞歸方程T(n)=3T(n/4)+cn2，a=3，b=4，f(n)=Θ(n2)。

每個子問題n/b未必為整數(shù)，但用T(n/b)代替T(［n/b］)和T(［n/b］)并不影響遞歸方程的漸近行為，因此我們在表達這種形式的分治算法時將略去向下取整函數(shù)和向上取整函數(shù)。T(n)=aT(n/b)+f(n)(2.1)

定理2.1設a≥1，b>1為常數(shù)，f(n)為一函數(shù)。T(n)由以下遞歸方程定義：其中n為非負整數(shù)，則T(n)有如下的漸近界限：(1)若對某些常數(shù)ε>0，有f(n)=O(nlogba-ε)，那么T(n)=Θ(nlogba)。(2)若f(n)=Θ(nlogba)，那么T(n)=Θ(nlogbalbn)。(3)若對某些常數(shù)ε>0，有f(n)=Ω(nlogba+ε)，且對常數(shù)c<1與所有足夠大的n，有af(n/b)≤cf(n)，那么T(n)=Θ(f(n))。在運用該定理之前，我們先來分析它的含義。在上述的每一種情況下，我們都把函數(shù)f(n)與函數(shù)nlogba進行比較，遞歸方程的解由這兩個函數(shù)中較大的一個決定。例如，在第一種情形中，函數(shù)nlogba比函數(shù)f(n)更大，則解為T(n)=Θ(nlogba)在第二種情形中，這兩個函數(shù)一樣大，則解為T(n)=Θ(nlogbalbn)=Θ(f(n)lbn)在第三種情形中，f(n)是較大的函數(shù)，則解為T(n)=Θ(f(n))我們可用圖2-5表示方程(2.1)，從另一個角度解釋主定理。圖2-5主定理的圖示樹中葉子結(jié)點數(shù)為對于第一種情形，從根到葉結(jié)點開銷的權(quán)重呈幾何級數(shù)增加，T(n)=f(n)+af(n/b)+a2f(n/b2)+…+

nlogba

T(1)=Θ(nlogba)葉結(jié)點占有整個權(quán)重的恒定比例。對于第二種情形，每一層的權(quán)重大致相同，T(n)=f(n)+af(n/b)+a2f(n/b2)+…+

nlogba

T(1)=Θ(nlogba1bn)對于第三種情形，從根到葉結(jié)點開銷的權(quán)重呈幾何級數(shù)減小，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分治法的基本思想

對于一個規(guī)模為n的問題，若該問題可以容易地解決(比如說規(guī)模n較小)，則直接解決，否則將其分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并，得到原問題的解。這種算法設計策略叫做分治法(divideandconquer)。分治法在每一層遞歸上由三個步驟組成：(1)劃分(divide)：將原問題分解為若干規(guī)模較小、相互獨立、與原問題形式相同的子問題。(2)解決(conquer)：若子問題規(guī)模較小，則直接求解；否則遞歸求解各子問題。(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)表示用分治法求解規(guī)模為n的問題所需的計算時間，如果問題規(guī)模足夠小，比如n≤c，則可直接求解問題，T(n)=Θ(1)。假定將原問題分為k個子問題，每一個子問題規(guī)模是原問題的1/m，若分解該問題和合并該問題的時間分別為D(n)和C(n)，則算法的計算時間T(n)可表示為如下的遞歸方程：n≤c

n>c

如果n為m的冪，分解該問題和合并該問題的時間為f(n)，則該遞歸方程的解為2.2.2二叉查找算法

已知一個按照非降序排列的n個元素列表a1，a2，…，an，要求判定某個給定元素v是否在該表中出現(xiàn)。如果元素v在表中出現(xiàn)，則找出v在表中的位置，表示查找成功；否則返回位置0，表示查找不成功。二叉查找(binarysearch)算法的基本思想是將n個元素分成大致相等的兩部分，取A(［n/2］)與v進行比較，如果相等，則找到v，返回v所在位置，算法終止；如果v<A(［n/2］)，則在數(shù)組的左半部分繼續(xù)查找v；如果v>A(［n/2］)，則在數(shù)組的右半部分繼續(xù)查找v。當所查找的區(qū)間為0時，表示v不在數(shù)組中，返回查找不成功標志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行檢查待查找的區(qū)間，第2行計算待比較的元素位置。如果第3行中的Ｄ條件為真，則表示查找成功，返回元素所在位置；否則，或者在左半部分繼續(xù)進行查找(執(zhí)行第6行)，或者在右半部分進行查找(執(zhí)行第7行)。如果第1行的while循環(huán)條件為假，則執(zhí)行第8行，返回查找不成功標志0。算法ITERATIVEBINARYSEARCH在運行過程中，維持以下循環(huán)不變式：如果待查找的元素在數(shù)組中，則待查找元素必然在子數(shù)組中。在循環(huán)迭代開始時，子數(shù)組為輸入原數(shù)組，循環(huán)不變式為真。在隨后的各循環(huán)迭代步中，下一迭代步中是當前子數(shù)組中去掉不含v的那半部分數(shù)組后所剩余的部分，如果v在原數(shù)組中，則v必在下一迭代步中將要查找的子數(shù)組中，因此，在每一循環(huán)步中，不變式總為真。在每次迭代中，當A［mid］=v時，將返回下標mid；否則，子數(shù)組長度將減少一半多。因為原數(shù)組有有限個元素，循環(huán)必定在有限步內(nèi)終止。因而，若算法終止于while循環(huán)(第4行)，則返回下標mid，循環(huán)不變式為真。若算法在第8行終止，則返回NIL，即待查找的元素不在原數(shù)組中。圖2-6二叉判定樹(n=12)為了理解二叉查找算法的運行過程，我們把它的執(zhí)行想象成一棵二叉判定樹(binarydecisiontree)的執(zhí)行。下面以A=〈5，7，12，25，34，37，43，46，58，80，92，105〉為例來說明，如圖2-6所示(圖中n=12)。樹中每一個結(jié)點表示一個元素在數(shù)組中的位置，也是算法運行過程中所有可能的mid值，結(jié)點外面的數(shù)值表示該元素的值。算法中所做的第一個元素比較是與A［6］進行的比較，如果待查找元素比A［6］小，則算法沿著左子樹與A［3］比較；如果待查找元素比A［6］大，則算法沿著右子樹與A［9］比較。通常稱這種表示查找過程的二叉樹為判定樹。從判定樹可見，查找元素25的過程恰好是走了一條從根結(jié)點到結(jié)點4的路徑，和給定值25進行比較的元素個數(shù)為該路徑上的結(jié)點數(shù)或結(jié)點4在判定樹上的層數(shù)。因而，找到數(shù)組中任一元素的過程就是走了一條從根結(jié)點到該元素的路徑，和給定值比較的元素個數(shù)恰為該結(jié)點在判定樹上的層數(shù)。因此，二叉查找在查找成功時進行比較的元素個數(shù)最多不超過樹的深度，而具有n個結(jié)點的判定樹深度為［lbn］+1，所以，二叉查找在查找成功時進行比較的元素個數(shù)至多為［lbn］+1。如果在所有結(jié)點的空指針域上增加一個指向方形結(jié)點的指針，并稱這些方形結(jié)點為判定樹的外部結(jié)點，其中的數(shù)值表示待查找的元素可能值的范圍，如58~80表示待查找的元素值在(58，80)之內(nèi)，如圖2-7所示，那么，二叉查找不成功的過程就是走了一條從根結(jié)點到外部結(jié)點的路徑，和給定值進行比較的元素個數(shù)等于該路徑上內(nèi)部結(jié)點的個數(shù)，例如查找50的過程即為走了一條從根結(jié)點到結(jié)點46~58的過程。因此，二叉查找不成功時和給定元素比較的元素個數(shù)也至多為［lbn］+1。圖2-7加上外部結(jié)點的二叉判定樹假定在A中查找元素25、50，這分別是一次成功和一次不成功的查找。表2-1給出算法執(zhí)行時變量low，high和mid的值。由表2-1可以得出，查找25進行3次元素比較，查找成功，返回元素在數(shù)組中的位置4。查找50進行4次元素比較，查找不成功，返回NIL。表2-1變量low，high和mid的運行軌跡我們對上述實例作進一步分析。如果以元素比較作為衡量算法的運行效率，由圖2-7可知，查找12個元素中的每一個元素所需的比較次數(shù)如表2-2所示。表2-2元素的比較次數(shù)要找到一個元素至少要比較1次，至多比較4次。對找到所有12項的比較次數(shù)取平均值，可得到每一次成功查找的比較次數(shù)為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］因此，一次不成功查找元素所需的比較次數(shù)為假定有序表的長度為n=2h-1，則二叉查找判定樹是深度為h的滿二叉樹。樹的第i層有2i-1個結(jié)點。假設數(shù)組中每個元素的查找概率相等(Pi=1/n)，則查找成功時，二叉查找的平均查找長度ASL(AverageSearchLength)為因此，ASL=O(lbn)。

由此可見，二叉查找的效率比順序查找高，但二叉查找只適用于有序表，且限于順序存儲結(jié)構(gòu)。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

如果數(shù)組中元素按照遞增的次序排列，則找出最大值和最小值所需的元素比較次數(shù)為n-1，這是最佳的情況。如果數(shù)組中元素按照遞減的次序排列，則找出最大值和最小值所需的元素比較次數(shù)為2(n-1)，這是最壞情況。在平均情況下，A中將有一半元素使得第3行的比較為真，找出最大值和最小值所需的元素比較次數(shù)為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)表示算法所需的元素比較次數(shù)，則可得算法的遞歸方程為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這表明算法的最壞、平均以及最好情況的元素比較次數(shù)為3n/2-2。事實上，至多進行3［n/2］次比較是找出最小值和最大值的充分條件。策略是維持到目前為止找到的最小值和最大值。我們并不將每個元素與最大值和最小值都進行比較，因為這樣每個元素需要進行兩次比較。下面我們成對處理元素。首先，輸入元素成對相互進行比較，并將較小者與當前最小值比較，較大者與當前最大值比較。這樣每兩個元素進行三次比較。設置當前最小元素和最大元素的初始值，與n的奇偶性有關(guān)。當n為奇數(shù)時，我們將最小值和最大值都設為第一個元素，然后，將其余元素成對處理；當n為偶數(shù)時，我們在前兩個元素之間進行一次比較，決定最大值和最小值的初始值，然后，將其余元素成對處理。以下分析上述算法的比較次數(shù)。如果n為奇數(shù)，那么需進行3［n/2］次比較；如果n為偶數(shù)，我們首先在前兩個元素之間進行一次比較，然后進行3(n-2)/2次比較，總共進行3n/2-2次比較。因此，不論在哪一種情況下，比較的次數(shù)至多為3［n/2］可以證明，任何基于比較的找最大值和最小值的算法，其元素比較次數(shù)下界為［3n/2］-2［18］。在這種意義下，算法REC-MAXMIN是最優(yōu)的。但是REC-MAXMIN也有其不足之處，它所要求的存儲空間較大，即算法中的每次遞歸調(diào)用都需要保留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如果子矩陣的規(guī)模大于2，則可以繼續(xù)劃分這些子矩陣，直至每個矩陣變成2×2的矩陣。對于2×2的矩陣的計算，只需8次乘法和4次減法，計算時間為O(1)。設T(n)表示兩個n×n矩陣相乘所需的計算時間，則由Cij(i，j=1，2)的計算可以看出，可將T(n)的計算轉(zhuǎn)化為計算8個 的矩陣相乘和4個矩陣相加，而計算 矩陣加法所需時間為O(n2)，可得n=2n>2該遞歸方程符合主定理的第一種情形，其解為T(n)=O(nlb8)=O(n3)。因此，直接的分治策略并沒有降低算法的計算復雜度。1969年，Strassen經(jīng)過對問題的分析，在分治策略的基礎上，通過數(shù)學技巧，使算法的計算復雜度從O(n3)降到了O(n2.81)。當此結(jié)果第一次發(fā)表時，震動了數(shù)學界。在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算法之后，許多科研人員致力于該問題的研究，希望對此結(jié)果有所改進。但J.E.Hopcroft和L.R.Kerr［19］已經(jīng)證明了兩個2×2矩陣相乘必須用7次乘法，因此，要進一步改進矩陣相乘的時間復雜度，就要考慮3×3或4×4等更大一級的分塊，或者采用新的設計思想。2.3.3整數(shù)相乘

兩個n位整數(shù)相乘(integermultiplication)的標準算法所需計算時間為Θ(n2)。算法是如此的自然，以至于我們可能會覺得沒有更好的算法了。在這里，我們卻要通過分治策略向大家展示一種確實存在的更好的算法。采用分治法，將x和y都分成兩部分：x=10n/2a+b,y=10n/2c+d，那么x與y的乘積可表示為如下的式子：xy=10nac+10n/2(ad+bc)+bd假設兩個n/2位的整數(shù)相乘不進位，如果按照上式計算xy的乘積，要做4次兩個n/2位的乘法，即ac、ad、bc和bd，此外還要做2次移位(對應于式中的10n和10n/2)和3次不超過2n位的整數(shù)加法，所有這些移位和加法所需計算時間為O(n)。

設T(n)表示兩個n位的整數(shù)相乘所需的計算時間，則n=1n>1其中，4T(n/2)表示需要解4個規(guī)模為n/2的子問題，O(n)表示利用移位和加法將子問題解組合成原問題解的時間。該遞歸方程符合主定理的第一種情形，其解為T(n)=O(nlb4)=O(n2)不幸的是，算法效率仍然沒有得到提高。這里的關(guān)鍵是分割產(chǎn)生的4個子問題有些多。能否像在Strassen算法中所做的那樣，通過一些技巧，或者說通過提高計算的效率，減少子問題的數(shù)量。答案是肯定的。不需分別計算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。當然，增加了一些加法運算，但卻使得計算規(guī)模為n/2的子問題的乘法減少了一個。遞歸方程為n=1n>1上述描述的整數(shù)相乘算法可用于小數(shù)相乘和二進制乘法。我們用下面的例子說明這個方法。設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的小數(shù)位置右移4位得到的，中間項是將u-v-w的小數(shù)位置右移2位得到的。2.3.4歸并排序

歸并排序(mergesorting)是分治法應用的另一個實例，由以下三步組成：(1)劃分：將待排序n個元素的序列劃分成兩個規(guī)模為n/2的子序列。(2)解決：用歸并排序遞歸地對每一子序列排序。(3)合并：歸并兩個有序序列，得到排序結(jié)果。當劃分的子序列規(guī)模為1時，遞歸結(jié)束。因為一個元素的序列被認為是有序的。

1．歸并算法及其運行時間

歸并排序的關(guān)鍵操作是歸并兩個已排序的子序列的過程。用過程MERGE(A，p，q，r)表示歸并兩個有序序列A［p..q］和A［q+1..r］。當過程MERGE(A，p，q，r)執(zhí)行完成后，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現(xiàn)在需要證明，在第12~17行的for循環(huán)開始執(zhí)行之前，這個循環(huán)不變式成立，并在循環(huán)的每次迭代過程中，循環(huán)不變式保持。當循環(huán)終止時，循環(huán)不變式還可以提供證明算法正確性的有用性質(zhì)?！こ跏迹涸谘h(huán)的第一次迭代之前，k=p，子數(shù)組A［p..k-1］為空。空數(shù)組包含k-p(=0)個L和R中的最小元素。由于i=j=1，因此L［i］和R［j］分別是各自數(shù)組中還未拷貝到A中的最小元素?！ぞS持：為證明每次迭代過程維持不變式，我們首先假定L［i］≤R［j］。L［i］是沒有拷貝到A中的最小元素。因為A［p..k-1］包含k-p個最小元素，在執(zhí)行第14行后，L［i］被拷貝到A［k］，子數(shù)組A［p..k］包含k-p+1個最小元素。在for循環(huán)更新中k增加，執(zhí)行第15行時i增加，重新建立下一次迭代的循環(huán)不變式。如果L［i］>R［j］，那么第16~17行執(zhí)行維持循環(huán)不變式的相應行為?！そK止：終止時，k=r+1。由循環(huán)不變式，子數(shù)組A［p..k-1］，即A［p..r］，包含L［1..n1+1］和R［1..n2+1］中的k-p=r-p+1個最小元素，且有序。數(shù)組L和R共有n1+n2+2=r-p+3個元素。除了L和R中兩個最大的元素，其他所有元素都已拷貝到A中。這兩個元素是觀察哨?，F(xiàn)在分析MERGE算法的時間復雜度。第1~3行和第8~11行需要常量時間，第4~7行的for循環(huán)需要Θ(n1+n2)=Θ(n)時間。第12~17行的for循環(huán)需要n次迭代，每次花費常量時間。因此MERGE過程的運行時間為Θ(n)。

2．歸并算法示例

圖2-8表示歸并過程MERGE作用于子數(shù)組〈2,4,5,7,1,2,3,6〉上執(zhí)行第10~17行的過程。調(diào)用歸并過程MERGE時，參數(shù)p、q和r的值分別為9、12和16。圖2-8調(diào)用MERGE(A,9,12,16)時第10~17行的運行過程圖2-8調(diào)用MERGE(A,9,12,16)時第10~17行的運行過程3．歸并排序算法我們將利用MERGE作為排序算法的子過程，利用MERGE-SORT對子數(shù)組A［p..r］中的元素進行排序。如果p≥r，則子數(shù)組至多有一個元素，因而有序；否則第2行計算下標q，將數(shù)組A［p..r］劃分成兩個子數(shù)組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的有序序列。初始時調(diào)用MERGE-SORT(A,1,length［A］)，其中l(wèi)ength［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)表示規(guī)模為n的問題的運行時間，為了簡化以下對于遞歸方程的分析，設n為2的冪。歸并排序每次的劃分步產(chǎn)生規(guī)模為n/2的兩個子問題。對于一個元素排序需要常量時間Θ(1)。按照分治算法的三個步驟，歸并排序分為(1)劃分：劃分步計算數(shù)組的中點，這需要常量時間Θ(1)。(2)解決：遞歸求解兩個規(guī)模為n/2的子問題，運行時間為2T(n/2)。(3)組合：組合過程對兩個規(guī)模為n/2的子問題進行歸并，時間為Θ(n)。由以上分析可知n=1n>1(2.2)該遞歸方程符合主定理的第二種情形，即Θ(nlogba)=Θ(nlb2)=Θ(n)=f(n)，其解為T(n)=Θ(nlb2lbn)=Θ(nlbn)由于對數(shù)函數(shù)要比線性函數(shù)增長慢，因此，歸并排序最壞情況下的時間復雜度Θ(nlbn)要優(yōu)于冒泡排序最壞情況下的時間復雜度Θ(n2)。圖2-10遞歸樹構(gòu)造(T(n)=2T(n/2)+cn)2.3.5快速排序1．快速排序算法

快速排序就像歸并排序一樣，基于分治算法設計范型，由以下三步組成：(1)劃分：將數(shù)組A［p..r］劃分成兩個子數(shù)組A［p..q-1］和A［q+1..r］(其中之一可能為空)，滿足數(shù)組A［p..q-1］中的每個元素值不超過數(shù)組A［q+1..r］中的每個元素。計算下標q作為劃分過程的一部分。(2)解決：遞歸調(diào)用快速排序算法，對兩個子數(shù)組A［p..q-1］和A［q+1..r］進行排序。(3)組合：由于子數(shù)組中元素已被排序，無需組合操作，整個數(shù)組A［p..r］有序。以下是實現(xiàn)快速排序的QUICKSORT過程。QUICKSORT(A,p,r)1if

p<r

2thenq←PARTITION(A,p,r)3QUICKSORT(A,p,q-1)4QUICKSORT(A,q+1,r)初始時，調(diào)用QUICKSORT(A,1,length［A］)。算法的關(guān)鍵之處在于劃分過程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)，對數(shù)組A［p..r］進行劃分。當過程運行時，數(shù)組被劃分成4個區(qū)域(可能為空)。圖2-11PARTITION運行過程在第3~6行循環(huán)的每次迭代的開始，對于任一下標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劃分的四個區(qū)域?qū)τ谧訑?shù)組A［p..r］，在A［p..i］中的值小于等于x，在A［i+1..j-1］中的值大于x，A［r］=x。A［j..r-1］可取任意值。我們證明循環(huán)不變式在第一次迭代之前成立，在循環(huán)的每次迭代中保持，并利用循環(huán)不變式證明算法終止時的正確性?！こ跏迹涸谘h(huán)的第一次迭代之前，i=p-1，j=p。p和i之間沒有值，i+1和j-1之間沒有值，因此循環(huán)前兩個條件平凡成立。第1行的賦值滿足性質(zhì)(3)?！ぞS持：參照圖2-13，考慮兩種情況。與第4行的判斷條件有關(guān)。圖2-13(a)表示A［j］>x

的情況，循環(huán)中惟一要做的是使變量j增加。變量j值增加后，條件(2)對A［j-1］成立。所有其它元素保持不變。圖2-13(b)表示A［j］≤x的情況，變量i增加，交換A［i］和A［j］，然后j增加。由于交換，使得A［i］≤x成立，條件(1)得到滿足。類似地，由循環(huán)不變式，被交換進入A［j-1］的項大于x，即A［j-1］>x。圖2-13過程PARTITION迭代的兩種情況·終止：終止時，j=r。于是，數(shù)組中的每個元素位于不變式描述的三個集合之一，并把數(shù)組中的元素值劃分成三個集合，即小于等于x的集合，大于x的集合，只含x的孤集。過程PARTITION的最后兩行將樞軸元素與最左邊大于x的元素交換，將其放在數(shù)組的中間。PARTITION的輸出滿足劃分步給出的規(guī)范。它在數(shù)組A［p..r］上的運行時間為Θ(n)，其中n=r-p+1。證明留作習題?？焖倥判虻倪\行時間與劃分是否平衡有關(guān)，而是否平衡又取決于所用的劃分元素。如果劃分平衡，算法的漸近運行時間與歸并排序一樣；如果劃分不平衡，則它的運行時間和冒泡排序一樣，都為O(n2)。以下研究三種不同劃分的情況下快速排序算法的性能。

2．快速排序最壞情況分析

當劃分過程產(chǎn)生的兩個子問題規(guī)模分別為n-1和0時，快速排序出現(xiàn)最壞的情況。假設每次遞歸調(diào)用時產(chǎn)生這種不平衡的情況。劃分的時間復雜度為Θ(n)，因為對規(guī)模為0的數(shù)組的遞歸調(diào)用只會返回，T(0)=Θ(1)，遞歸方程的運行時間為T(n)=T(n-1)+T(0)+Θ(n)=T(n-1)+Θ(n)直覺地，如果我們對遞歸每一層的開銷求和，就得到一個算術(shù)級數(shù)，其和為Θ(n2)。也可以利用替換方法證明遞歸方程T(n)=T(n-1)+Θ(n)的解為Θ(n2)。因而，如果劃分在算法的每一層遞歸上產(chǎn)生最大不平衡，則運行時間為Θ(n2)。因此，快速排序最壞情況下的運行時間不比冒泡排序的運行時間好，而最壞情況是在輸入已經(jīng)完全有序(升序)時出現(xiàn)的。

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

在大多數(shù)均勻劃分的情況下，PARTITION產(chǎn)生兩個規(guī)模不超過n/2的子問題，其中一個規(guī)模為［n/2］，另一個規(guī)模為［n/2］-1。在這種情況下，快速排序運行更快。此時，遞歸方程為T(n)≤2T(n/2)+Θ(n)由主定理的第2種情形，a=2，b=2，nlogba=nlb2=Θ(n)=f(n)，可知遞歸方程的解為T(n)=O(nlbn)。因此，如果劃分在算法的每一層遞歸上產(chǎn)生兩個相同規(guī)模的問題，則得快速排序算法的最佳情況。

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

快速排序算法的平均情況分析更類似于最佳情況分析，關(guān)鍵在于要理解平衡劃分是如何反映描述運行時間的遞歸方程的。假定劃分算法總是產(chǎn)生9∶1的劃分比例，這似乎是相當不平衡的?？焖倥判虻倪f歸方程表示如下：T(n)≤T(9n/10)+T(n/10)+cn圖2-14表示這個遞歸方程的遞歸樹。圖2-14劃分比例為99∶1時的快速排序遞歸樹當我們在隨機輸入數(shù)組上運行快速排序時，每一次的劃分并不總是一樣的。我們期望某些劃分合理地平衡，然而某些劃分卻相當不平衡。例如，大約80%的PARTITION過程產(chǎn)生平衡大于9∶1，而大約20%的PARTITION過程產(chǎn)生平衡小于9∶1。在平均情況下，PARTITION過程產(chǎn)生的劃分既有“好”也有“壞”。在PARTITION過程平均情況執(zhí)行的遞歸樹中，好壞的情況隨機地分布在遞歸樹中。假定好壞的情況在樹中交替出現(xiàn)，并且好的情況就是最佳情況，壞的情況就是最壞情況。圖2-15表示遞歸樹中兩個連續(xù)層的劃分。在樹根結(jié)點，劃分開銷為n，產(chǎn)生兩個規(guī)模分別為n-1和0的劃分，這是一種最壞情況。在下一層，對規(guī)模為n-1的子數(shù)組進行最佳劃分，產(chǎn)生兩個規(guī)模分別為(n-1)/2和(n-1)/2的子數(shù)組。假設規(guī)模為0的子數(shù)組，其邊界條件開銷為1。圖2-15快速排序的兩層遞歸樹橢圓形區(qū)域表示子問題的劃分開銷，都為Θ(n)。在圖2-15(a)中所剩下要解的子問題(方形陰影區(qū)域)不會大于圖2-15(b)中所剩下要解的子問題。在圖2-15(a)中，將劃分產(chǎn)生的三個規(guī)模分別為0、(n-1)/2-1、(n-1)/2的子數(shù)組組合，總開銷為Θ(n)+Θ(n-1)=Θ(n)肯定地說，這種情況不會比圖2-15(b)中的平衡劃分壞，即產(chǎn)生兩個規(guī)模為(n-1)/2的某層劃分，其開銷為Θ(n)。而后者的情形是平衡的！從直覺上來看，壞的劃分Θ(n-1)可以被吸收進好劃分的Θ(n)中，導致最終劃分結(jié)果是好的。因此，快速排序的運行時間，當好的劃分與壞的劃分在樹的層次間交替進行時，就像都是好的劃分結(jié)果一樣，仍然為O(nlbn)，但是隱含在大O中的常數(shù)因子較大。2.3.6線性時間選擇

1．期望線性時間的選擇

一般的選擇問題要比找最小值問題更難，然而令人驚訝的是這兩個問題具有相同的漸近運行時間O(n)。我們?nèi)匀焕梅种尾呗越鉀Q選擇問題。我們利用前面提到的PARTITION過程，但需要做一些修改，這是因為PARTITION過程假定所有輸入元素的排列出現(xiàn)概率相同，但在實際情況中這種假定并不總是能夠成立。我們在算法中引入隨機化，以便更好地研究選擇問題平均情況下的性能。修改后的劃分過程如下：RANDOMIZEDPARTITION(A,p,r)1i←RANDOM(p,r)2exchangeA［r］A［i］3returnPARTITION(A,p,r)RANDOMIZED-SELECT利用過程RANDOMIZED-PARTITION作為子過程。以下過程RANDOMIZED-SELECT返回數(shù)組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//樞軸元素為所求結(jié)果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，子數(shù)組A［p..q］有k個元素(都小于等于樞軸元素)概率為1/n。對于k=1,2,…,n，我們定義指示器隨機變量Xk為Xk=I{子數(shù)組A［p..q］只有k個元素}且E［Xk］=1/n

當我們調(diào)用RANDOMIZED-SELECT并選擇A［q］作為樞軸元素時，預先并不知道是否可以很快以正確解終止，在子數(shù)組A［p..q-1］上遞歸，還是在子數(shù)組A［q+1..r］上遞歸是與樞軸元素A［q］有關(guān)的。假設T(n)單調(diào)遞增，我們分析在最大可能輸入的情況下遞歸調(diào)用所需的時間。換句話說，就是得到一個上界。第i個元素總是在具有最大個數(shù)的那個劃分中。對于給定的調(diào)用RANDOMIZED-SELECT，指示器隨機變量Xk在只有一個k值時為1；其他所有k值時則為0。當Xk=1時，我們可能遞歸調(diào)用的兩個子數(shù)組大小分別為k-1和n-k。因此，遞歸方程為兩邊取期望值，則得其中Xk和T(max(k-1,n-k))是獨立的隨機變量?？紤]表達式max(k-1,n-k)，則有如果n為偶數(shù)，在求和算式中，從T(［n/2］)到T(n-1)中的每一項只出現(xiàn)兩次；如果n為奇數(shù)，所有這些項出現(xiàn)兩次，T(［n/2］)出現(xiàn)一次。因此，用替換方法解此方程。假設對于滿足遞歸方程初始條件的某些常數(shù)c，T(n)≤cn,且當n≤n0時，T(n)=O(1)，其中n0為足夠小的整數(shù)。我們稍后選擇這個常數(shù)n。同時，還要選擇式(2.3)中O(n)項隱含的常數(shù)a，使得對于所有n>0，O(n)≤an。利用歸納假設需要證明，對于足夠大的n，最后的表達式至多為cn，或cn/4-c/2-an≥0。該不等式兩邊加上c/2且提出公因子n，可得n(c/4-a)≥c/2。只要選擇常數(shù)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)。因此，對于任意順序統(tǒng)計量，尤其是中值的計算，平均情況下線性即可決定。2．最壞情況線性時間的選擇

以下介紹一種最壞情況下運行時間為O(n)的選擇算法SELECT。算法SELECT是一遞歸算法，基本思想是對數(shù)組劃分時，保證產(chǎn)生好的分割。算法中仍然用快速排序中使用過的確定劃分算法PARTITION，但用劃分元素作為輸入?yún)?shù)。SELECT算法描述如下：

SELECT1將n個輸入元素分成［n/5］個組，每組5個元素，另一組由剩余的nmod5個元素組成。2利用插入排序算法對［n/5］個組進行排序，并找出每組元素的中值。3對于第2步中找出的［n/5］個中值，利用SELECT遞歸算法找出這［n/5］個中值的中值x。4利用修改的PARTITION過程，以中值的中值x作為劃分元素，對輸入數(shù)組進行劃分。設k是劃分后左半部分元素數(shù)再加上1。因此，x是第k個最小元素，且右半部分有n-k個元素。5如果i=k，則返回x；如果i<k，則利用SELECT在劃分的左半部分找第i個最小元素；如果i>k，則在右半部分找第i-k個最小元素。為了分析SELECT的運行時間，我們首先確定大于劃分元素x的元素個數(shù)。圖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的元素個數(shù)至少為類似地我們可