第3章分治法知識講解

第二章分治法

——“分”而治之2.1一般方法對大規(guī)模問題的求解利用分治法求解大規(guī)模問題1.基本思想分而治之方法法與軟件設(shè)計的模塊化方法非常相似。為解決一個大問題，可以（1）把它分解成兩個或多個更小的問題；（2）分別解決每個小問題；（3）把各小問題的解答組合起來，即可得到原問題的解。小問題通常與原問題相似或同質(zhì)，因而可以遞歸地使用分而治之策略解決。1/30/2025本章教學(xué)要求及重點難點理解分治法的基本思想掌握二分檢索中成功檢索和不成功檢索各自時間復(fù)雜度的計算方法掌握歸并分類的基本方法掌握快速分類的算法及對此算法的時間復(fù)雜度分析掌握最壞情況下選擇問題的時間復(fù)雜度分析重點：二分檢索、找最大和最小元素、歸并分類、快速分類。難點：選擇問題的算法及對該算法的時間復(fù)雜度分析1/30/2025通常，子問題與原始問題“同質(zhì)”1/30/2025例[找偽幣]假設(shè)16枚金幣中有一枚是偽造的，真假金幣的區(qū)別僅是重量不同(偽幣輕一些），利用一個沒有砝碼的天平作工具，找出這枚偽造的金幣。

方法1：比較硬幣1和2的重量，有一個輕則找到；否則比較硬幣3和4，依次比較下去，直到找到。最多8次比較。方法2：利用分治法。16個硬幣分為兩組，每組8個，比較重量，偽幣在輕的一組。將輕的一組再分為兩組，每組4個……繼續(xù)劃分下去，依次每組2個，每組1個，此時找到。1/30/2025DANDC的計算時間若所分成的兩個子問題的輸入規(guī)模大致相等，則DANDC總的計算時間可用遞歸關(guān)系式表示，如下：g(n)n足夠小T(n)=2T(n/2)+f(n)否則

注：

T(n)：表示輸入規(guī)模為n的DANDC計算時間

g(n)：表示對足夠小的輸入規(guī)模直接求解的計算時間

f(n)：表示COMBINE對兩個子區(qū)間的子結(jié)果進(jìn)行合并的時間（該公式針對具體問題有各種不同的變形）1/30/20252.2二分檢索（折半查找）1.問題的描述已知一個按非降次序排列的元素表a1,a2,…,an,判定某給定的元素x是否在該表中出現(xiàn)。若是，則找出x在表中的位置并返回其所在下標(biāo)若非，則返回0值。1/30/2025分治求解策略分析：定義問題的形式描述：I=(n,a1,a2,…,an,x)問題分解：選取下標(biāo)k，由此將I分解為3個子問題：I1=(k-1,a1,a2,…,ak-1,x)I2=(1,ak,x)I3=(n-k,ak+1,ak+2,…,an,x)對于I2，若ak=x，則有解k，對I1、I3不用再求解；否則，若x<ak，則只在I1中求解，對I3不用求解；若x>ak，則只在I3中求解，對I1不用求解；I1、I3上的求解可再次采用分治方法劃分后求解（遞歸過程）1/30/20252.二分檢索算法算法2.3二分檢索procedureBINSRCH(A,n,x,j)integerlow,high,mid,j,n;low←1;high←n;whilelow≤highdo

mid←case:x<A(mid):high←mid-1:x>A(mid):low←mid+1:else:j←mid;returnendcaserepeatj←0endBINSRCH注：給定一個按非降次序排列的元素數(shù)組A(1:n)，n≥1,判斷x是否出現(xiàn)。若是，置j，使得x=A(j)若非，j=01/30/2025例2.1：設(shè)A(1:9)=(-15，-6，0，7，9，23，54，82，101)在A中檢索x=101，-14，82。執(zhí)行軌跡見下表1成功的檢索不成功的檢索成功的檢索1/30/20253.算法的正確性證明定理2.1過程BINSRCH(A,n,x,j)能正確運(yùn)行證明：1）在具體指定A中的數(shù)據(jù)元素及x的數(shù)據(jù)類型后，算法中的所有運(yùn)算都能按要求正確運(yùn)行——即首先滿足確定性和能行性2）終止性算法初始部分置low←1,high←n

①若n=0，不進(jìn)入循環(huán)，j置0，算法終止

②否則，進(jìn)入循環(huán)，計算mid,或x=A(mid)，j置為mid，算法終止；或x<A(mid)，置high←mid-1，搜索范圍實際縮小為[low,mid-1]，進(jìn)入下次循環(huán)，對[mid+1,high]區(qū)間不做進(jìn)一步搜索；或x>A(mid)，置low←mid+1，進(jìn)入下次循環(huán)；搜索范圍實際縮小為[mid+1,high]，對[low,mid-1]區(qū)間不做進(jìn)一步搜索；

因low,high,mid都是整型變量，故按照上述規(guī)則，在有限步內(nèi)，或找到某個mid，有A(mid)=x；或變得low>high，在A中沒有找到任何元素等于x，算法終止。1/30/20254.性能分析1）空間特性n+5個空間位置——О(n)2)時間特性區(qū)分以下情況，并進(jìn)行相應(yīng)的分析成功檢索：所檢索的x出現(xiàn)在A中。成功檢索情況共有n種：x恰好是A中的某個元素，A中共有n個元素，故有n種可能的情況不成功檢索：所檢索的x不出現(xiàn)在A中。不成功檢索情況共有n+1種：x<A(1),或A(i)<x<A(i+1),1≤i<n-1或x>A(n)

成功/不成功檢索的最好情況：執(zhí)行步數(shù)最少，計算時間最短成功/不成功檢索的最壞情況：執(zhí)行步數(shù)最多，計算時間最長成功/不成功檢索的平均情況：一般情況下的計算時間1/30/2025實例分析（例2.1）頻率計數(shù)特征

while循環(huán)體外語句的頻率計數(shù)為1

集中考慮while循環(huán)中的x與A中元素的比較（其它運(yùn)算的頻率計數(shù)與之有相同的數(shù)量級）假定只需一次比較就可確定case語句控制是三種情況的哪一種。查找每個元素所需的元素比較次數(shù)統(tǒng)計如下：A⑴⑵⑶⑷⑸⑹⑺⑻⑼元素-15-6079235482101成功檢索比較次數(shù)323413234

不成功檢索比較次數(shù)33344333441/30/2025成功檢索最好：1次

最壞：4次

平均：（3+2+3+4+1+3+2+3+4）/9≈2.77次不成功檢索最好：3次

最壞：4次

平均：(3+3+3+4+4+3+3+3+4+4)/10=3.4次1/30/2025二元比較樹算法執(zhí)行過程的主體是x與一系列中間元素A(mid)比較。可用一棵二元樹描述這一過程，并稱之為二元比較樹。構(gòu)造：比較樹由稱為內(nèi)結(jié)點和外結(jié)點的兩種結(jié)點組成：內(nèi)結(jié)點：表示一次元素比較，用圓形結(jié)點表示，存放一個mid值；代表一次成功檢索；外結(jié)點：在二分檢索算法中表示一種不成功檢索的情況，用方形結(jié)點表示。路徑：表示一個元素的比較序列。例2.1的二元比較樹1/30/2025基于二元比較樹的分析若x在A中出現(xiàn)，則算法的執(zhí)行過程在一個圓形的內(nèi)結(jié)點處結(jié)束。若x不在A中出現(xiàn)，則算法的執(zhí)行過程在一個方形的外結(jié)點處結(jié)束——外結(jié)點不代表元素的比較，因為比較過程在該外結(jié)點的上一級的內(nèi)結(jié)點處結(jié)束。

例2.1的二元比較樹1/30/2025定理2.2若n在區(qū)域[2k-1,2k)中，則對于一次成功的檢索，BINSRCH至多做k次比較；對于一次不成功的檢索，或者做k-1次比較，或者做k次比較。證明：要點：成功檢索都在內(nèi)結(jié)點處結(jié)束，不成功檢索都在外結(jié)點處結(jié)束當(dāng)2k-1≤n<2k時，所有內(nèi)結(jié)點在1至k級，所有外結(jié)點在第k級或第k+1級，故：成功檢索在i級終止所需要的元素比較次數(shù)是i不成功檢索在i級外部結(jié)點終止的元素比較次數(shù)是i-11/30/2025BINSRCH計算復(fù)雜度的理論分析1）不成功檢索的最好、最壞和平均情況的計算時間均為——外結(jié)點處在最末的兩級上；2）最好情況下的成功檢索的計算時間為最壞情況下的成功檢索的計算時間為1/30/20253）平均情況下的成功檢索的計算時間分析利用外部結(jié)點和內(nèi)部結(jié)點到根距離和之間的關(guān)系進(jìn)行推導(dǎo)：記，由根到所有內(nèi)結(jié)點的距離之和稱為內(nèi)部路徑長度，記為I；由根到所有外部結(jié)點的距離之和稱為外部路徑長度，記為E。則有，E=I+2n

記，

U(n)是平均情況下不成功檢索的計算時間，則U(n)=E/(n+1)

S(n)是平均情況下成功檢索的計算時間，則S(n)=I/n+1

利用上述公式，可有:S(n)=(1+1/n)U(n)-1當(dāng)n→∞,S(n)∝U(n)

，而U(n)=

所以S(n)=1/30/20254.以比較為基礎(chǔ)檢索的時間下界問題：設(shè)n個元素的數(shù)組A(1:n)有A(1)<A(2)<…<A(n)。檢索一給定元素x是否在A中出現(xiàn)。定理2.2給出了二分檢索算法的時間下界，是否預(yù)計還存在有以元素比較為基礎(chǔ)的另外的檢索算法，它在最壞情況下比二分檢索算法在計算時間上有更低的數(shù)量級?以比較為基礎(chǔ)的算法：假定算法中只允許進(jìn)行元素間的比較，而不允許對它們實施其它運(yùn)算。1/30/2025注：每個內(nèi)結(jié)點表示一次元素的比較。每棵比較樹中恰好含有n個內(nèi)結(jié)點，分別與n個不同i值相對應(yīng)；每個外結(jié)點對應(yīng)一次不成功的檢索，并恰好又n+1個外結(jié)點對應(yīng)于n+1中不成功檢索的情況。任何以比較為基礎(chǔ)的檢索算法，其執(zhí)行過程都可以用二元比較樹來描述。1/30/2025以比較為基礎(chǔ)的有序檢索問題最壞情況的時間下界定理2.3設(shè)A(1:n)含有n(n≥1)個不同的元素，排序為A(1)<A(2)<…<A(n)。又設(shè)用以比較為基礎(chǔ)的算法去判斷是否，則這樣的任何算法在最壞情況下所需的最小比較次數(shù)FIND(n)有：證明：從模擬求解檢索問題算法的比較樹可知，F(xiàn)IND(n)不大于樹中由根到一個葉子的最長路徑的距離。而所有樹中必定有n個內(nèi)結(jié)點與x在A中的n中可能的出現(xiàn)相對應(yīng)。如果一棵二元樹的所有內(nèi)結(jié)點所在的級數(shù)小于或等于k，則最多有2k-1個內(nèi)結(jié)點。故n≤2k-1,即1/30/2025任何一種以比較為基礎(chǔ)的算法，在最壞情況下的計算時間都不低于Ο(logn)。因此，不可能存在最壞情況比二分檢索數(shù)量級還低的算法。二分檢索是解決檢索問題的最優(yōu)的最壞情況算法。1/30/20252.3找最大和最小元素問題描述：給定含有n個元素的集合，在其中找出最大和最小元素。1/30/20251.直接找最大和最小元素算法2.5直接找最大和最小元素procedureSTRAITMAXMIN(A,n,max,min)//將A中的最大值置于max，最小值置于min//Integeri,nmax←min←A(1)fori←2tondoifA(i)>maxthenmax←A(i)endififA(i)<minthenmin←A(i)endifrepeatendSTRAITMAXMIN

算法的性能：只考慮算法中的比較運(yùn)算，以此代表算法的執(zhí)行特征；該算法最好、最壞、平均情況下均需要做2(n-1)次元素比較1/30/2025STRAITMAXMIN算法的一種簡單改進(jìn)形式:procedureSTRAITMAXMIN1(A,n,max,min)integeri,nmax←min←A(1)fori←2tondoifA(i)>maxthenmax←A(i)endifelseifA(i)<minthenmin←A(i)endifrepeatendSTRAITMAXMIN1這使得，最好情況：按遞增次序排列，元素比較次數(shù)為n-1次最壞情況：按遞減次序排列，元素比較次數(shù)為2(n-1)次平均情況：元素比較次數(shù)為3(n-1)/2次1/30/20252.分治求解策略記問題的一個實例為：I=(n,A(1),…,A(n))采用二分法將I分成兩個子集合處理

I1=(,A(1),…，A())，和

I2=(n-,A(+1),…，A(n))則有，MAX(I)=max(MAX(I1),MAX(I2))MIN(I)=min(MIN(I1),MIN(I2))采用遞歸的設(shè)計策略，得到以下算法：1/30/20253.一種遞歸求解策略算法2.6遞歸求取最大和最小元素procedureMAXMIN(i,j,fmax,fmin)//A(1:n)是含有n個元素的數(shù)組，參數(shù)I,j是整數(shù)，1≤i,j≤n//

//該過程把A(i:j)中的最大和最小元素分別賦給fmax和fmin//integeri,j;globaln,A(1:n)case:i=j:fmax←fmin←A(i)//只有一個元素:i=j-1:ifA(i)<A(j)thenfmax←A(j);fmin←A(i)elsefmax←A(i);fmin←A(j)//兩個元素的情況endif:else:mid←//取中callMAXMIN(i,mid,gmax,gmin)callMAXMIN(mid+1,j,hmax,hmin)

fmax←max(gmax,hmax);fmin←min(gmin,hmin)endcaseendMAXMIN1/30/2025例：在A(1:9)=(22,13,-5,-8,15,60,17,31,47)上執(zhí)行算法2.6每個結(jié)點內(nèi)的值分別是：i,j,fmax,fmin遞歸調(diào)用遞歸調(diào)用分解過程遞歸調(diào)用的返回1/30/2025性能分析(T(n)表示元素比較數(shù)）0n=1T(n)=1n=2n>2當(dāng)n是2的冪時(n=2k),化簡上式有，T(n)=2T(n/2)+2=2(2T(n/4)+2)+2=…=2k-1T(2)+=2k-1+2k-2=3n/2-21/30/2025性能分析1）與STRAITMAXMIN算法相比，比較次數(shù)減少了25%（3n/2-2:2n-2)。已經(jīng)達(dá)到了以元素比較為基礎(chǔ)的找最大最小元素的算法計算時間的下界：2）存在的問題：空間占用量大

?有

級的遞歸，入棧參數(shù)：

?i,j,fmax,fmin和返回地址五個值。時間可能不比預(yù)計的理想如果元素A(i)和A(j)的比較與i和j的比較相差不大時，算法MAXMIN不可取。1/30/2025假設(shè)元素的比較與i和j的比較時間相同（整型數(shù)）。又設(shè)case語句中僅需一次i和j的比較就能夠確定是哪種情況。記此時MAXMIN的頻率計數(shù)為C(n)，n=2k(k為正整數(shù)）。則有，2n=2C(n)=2C(n/2)+3n>2化簡得，C(n)=2C(n/2)+3=…=5n/2-3按照同樣的假設(shè)，重新估算STRAITMAXMIN算法的比較次數(shù)為：3(n-1)。考慮MAXMIN算法遞歸調(diào)用的開銷，此時MAXMIN算法的效率可能還不如STRAITMAXMIＮ算法。1/30/2025結(jié)論：如果A中的元素間的比較代價遠(yuǎn)比整型數(shù)（下標(biāo)）的比較昂貴，則分治方法將產(chǎn)生一個效率較高的算法；反之，可能僅得到一個低效的算法。故，分治策略只能看成一個較好的但并不總是成功

的算法設(shè)計指導(dǎo)。1/30/20252.4歸并分類1.分類問題——排序給定一n個元素的集合A，按照某種方法將A中的元素按非降或非增次序排列。分類：內(nèi)排序，外排序常見內(nèi)排序方法：冒泡排序插入排序歸并排序快速排序堆排序…[例]輸入：（8，5，4，9）輸出：（4，5，8，9）或（9，8，5，4）1/30/20252.插入分類

算法2.7插入分類procedureINSERTIONSORT(A,n)//將A(1：n)中的元素按非降次序分類，n≥1//A(0)←-∞//設(shè)置初始邊界值forj←2tondo//A(1:j-1)已分類//item←A(j);i←j-1whileitem<A(i)do//0≤i<j//A(i+1)←A(i);i←i-1repeatA(i+1)←item;repeatendINSERTIONSORT

(8,5,4,9)(8,5,4,9)

(5,8,4,9)(5,8,

4,9)(4,5,8,9)(4,5,8,9)1/30/2025性能分析：最壞情況：輸入數(shù)據(jù)按非增次序排列,每次內(nèi)層while循環(huán)執(zhí)行j次（j=2,3,…,n)。則有，最好情況：輸入數(shù)據(jù)已按非降序排列，不進(jìn)入while循環(huán)，則最好情況下計算時間為Ω(n)1/30/20253.分治策略求解

基本設(shè)計思想：將原始數(shù)組A中的元素分成兩個子集合：A1(1:)和A2(+1:n)。分別對這兩個子集合單獨分類，然后將已分類的兩個子序列歸并成一個含有n個元素的分類好的序列。這樣的一個分類過程稱為歸并分類。

1/30/2025算法2.8歸并分類

procedureMERGESORT(low,high)//A(low:high)是一個全程數(shù)組，它含有high-low+1≥0個待分類的元素//integerlow,highiflow<highthen

mid←//計算中分點//callMERGESORT(low,mid)//在第一個子集合上分類(遞歸)//callMERGESORT(mid+1,high)//在第二個子集合上分類(遞歸)//callMERGE(low,mid,high)//歸并已分類的兩子集合//endifendMERGESORT1/30/2025算法2.9使用輔助數(shù)組歸并兩個已分類的集合procedureMERGE(low,mid,high)//A(low,high)是一個全程數(shù)組,它含有兩個放在A(low,mid)和A(mid+1,high)中的已分類的子集合.目標(biāo)是將這兩個已分類的集合歸并成一個集合，并存放到A(low,high)中//integerh,I,j,k,low,mid,high;//low≤mid＜high//globalA(low,high);localB(low,high)h←low;i←low;j←mid+1;whileh≤midandj≤highdo//當(dāng)兩個集合都沒有取盡時,將較小的元素先存放到B中//ifA(h)≤A(j)thenB(i)←A(h);h←h+1//如果前一個數(shù)組中的元素較小//elseB(i)←A(j);j←j+1//如果后一個數(shù)組中的元素較小//endifrepeat

//處理尚有剩余元素的集合//ifh>midthenfork←jtohighdoB(i)←A(k);i←i+1;repeatelsefork←htomiddoB(i)←A(k);i←i+1;repeatendiffork←lowtohighdoA(k)←B(k)repeat//將已歸并的集合復(fù)制到A中//endMERGE1/30/2025性能分析1)過程MERGE的歸并時間與兩數(shù)組元素的總數(shù)成正比(可表示為:cn,n為元素數(shù),c為某正常數(shù))2)過程MERGESORT的分類時間用遞推關(guān)系式表示如下:an=1,a是常數(shù)T(n)=2T(n/2)+cnn>1,c是常數(shù)化簡:若n=2k,則有,T(n)=2(2T(n/4)+cn/2)+cn=4T(n/4)+2cn=4T(2T(n/8)+cn/4)+2cn=…=2kT(1)+kcn=an+cnlogn//k=logn//若2k<n<2k+1,則有T(n)≤T(2k+1)。所以得：T(n)=Ο(nlogn)

1/30/2025歸并分類示例設(shè)A=（310，285，179，652，351，423，861，254，450，520）1）劃分過程310，285，179，652，351，423，861，254，450，520310，285，179，652，351423，861，254，450，520310，285，179652，351310，285179310285652351423，861，254450，520423，8612544238614505201/30/20252）歸并過程首先進(jìn)入左分枝的劃分與歸并。首先形成的劃分狀態(tài)是：（310|285|179|652，351|423，861，254，450，520）第一次歸并：（285，310|179|652，351|423，861，254，450，520）第二次歸并：（179，285，310|652，351|423，861，254，450，520）第三次歸并：（179，285，310|351，652|423，861，254，450，520）第四次歸并：（179，285，310，351，652|423，861，254，450，520）進(jìn)入右分枝的劃分與歸并過程（略）1/30/20253）用樹結(jié)構(gòu)描述歸并分類過程1/30/20254.歸并分類算法的改進(jìn)1）算法2.8存在的問題遞歸層次太深在MERGESORT的執(zhí)行過程中，當(dāng)集合僅含有兩個元素時，仍要進(jìn)一步做遞歸調(diào)用，直至每個集合僅含有一個元素時才退出遞歸調(diào)用。在集合含有僅相當(dāng)少的元素時，較深層次的遞歸調(diào)用使得時間過多地消耗在處理遞歸上。元素在數(shù)組A和輔助數(shù)組B之間的頻繁移動每次歸并，都要首先將A中的元素移到B中，在由B復(fù)制到A的對應(yīng)位置上。1/30/20252）改進(jìn)措施針對遞歸層次問題采用能在小規(guī)模集合上有效工作的其它算法，直接對小規(guī)模集合處理。如INSERTIONSORT算法針對元素頻繁移動問題采用一個稱為鏈接信息數(shù)組LINK（1：n）的數(shù)據(jù)結(jié)構(gòu)，記錄歸并過程中A中的元素相對于其排序后在分類表中位置坐標(biāo)的鏈接關(guān)系。LINK(i)取值于[1，n]，是指向A的元素的指針：在分類表中它指向下一個元素在A中的位置坐標(biāo)。1/30/2025例：LINK(1)(2)(3)(4)(5)(6)(7)(8)

6

4

7

1

3

0

8

0該表中含有兩個子表，0表示表的結(jié)束。設(shè)置表頭指針Q和R分別指向兩個子表的起始處：Q=2，R=5；則有，表1：Q(2，4，1，6)，經(jīng)過分類后有：A(2)≤A(4)≤A(1)≤A(6)表2：R(5，3，7，8)，同樣有：A(5)≤A(3)≤A(7)≤A(8)

鏈接信息表在歸并過程中的應(yīng)用：將歸并過程中元素在A和B之間移動的過程變成更改LINK所指示的鏈接關(guān)系，從而避免移動元素的本身。

分類表可以通過LINK的表頭指針和讀取LINK中的鏈接關(guān)系取得。1/30/2025改進(jìn)后的歸并分類模型算法2.10使用鏈接信息數(shù)組的歸并分類模型procedureMERGESORT1(low,high,p)//利用鏈接信息數(shù)組LINK(1:n)將全程數(shù)組A(low:high)按非降次序分類。LINK中值表示按分類次序給出A下標(biāo)的表，并把p置于該表的開始處//globalA(low:high),LINK(low,high)ifhigh-low+1<16//當(dāng)集合中的元素個數(shù)足夠少(<16)時，采用更有效的小規(guī)模集合上的分類算法直接分類//thencallINSERTSORT1(A,LINK,low,high,p)//算法2.7的改型//elsemid←callMERGESORT1(low,mid,q)//返回q表//callMERGESORT1(mid+1,high,r)//返回r表//callMERGE1(q,r,p)//將表q和表r歸并成表p//endifendMERGESORT11/30/2025算法2.11使用鏈接表歸并已分類的集合

procedureMERGE1(q,r,p)//q和r是全程數(shù)組LINK(1:n)中兩個表的指針。歸并這兩個表，得到一個由p所指示的新表。此表將A中的元素按非降次序分類。LINK(0)被定義//globaln,A(1:n),LINK(1:n)localintegeri,j,ki←q;j←r;k←0

//新表在LINK(0)處開始//whilei≠0andj≠0do

//當(dāng)兩表均非空時//ifA(i)≤A(j)

//找較小的關(guān)鍵字//thenLINK(k)←i;k←i;i←LINK(i)

//加一個新關(guān)鍵字到表中//elseLINK(k)←j;k←j;j←LINK(j)

//加一個新關(guān)鍵字到表中//endifrepeatifi=0thenLINK(k)=jelseLINK(k)=iendifp=LINK(0)endMERGE11/30/2025MERGESORT1的調(diào)用在初次調(diào)用時，待分類的n個元素放于A(1:n)中。LINK(1:n)初始化為0；初次調(diào)用：callMERGESORT1(1,n,p)p作為按分類次序給出A中元素的指示表的指針。3）改進(jìn)歸并分類算法示例設(shè)元素表：（50，10，25，30，15，70，35，55）采用MERGESORT1對上述元素表分類（不做小規(guī)模集合的單獨處理）下表給出在每一次調(diào)用MERGESORT1結(jié)束后，LINK數(shù)組的變化情況。1/30/2025在上表的最后一行，p=2返回，得到鏈表（2，5，3，4，7，1，8，6）即：A(2)≤A(5)≤A(3)≤A(4)≤A(7)≤A(1)≤A(8)≤A(6)1/30/20255.以比較為基礎(chǔ)分類的時間下界任何以關(guān)鍵字比較為基礎(chǔ)的分類算法，其最壞情況下的時間下界都為：Ω(nlogn)利用二元比較樹證明。假設(shè)參加分類的n個關(guān)鍵字A(1),A(2),…,A(n)互異。任意兩個關(guān)鍵字的比較必導(dǎo)致A(i)<A(j)或A(i)>A(j)的結(jié)果。以二元比較樹描述元素間的比較過程：若A(i)<A(j)，進(jìn)入下一級的左分支若A(i)>A(j)，進(jìn)入下一級的右分支1/30/2025算法在外部結(jié)點終止。從根到某外結(jié)點的路徑代表某個特定輸入情況下一種唯一的分類排序序列。路徑長度表示生成該序列代表的分類表所需要的比較次數(shù)。而最長的路徑代表算法在最壞情況下的執(zhí)行情況，該路徑的長度即是算法在最壞情況下所作的比較次數(shù)。故，以比較為基礎(chǔ)的分類算法的最壞情況下界等于該算法對應(yīng)的比較樹的最小高度。1/30/2025①由于n個關(guān)鍵字有n!種可能的排列，所以二元比較樹中將有n!個外部結(jié)點：每種排列對應(yīng)于某種特定輸入情況下的分類情況，每個外部結(jié)點表示一種可能的分類序列。②設(shè)一棵二元比較樹的所有內(nèi)結(jié)點的級數(shù)均小于或等于k，則該樹中最多有2k個外結(jié)點。記算法在最壞情況下所作的比較次數(shù)為T(n)，則有T(n)=k：生成外結(jié)點所代表的分類序列所需的比較次數(shù)等于該外結(jié)點所在的級數(shù)-1；根據(jù)①和②的分析，有：

n!≤2T(n)化簡：當(dāng)n>1時，有n!≥n(n-1)(n-2)…()≥(n/2)n/2當(dāng)n≥4時，有T(n)≥(n/2)log(n/2)≥(n/4)logn故，任何以比較為基礎(chǔ)的分類算法的最壞情況的時間下界為：

Ω(nlogn)

1/30/20252.5快速分類任何一個基于比較來確定兩個元素相對位置的排序算法需要Ω(nlogn)計算時間。如果我們能設(shè)計一個需要O(n1ogn)時間的排序算法，則在漸近的意義上，這個排序算法就是最優(yōu)的。許多排序算法都是追求這個目標(biāo)。下面介紹快速排序算法，它在平均情況下需要O(nlogn)時間。這個算法是由C.A.R.Hoare發(fā)明的。1.問題描述分類問題2.劃分快速分類是一種基于劃分的分類方法；

劃分：選取待分類集合A中的某個元素t，按照與t的大小關(guān)系重新整理A中元素，使得整理后的序列中所有在t以前出現(xiàn)的元素均小于等于t，而所有出現(xiàn)在t以后的元素均大于等于t。這一元素的整理過程稱為劃分（Partitioning）。元素t稱為劃分元素。

快速分類：通過反復(fù)地對待排序集合進(jìn)行劃分達(dá)到分類目的的分類算法。1/30/2025劃分過程（PARTITION）的算法描述算法2.2用A(m)劃分集合A(m:p-1)procedurePARTITION(m,p)integerm,p,i;globalA(m:p-1)v←A(m);i←m//A(m)是劃分元素//looploopi←i+1untilA(i)≥vrepeat//i由左向右移//loopp←p-1untilA(p)≤vrepeat//p由右向左移//ifi<pthencallINTERCHANGE(A(i),A(p))elseexitendifrepeatA(m)←A(p)；A(p)←v//劃分元素在位置p//endPARTITION1/30/2025注：算法對集合A(m:p-1)進(jìn)行劃分。并使用待劃分區(qū)間的第一個元素A(m)作為劃分元素A(p)不在劃分區(qū)間內(nèi)，但被定義，且A(p）≥A(m)，用于限界1/30/2025例2.5劃分實例(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)ipA:657075808560555045+∞29

|……|A:654575808560555070+∞38

|…………|A:654550808560557570+∞47

|………………|A:6545505585

60807570+∞56

|……|A:654550556085807570+∞65

|……|A:604550556585807570+∞劃分元素定位于此交換劃分元素1/30/2025經(jīng)過一次“劃分”后，實現(xiàn)了對集合元素的調(diào)整：其中一個子集合的所有元素均小于等于另外一個子集合的所有元素。按同樣的策略對兩個子集合進(jìn)行分類處理。當(dāng)子集合分類完畢后，整個集合的分類也完成了。這一過程避免了子集合的歸并操作。這一分類過程稱為快速分類。1/30/20253.快速分類通過反復(fù)使用劃分過程PARTITION實現(xiàn)對集合元素分類的算法。算法2.13快速分類procedureQUICKSORT(p,q)//將數(shù)組A(1:n)中的元素A(p),…A(q)按遞增的方式分類。A(n+1)有定義，且假定A(n+1)←+∞//integerp,q;globaln,A(1:n)ifp<qthen

j←q+1

//進(jìn)入時，A(j)定義了劃分區(qū)間[p,q]的上界，初次調(diào)用時j=n+1callPARTITION(p,j)//出口時，j帶出此次劃分后劃分元素所在的坐標(biāo)位置//callQUICKSORT(p,j-1)//前一子集合上遞歸調(diào)用callQUICKSORT(j+1,q)//后一子集合上遞歸調(diào)用endifendQUICKSORT1/30/20254.快速分類分析統(tǒng)計的對象：元素的比較次數(shù)，記為：C(n)兩點假設(shè)

①參加分類的n個元素各不相同

②PARTITION中的劃分元素v是隨機(jī)選取的（針對平均情況的分析）隨機(jī)選取劃分元素：在劃分區(qū)間[m,p]隨機(jī)生成某一坐標(biāo)：i←RANDOM(m,p-1)；調(diào)換A(m)與A(i):v←A(i);A(i)←A(m);i←m作用：將隨機(jī)指定的劃分元素的值依舊調(diào)換到A(m)位置。之后，算法主體不變，仍從A(m)開始執(zhí)行劃分操作。1/30/2025遞歸層次QuickSort(1,n)QuickSort(1,j1-1)QuickSort(j1-1,n)QuickSort(1,j21-1)QuickSort(j21+1,j1-1)QuickSort(j1-1,j22-1)QuickSort(j22+1,n)n個元素參加劃分和分類去掉1個第一級的劃分元素n-1個元素參加劃分和分類去掉2個第二級的劃分元素n-3個元素參加劃分和分類去掉4個第三級的劃分元素第一層第二層第三層設(shè)在任一級遞歸調(diào)用上，調(diào)用PARTITION處理的所有元素總數(shù)為r，則，初始時r=n，以后的每級遞歸上，由于刪去了上一級的劃分元素，故r比上一級至少少1：理想情況，第一級少1，第二級少2，第三級少4，…；最壞情況，每次僅減少1（如集合元素已經(jīng)按照遞增或遞減順序排列）1/30/2025最壞情況分析記最壞情況下的元素比較次數(shù)是Cw(n)；PARTITION一次調(diào)用中的元素比較數(shù)是p-m+1，故每級遞歸調(diào)用上，元素的比較次數(shù)等于該級所處理的待分類元素數(shù)。

最壞情況下，每級遞歸調(diào)用的元素總數(shù)僅比上一級少1，故Cw(n)是r由n到2的累加和。即：Cw(n)==Ο(n2)1/30/2025平均情況分析

平均情況是指集合中的元素以任一一種順序排列，且任選所有可能的元素作為劃分元素進(jìn)行劃分和分類，在這些所有可能的情況下，算法執(zhí)行性能的平均值。設(shè)調(diào)用PARTITION(m,p)時，所選取劃分元素v恰好是A(m:p-1)中的第i小元素（1≤i≤p-m）的概率相等。則經(jīng)過一次劃分，所留下的待分類的兩個子文件恰好是A(m:j-1)和A(j+1:p-1)的概率是：1/(p-m),m≤j<p。則有，

其中，n+1是PARTITION第一次調(diào)用時所需的元素比較次數(shù)。CA(0)=CA(1)=0

1/30/2025化簡上式可得：CA(n)/(n+1)=CA(n-2)/(n-1)+2/n+2/(n+1)=CA(n-3)/(n-2)+2/(n-1)+2/n+2/(n+1)…=CA(1)/2+由于所以得，CA(n)<2(n+1)loge(n+1)=Ο(nlogn)1/30/20255.快速分類算法的迭代模型消去遞歸（略）6.快速分類與歸并分類比較兩者平均情況時間都是Ο(nlogn），平均情況下哪種快一些？實驗證明快速分類要快一些1/30/2025實驗1實現(xiàn)歸并分類和快速分類算法，并比較二者的時間性能。要求：撰寫實驗報告，包括實驗?zāi)康?、方法、結(jié)果等，另附源程序清單1/30/20252.6選擇問題1.問題描述給出含有n個元素表A(1:n)，要求確定其中的第k小元素。2.設(shè)計思路利用PARTITION過程。如果劃分元素v測定在A(j)的位置上，則有j-1個元素小于或等于A(j)，且有n-j個元素大于或等于A(j)。此時，若k=j，則A(j)即是第k小元素；否則，若k<j，則第k小元素將出現(xiàn)在A(1:j-1)中；若k>j，則第k小元素將出現(xiàn)在A(j+1:n)中。1/30/20253.利用PARTITION實現(xiàn)的選擇算法算法描述算法2.15找第k小元素procedureSELECT(A,n,k)//在數(shù)組A(1:n)中找第k小元素，并將之放在A(k)中。//integern,k,m,r,j; m←1;r←n+1;A(n+1)←+∞

//A(n+1)被定義，并置為一大值，用于限界//loop//在進(jìn)入循環(huán)時，1≤m≤k≤r≤n+1//j←r//將剩余元素的最大下標(biāo)加1后置給j//callPARTITION(m.j)//返回j,它使得A(j)是第j小的值//case:k=j:return:k<j:r←j//j是新的上界//:else:m←j+1//k>j,j+1是新的下界//endcaserepeatendSELECT1/30/2025算法分析兩點假設(shè)①A中的元素互異②隨機(jī)選取劃分元素，且選擇A中任一元素作為劃分元素的概率相同分析每次調(diào)用PARTITION（m,j),所需的元素比較次數(shù)是

Ο(j-m+1)。在執(zhí)行一次PARTITION后，或者找到第k小元素，或者將在縮小的子集(A(m,k-1)或A(k+1,j))中繼續(xù)查找?？s小的子集的元素數(shù)將至少比上一次劃分的元素數(shù)少1。1/30/20251)最壞情況SELECT的最壞情況時間是Ο(n2)

當(dāng)A中的元素已經(jīng)按照遞增的順序排列，且k=n。此時，需要n次調(diào)用PARTITION過程，且每次返回的元素位置是子集中的第一個元素，子集合的元素數(shù)一次僅減少１，而j值不變。則,n次調(diào)用的時間總量是1/30/20252)平均情況

設(shè)是找A(1:n)中第k小元素的平均時間。是SELECT的平均計算時間，則有并定義則有：T(n)≤R(n)。1/30/2025定理2.4SELECT的平均計算時間TA(n)是Ο(n)證明：PARTITION和SELECT中，case語句的執(zhí)行時間是Ο(n)。在隨機(jī)等概率選擇劃分元素時，首次調(diào)用PARTITION中劃分元素v剛好是A中第i小元素的概率為1/n，1≤i≤n。則，存在正常數(shù)c，c>0,有，n≥2且有，n≥2

1/30/2025令c≥R(1)。利用數(shù)學(xué)歸納法證明，對所有n≥2，有R(n)≤4cn.①當(dāng)n=2時，由上式得：②假設(shè)對所有得n,2≤n<m，有R(n)≤4cn③當(dāng)n=m時，有，由于R(n)是n的非降函數(shù)，故在當(dāng)m為偶數(shù)而k=m/2，或當(dāng)m為奇數(shù)而k=(m+1)/2時，取得極大值。因此，

若m為偶數(shù)，則

若m為奇數(shù)，則由于TA(n)≤R(n)，所以TA(n)≤4cn。故，TA(n)=Ο(n)1/30/20254.最壞情況是Ο(n)的選擇算法1）采用兩次取中間值的規(guī)則精心選取劃分元素首先，將參加劃分的n個元素分成組，每組有r個元素(r≥1)。（多余的個元素忽略不計）然后，對這組每組的r個元素進(jìn)行分類并找出其中間元素mi,1≤i≤，共得個中間值。之后，對這個中間值分類，并找出其中間值mm。將mm作為劃分元素執(zhí)行劃分。2）算法描述1/30/2025算法2.16使用二次取中規(guī)則得選擇算法的說明性描述procedureSELECT2(A,k,n)//在集合A中找第k小元素，使用兩次取中規(guī)則//①若n≤r，則采用插入法直接對A分類并返回第k小元素②把A分成大小為r的個子集合，忽略多余的元素③設(shè)M={m1,m2,…m}是子集合的中間值集合④v←SELECT2(M,,)⑤j←PARTITION(A，v)

//v作為劃分元素，劃分后j等于劃分元素所在位置的下標(biāo)//⑥case:k=j:return(v):k<j:設(shè)S是A(1:j-1)中元素的集合return(SELECT2(S,k,j-1)):else:設(shè)R是A(j+1:n)中元素的集合return(SELECT2(R,k-j,n-j))endcaseendSELECT21/30/2025例：設(shè)n=35,r=7。分為n/r=5個元素組：B1，B2，B3，B4，B5；每組有7個元素。

B1-B5按照各組的mi的非增次序排列。

mm=mi的中間值，1≤i≤5由圖所示有：mm中間值小于等于mm的元素大于等于mm的元素非降次序B1B2B3B4B5按照mi的非降次序排列1/30/2025由于r個元素的中間值是第小元素。則，至少有個mi小于或等于mm；至少有個mi大于或等于mm。則，至少有個元素小于或等于（或大于或等于）mm。

當(dāng)r=5，則使用兩次取中間值規(guī)則來選擇v=mm，可推出，至少有個元素小于或等于選擇元素v。至多有個元素大于v。至多有0.7n+1.2個元素小于v。

故，這樣的v可近似平均地劃分A中的n個元素。1/30/20252)算法分析記T(n)是SELECT2所需的最壞情況時間對特定的r分析SELECT2:選取r=5。假定A中的元素各不相同，則有①若n≤r，則采用插入法直接對A分類并返回第k小元素→Ο(1)②把A分成大小為r的個子集合，忽略多余的元素→Ο(n)③設(shè)M={m1,m2,…m}是子集合的中間值集合→Ο(n)④v←SELECT2(M,,)→T(n/5)⑤j←PARTITION(A，v)→Ο(n)⑥case→T(3n/4),n≥24:k=j:return(v):k<j:設(shè)S是A(1:j-1)中元素的集合;return(SELECT2(S,k,j-1)):else:設(shè)R是A(j+1:n)中元素的集合;return(SELECT2(R,k-j,n-j))endcaseendSELECT21/30/2025故有，cnn＜24,T(n)＝T(n/5)+T(3n/4)+cnn≥24用歸納法可證：T(n)≤20cn即，T(n)=Ο(n)1/30/2025當(dāng)A中的元素不盡相同步驟⑤經(jīng)PARTITION調(diào)用所產(chǎn)生的S和R兩個子集合中可能存在一些元素等于當(dāng)前的劃分元素v,可能導(dǎo)致|S|或|R|大于0.7n+1.2。此時上述處理作一下改進(jìn)：方法一：將A集合分成3個子集合U,S和R，其中U是有A中所有與v相同的元素組成，S是由A中所有比v小的元素組成，R則是A中所有比v大的元素組成。同時步驟⑥更改：case:|S|≥k:return(SELECT2(S,k,|S|):|S|+|U|≥k:return(v):else:return(SELECT2(R,k-|S|-|U|,|R|))endcase

從而保證|S|+|R|≤0.7n+1.2成立，故關(guān)于T(n)的分析仍然成立。

T(n)=Ο(n)1/30/2025方法二：選取其他的r值進(jìn)行計算特例：當(dāng)r=5,且A中的元素不盡相同。假設(shè)其中有0.7n+1.2個元素比v小而其余的元素都等于v的情況。則，經(jīng)過PARTITION，在這些等于v的元素中至多有一半可能在S中，故|S|≤0.7n+1.2+(0.3n-1.2)/2=0.85n+0.6同理，|R|≤0.85n+0.6可得，步驟④和⑥此時所處理的元素總數(shù)將是1.05n+0.6>n不再是線性關(guān)系。故有T(n)≠Ο(n)改進(jìn)：取r=9。經(jīng)計算可得，此時將有個元素小于或等于v，同時至少有同樣多的元素大于或等于v。則當(dāng)n≥90時，|S