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

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

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

thenreturn13return

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

例2.2歐幾里得(Euclid)算法。歐幾里得算法是兩千年來(lái)最著名的算法之一：已知兩個(gè)非負(fù)整數(shù)m，n，且m>n>0，求這兩個(gè)數(shù)的最大公因子。歐幾里得得出本算法基于這樣一種觀察，兩個(gè)整數(shù)m和n的最大公因子等于n與mmodn的公因子。歐幾里得算法如下：GCD(m，n)1if

n=02thenreturnm3returnGCD(n，mmodn)圖2-2歐幾里得算法的例子

例2.3漢諾塔(Hanoi)問(wèn)題。設(shè)有三個(gè)塔座X、Y、Z，n個(gè)圓盤(pán)。這些圓盤(pán)大小互不相同，初始時(shí)，這些編號(hào)為1，2，…，n的圓盤(pán)從大到小依次放在塔座X上。最底下為最大圓盤(pán)。要求將該塔座上的圓盤(pán)移到另一個(gè)塔座Z上，并按照同樣順序放置。圓盤(pán)移動(dòng)時(shí)，滿足以下規(guī)則：①一次只能移動(dòng)一個(gè)圓盤(pán)；②任何時(shí)刻不允許將大的圓盤(pán)放在小的圓盤(pán)之上；③圓盤(pán)可以放在X、Y和Z的任一塔座上。我們可以用遞歸解決這個(gè)問(wèn)題。其中遞歸是基于這樣的一個(gè)想法：當(dāng)n=1時(shí)，只要將編號(hào)為1的圓盤(pán)從塔座X直接移到塔座Z上即可；當(dāng)n>1時(shí)，利用Z作中間塔座，依照上述規(guī)則，將編號(hào)為n的圓盤(pán)上的n-1個(gè)圓盤(pán)從塔座X移到塔座Y上，再將X上編號(hào)為n的圓盤(pán)直接移到塔座Z上，最后，以X作中間塔座，將塔座Y上的n-1個(gè)圓盤(pán)從塔座Y移到塔座Z上。而對(duì)于n-1個(gè)圓盤(pán)的移動(dòng)是一個(gè)和原問(wèn)題具有相同特征的子問(wèn)題，可用同樣方法求解。因此，規(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上編號(hào)為1~n的n個(gè)圓盤(pán)按照規(guī)則移到塔座Z上，以Y作中間塔座。HANOI(n-1，X，Z，Y)表示將塔座X上編號(hào)為1~n-1的n-1個(gè)圓盤(pán)按照規(guī)則移到塔座Y上，以Z作中間塔座。HANOI(n-1，Y，X，Z)表示將塔座Y上編號(hào)為1~n-1的n-1個(gè)圓盤(pán)按照規(guī)則移到塔座Z上，以X作中間塔座。MOVE(X，n，Z)表示將編號(hào)為n的圓盤(pán)從塔座X移到塔座Z上。遞歸過(guò)程在實(shí)現(xiàn)時(shí)，可用一個(gè)等價(jià)的遞歸棧實(shí)現(xiàn)過(guò)程的嵌套調(diào)用。遞歸的深度就是在整個(gè)計(jì)算中過(guò)程嵌套調(diào)用的最大程度。通常，深度取決于輸入規(guī)模。因此，對(duì)于大型問(wèn)題，棧所需的空間可能妨礙我們使用遞歸方法求解。圖2-3表示n=4時(shí)漢諾塔算法的運(yùn)行過(guò)程。圖2-3漢諾塔的執(zhí)行過(guò)程(n=4)漢諾塔算法的時(shí)間復(fù)雜度為指數(shù)級(jí)的復(fù)雜度。以下做一簡(jiǎn)要證明。假設(shè)漢諾塔算法的時(shí)間復(fù)雜度為T(mén)(n)，由遞歸算法可得n=1n>1不失一般性，設(shè)n為2的冪。由數(shù)學(xué)歸納法容易得出，該遞歸方程的解為2n-1，即O(2n)。

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

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

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

lbn成立，其中n0是一個(gè)可以選擇的常數(shù)。由于對(duì)于n>3，遞歸方程并不直接依賴T(1)，因此可設(shè)n0=2，選擇T(2)和T(3)作為歸納證明中的邊界條件。由遞歸方程可得T(2)=4和T(3)=5。此時(shí)只要選擇c≥2，就會(huì)使得T(2)≤c·2·lb2和T(3)≤c·3·lb3成立。因此，只要選擇n0=2和c≥2，則有T(n)≤cn

lbn成立。不幸的是，并不存在一般的方法來(lái)猜測(cè)遞歸方程的正確解。這種猜測(cè)需要經(jīng)驗(yàn)，有時(shí)需要?jiǎng)?chuàng)造性。有時(shí)，一些看上去非常陌生的遞歸方程，在經(jīng)過(guò)一些簡(jiǎn)單代數(shù)變換之后，就可以變?yōu)槲覀冚^熟悉的形式。例2.5解遞歸方程。

解設(shè)n=2m

或者m=lbn，則遞歸方程變?yōu)門(mén)(2m)=2T(2m/2)+1再做一次替換，設(shè)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遞歸樹(shù)方法

盡管替換方法提供了證明遞歸方程解的簡(jiǎn)要證明方法，但要猜測(cè)一個(gè)好的解卻比較困難。以下介紹基于遞歸樹(shù)的方法，通過(guò)這種方法，可以更好地猜測(cè)一個(gè)問(wèn)題的解，并用替換方法證明這個(gè)猜測(cè)。圖2-4表明了如何解遞歸方程T(n)=3T(n/4)+cn2。假設(shè)n為4的冪。圖2-4遞歸樹(shù)的構(gòu)造過(guò)程現(xiàn)在，我們確定樹(shù)中每一層的開(kāi)銷(xiāo)。每一層的結(jié)點(diǎn)數(shù)是上一層結(jié)點(diǎn)數(shù)的兩倍，因此，第i層的結(jié)點(diǎn)數(shù)為3i。由于每一層子問(wèn)題規(guī)模為上一層的1/4，由根向下，深度為i(i=0，1，…，log4n-1)的每個(gè)結(jié)點(diǎn)的開(kāi)銷(xiāo)為c(n/4i)2，那么第i層上結(jié)點(diǎn)的總開(kāi)銷(xiāo)為3ic(n/4i)2=(3/16)icn2

i=0，1，…，log4n-1深度為log4n的最后一層有 個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)的開(kāi)銷(xiāo)為T(mén)(1)，該層總開(kāi)銷(xiāo)為 ，即 。將所有層的開(kāi)銷(xiāo)相加得到整棵樹(shù)的開(kāi)銷(xiāo)：現(xiàn)在利用替換方法證明我們的猜測(cè)是正確的。假設(shè)這個(gè)界限對(duì)于n/4成立，即存在某個(gè)常數(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)描述了算法的運(yùn)行時(shí)間，算法將規(guī)模為n的問(wèn)題劃分成a個(gè)子問(wèn)題，每個(gè)子問(wèn)題的大小為n/b，其中a、b是正常數(shù)。求解這a個(gè)子問(wèn)題，每個(gè)所需時(shí)間為T(mén)(n/b)。函數(shù)f(n)表示劃分子問(wèn)題與組合子問(wèn)題解的開(kāi)銷(xiāo)。例如，對(duì)于遞歸方程T(n)=3T(n/4)+cn2，a=3，b=4，f(n)=Θ(n2)。

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

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

nlogba

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

nlogba

T(1)=Θ(nlogba1bn)對(duì)于第三種情形，從根到葉結(jié)點(diǎn)開(kāi)銷(xiāo)的權(quán)重呈幾何級(jí)數(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分治法的基本思想

對(duì)于一個(gè)規(guī)模為n的問(wèn)題，若該問(wèn)題可以容易地解決(比如說(shuō)規(guī)模n較小)，則直接解決，否則將其分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題形式相同，遞歸地解這些子問(wèn)題，然后將各子問(wèn)題的解合并，得到原問(wèn)題的解。這種算法設(shè)計(jì)策略叫做分治法(divideandconquer)。分治法在每一層遞歸上由三個(gè)步驟組成：(1)劃分(divide)：將原問(wèn)題分解為若干規(guī)模較小、相互獨(dú)立、與原問(wèn)題形式相同的子問(wèn)題。(2)解決(conquer)：若子問(wèn)題規(guī)模較小，則直接求解；否則遞歸求解各子問(wèn)題。(3)合并(combine)：將各子問(wèn)題的解合并為原問(wèn)題的解。它的一般算法設(shè)計(jì)范型如下：

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從分治法的一般設(shè)計(jì)模式可以看出，直接用它設(shè)計(jì)出的算法是一個(gè)遞歸算法。我們可用遞歸方程描述遞歸算法的運(yùn)行時(shí)間。設(shè)T(n)表示用分治法求解規(guī)模為n的問(wèn)題所需的計(jì)算時(shí)間，如果問(wèn)題規(guī)模足夠小，比如n≤c，則可直接求解問(wèn)題，T(n)=Θ(1)。假定將原問(wèn)題分為k個(gè)子問(wèn)題，每一個(gè)子問(wèn)題規(guī)模是原問(wèn)題的1/m，若分解該問(wèn)題和合并該問(wèn)題的時(shí)間分別為D(n)和C(n)，則算法的計(jì)算時(shí)間T(n)可表示為如下的遞歸方程：n≤c

n>c

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

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

由此可見(jiàn)，二叉查找的效率比順序查找高，但二叉查找只適用于有序表，且限于順序存儲(chǔ)結(jié)構(gòu)。2.3分治法應(yīng)用實(shí)例2.3.1找最大值與最小值

在含有n個(gè)不同元素的集合中同時(shí)找出它的最大值和最小值(maximum&minimum)的最簡(jiǎn)單方法是將元素逐個(gè)進(jìn)行比較。算法中用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。如果我們將分治策略用于此問(wèn)題，每次將問(wèn)題分成大致相等的兩部分，分別在這兩部分中找出最大值與最小值，再將這兩個(gè)子問(wèn)題的解組合成原問(wèn)題的解，就可得到該問(wèn)題的分治算法。算法描述如下：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}設(shè)T(n)表示算法所需的元素比較次數(shù)，則可得算法的遞歸方程為n=1n=2n>2假設(shè)n為2的冪，化簡(jiǎn)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。事實(shí)上，至多進(jìn)行3［n/2］次比較是找出最小值和最大值的充分條件。策略是維持到目前為止找到的最小值和最大值。我們并不將每個(gè)元素與最大值和最小值都進(jìn)行比較，因?yàn)檫@樣每個(gè)元素需要進(jìn)行兩次比較。下面我們成對(duì)處理元素。首先，輸入元素成對(duì)相互進(jìn)行比較，并將較小者與當(dāng)前最小值比較，較大者與當(dāng)前最大值比較。這樣每?jī)蓚€(gè)元素進(jìn)行三次比較。設(shè)置當(dāng)前最小元素和最大元素的初始值，與n的奇偶性有關(guān)。當(dāng)n為奇數(shù)時(shí)，我們將最小值和最大值都設(shè)為第一個(gè)元素，然后，將其余元素成對(duì)處理；當(dāng)n為偶數(shù)時(shí)，我們?cè)谇皟蓚€(gè)元素之間進(jìn)行一次比較，決定最大值和最小值的初始值，然后，將其余元素成對(duì)處理。以下分析上述算法的比較次數(shù)。如果n為奇數(shù)，那么需進(jìn)行3［n/2］次比較；如果n為偶數(shù)，我們首先在前兩個(gè)元素之間進(jìn)行一次比較，然后進(jìn)行3(n-2)/2次比較，總共進(jìn)行3n/2-2次比較。因此，不論在哪一種情況下，比較的次數(shù)至多為3［n/2］可以證明，任何基于比較的找最大值和最小值的算法，其元素比較次數(shù)下界為［3n/2］-2［18］。在這種意義下，算法REC-MAXMIN是最優(yōu)的。但是REC-MAXMIN也有其不足之處，它所要求的存儲(chǔ)空間較大，即算法中的每次遞歸調(diào)用都需要保留i，j，fmax，fmin的值及返回地址。2.3.2Strassen矩陣乘法矩陣乘法是科學(xué)計(jì)算中最基本的問(wèn)題之一。設(shè)A和B是兩個(gè)n×n的矩陣，它們的乘積C=AB也是一個(gè)n×n的矩陣。其中乘積矩陣中的元素cij定義為由此可得，計(jì)算矩陣C中的每個(gè)元素需要n次乘法和n-1次加法。因此，計(jì)算矩陣C的n2個(gè)元素所需的時(shí)間為O(n3)。假設(shè)n為2的冪，運(yùn)用分治策略，將矩陣分成4塊大小相等的子矩陣，每個(gè)子矩陣 的方陣。矩陣乘積C=AB可重寫(xiě)為其中：C11=A11B11+A12B21

C12=A11B12+A12B22

C21=A21B11+A22B21

C22=A21B12+A22B22如果子矩陣的規(guī)模大于2，則可以繼續(xù)劃分這些子矩陣，直至每個(gè)矩陣變成2×2的矩陣。對(duì)于2×2的矩陣的計(jì)算，只需8次乘法和4次減法，計(jì)算時(shí)間為O(1)。設(shè)T(n)表示兩個(gè)n×n矩陣相乘所需的計(jì)算時(shí)間，則由Cij(i，j=1，2)的計(jì)算可以看出，可將T(n)的計(jì)算轉(zhuǎn)化為計(jì)算8個(gè) 的矩陣相乘和4個(gè)矩陣相加，而計(jì)算 矩陣加法所需時(shí)間為O(n2)，可得n=2n>2該遞歸方程符合主定理的第一種情形，其解為T(mén)(n)=O(nlb8)=O(n3)。因此，直接的分治策略并沒(méi)有降低算法的計(jì)算復(fù)雜度。1969年，Strassen經(jīng)過(guò)對(duì)問(wèn)題的分析，在分治策略的基礎(chǔ)上，通過(guò)數(shù)學(xué)技巧，使算法的計(jì)算復(fù)雜度從O(n3)降到了O(n2.81)。當(dāng)此結(jié)果第一次發(fā)表時(shí)，震動(dòng)了數(shù)學(xué)界。在Strassen矩陣相乘(Strassenmatrtrixmultiplication)算法中，只用了7個(gè) 的矩陣相乘，但增加了10個(gè)矩陣加、減法運(yùn)算。這7個(gè)矩陣乘法是：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)然后，再通過(guò)8個(gè)矩陣的加、減法運(yùn)算來(lái)計(jì)算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個(gè)的矩陣相乘和4個(gè) 矩陣相加。因此，算法所需的計(jì)算時(shí)間滿足如下遞歸方程：n=2n>2該遞歸方程仍然符合主定理的第一種情形，其解為T(mén)(n)=O(nlb7)≈O(n2.81)。因此，Strassen矩陣乘法的計(jì)算時(shí)間較之前面討論的矩陣乘法有所改進(jìn)。繼Strassen算法之后，許多科研人員致力于該問(wèn)題的研究，希望對(duì)此結(jié)果有所改進(jìn)。但J.E.Hopcroft和L.R.Kerr［19］已經(jīng)證明了兩個(gè)2×2矩陣相乘必須用7次乘法，因此，要進(jìn)一步改進(jìn)矩陣相乘的時(shí)間復(fù)雜度，就要考慮3×3或4×4等更大一級(jí)的分塊，或者采用新的設(shè)計(jì)思想。2.3.3整數(shù)相乘

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

設(shè)T(n)表示兩個(gè)n位的整數(shù)相乘所需的計(jì)算時(shí)間，則n=1n>1其中，4T(n/2)表示需要解4個(gè)規(guī)模為n/2的子問(wèn)題，O(n)表示利用移位和加法將子問(wèn)題解組合成原問(wèn)題解的時(shí)間。該遞歸方程符合主定理的第一種情形，其解為T(mén)(n)=O(nlb4)=O(n2)不幸的是，算法效率仍然沒(méi)有得到提高。這里的關(guān)鍵是分割產(chǎn)生的4個(gè)子問(wèn)題有些多。能否像在Strassen算法中所做的那樣，通過(guò)一些技巧，或者說(shuō)通過(guò)提高計(jì)算的效率，減少子問(wèn)題的數(shù)量。答案是肯定的。不需分別計(jì)算ad和bc，而只需計(jì)算它們的和ad+bc。注意下式：(a+b)(c+d)=(ad+bc)+(ac+bd)如果計(jì)算出ac、bd和(a+b)(c+d)，那么可以從(a+b)(c+d)減去ac和bd得到ac+bd的值，即ac+bd=(a+b)(c+d)-ac-bd。當(dāng)然，增加了一些加法運(yùn)算，但卻使得計(jì)算規(guī)模為n/2的子問(wèn)題的乘法減少了一個(gè)。遞歸方程為n=1n>1上述描述的整數(shù)相乘算法可用于小數(shù)相乘和二進(jìn)制乘法。我們用下面的例子說(shuō)明這個(gè)方法。設(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中的第一項(xiàng)是將v的小數(shù)位置右移4位得到的，中間項(xiàng)是將u-v-w的小數(shù)位置右移2位得到的。2.3.4歸并排序

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

1．歸并算法及其運(yùn)行時(shí)間

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

2．歸并算法示例

圖2-8表示歸并過(guò)程MERGE作用于子數(shù)組〈2,4,5,7,1,2,3,6〉上執(zhí)行第10~17行的過(guò)程。調(diào)用歸并過(guò)程MERGE時(shí)，參數(shù)p、q和r的值分別為9、12和16。圖2-8調(diào)用MERGE(A,9,12,16)時(shí)第10~17行的運(yùn)行過(guò)程圖2-8調(diào)用MERGE(A,9,12,16)時(shí)第10~17行的運(yùn)行過(guò)程3．歸并排序算法我們將利用MERGE作為排序算法的子過(guò)程，利用MERGE-SORT對(duì)子數(shù)組A［p..r］中的元素進(jìn)行排序。如果p≥r，則子數(shù)組至多有一個(gè)元素，因而有序；否則第2行計(jì)算下標(biāo)q，將數(shù)組A［p..r］劃分成兩個(gè)子數(shù)組A［p..q］和A［q+1..r］，它們分別包含［n/2］和［n/2］個(gè)元素。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)算法通過(guò)兩個(gè)長(zhǎng)為1的子序列形成長(zhǎng)為2的有序序列，再通過(guò)兩個(gè)長(zhǎng)為2的有序序列形成長(zhǎng)為4的有序序列，直到通過(guò)兩個(gè)長(zhǎng)為n/2的有序序列形成長(zhǎng)為n的有序序列。初始時(shí)調(diào)用MERGE-SORT(A,1,length［A］)，其中l(wèi)ength［A］=n。設(shè)A=〈5,2,4,7,1,3,2,6〉，圖2-9說(shuō)明了MERGE-SORT排序的過(guò)程。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排序的過(guò)程

4．歸并排序算法的復(fù)雜度分析

設(shè)T(n)表示規(guī)模為n的問(wèn)題的運(yùn)行時(shí)間，為了簡(jiǎn)化以下對(duì)于遞歸方程的分析，設(shè)n為2的冪。歸并排序每次的劃分步產(chǎn)生規(guī)模為n/2的兩個(gè)子問(wèn)題。對(duì)于一個(gè)元素排序需要常量時(shí)間Θ(1)。按照分治算法的三個(gè)步驟，歸并排序分為(1)劃分：劃分步計(jì)算數(shù)組的中點(diǎn)，這需要常量時(shí)間Θ(1)。(2)解決：遞歸求解兩個(gè)規(guī)模為n/2的子問(wèn)題，運(yùn)行時(shí)間為2T(n/2)。(3)組合：組合過(guò)程對(duì)兩個(gè)規(guī)模為n/2的子問(wèn)題進(jìn)行歸并，時(shí)間為Θ(n)。由以上分析可知n=1n>1(2.2)該遞歸方程符合主定理的第二種情形，即Θ(nlogba)=Θ(nlb2)=Θ(n)=f(n)，其解為T(mén)(n)=Θ(nlb2lbn)=Θ(nlbn)由于對(duì)數(shù)函數(shù)要比線性函數(shù)增長(zhǎng)慢，因此，歸并排序最壞情況下的時(shí)間復(fù)雜度Θ(nlbn)要優(yōu)于冒泡排序最壞情況下的時(shí)間復(fù)雜度Θ(n2)。圖2-10遞歸樹(shù)構(gòu)造(T(n)=2T(n/2)+cn)2.3.5快速排序1．快速排序算法

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

p<r

2thenq←PARTITION(A,p,r)3QUICKSORT(A,p,q-1)4QUICKSORT(A,q+1,r)初始時(shí)，調(diào)用QUICKSORT(A,1,length［A］)。算法的關(guān)鍵之處在于劃分過(guò)程PARTITION，如果不計(jì)所用棧的空間，快速排序所需空間為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個(gè)元素的PARTITION運(yùn)行過(guò)程。PARTITION總是選擇元素x=A［r］作為樞軸元素(pivotelement)，對(duì)數(shù)組A［p..r］進(jìn)行劃分。當(dāng)過(guò)程運(yùn)行時(shí)，數(shù)組被劃分成4個(gè)區(qū)域(可能為空)。圖2-11PARTITION運(yùn)行過(guò)程在第3~6行循環(huán)的每次迭代的開(kāi)始，對(duì)于任一下標(biāo)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劃分的四個(gè)區(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)不變式證明算法終止時(shí)的正確性。·初始：在循環(huán)的第一次迭代之前，i=p-1，j=p。p和i之間沒(méi)有值，i+1和j-1之間沒(méi)有值，因此循環(huán)前兩個(gè)條件平凡成立。第1行的賦值滿足性質(zhì)(3)?！ぞS持：參照?qǐng)D2-13，考慮兩種情況。與第4行的判斷條件有關(guān)。圖2-13(a)表示A［j］>x

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

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

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

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

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

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

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

1．期望線性時(shí)間的選擇

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

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

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

SELECT1將n個(gè)輸入元素分成［n/5］個(gè)組，每組5個(gè)元素，另一組由剩余的nmod5個(gè)元素組成。2利用插入排序算法對(duì)［n/5］個(gè)組進(jìn)行排序，并找出每組元素的中值。3對(duì)于第2步中找出的［n/5］個(gè)中值，利用SELECT遞歸算法找出這［n/5］個(gè)中值的中值x。4利用修改的PARTITION過(guò)程，以中值的中值x作為劃分元素，對(duì)輸入數(shù)組進(jìn)行劃分。設(shè)k是劃分后左半部分元素?cái)?shù)再加上1。因此，x是第k個(gè)最小元素，且右半部分有n-k個(gè)元素。5如果i=k，則返回x；如果i<k，則利用SELECT在劃分的左半部分找第i個(gè)最小元素；如果i>k，則在右半部分找第i-k個(gè)最小元素。為了分析SELECT的運(yùn)行時(shí)間，我們首先確定大于劃分元素x的元素個(gè)數(shù)。圖2-16可視化說(shuō)明了劃分元素的選擇過(guò)程。小圓圈表示n個(gè)元素。每列表示一組，每組中的中值用淺灰色表示，中值的中值已標(biāo)示出。箭頭表示從大元素到小元素，由此可見(jiàn)，x右邊的5個(gè)元素的每個(gè)組中，每組有3個(gè)元素大于x，x左邊的5個(gè)元素的每個(gè)組中，每組有3個(gè)元素小于x。陰影背景中的元素比x大。圖2-16SELECT算法分析在算法SELECT第2步所找到的中值中，至少有一半大于x。因此，［n/5］組中至少有一半的小組有3個(gè)元素大于x，除了元素不足5個(gè)的組(如果n不能被5整除)以及包括x自身的那個(gè)組。減去這兩個(gè)組，則大于x的元素個(gè)數(shù)至少為類(lèi)似地我們可