分治法-分而治之課件

第四章分治法

——“分”而治之4.1一般方法對大規(guī)模問題的求解利用分治法求解大規(guī)模問題1.基本思想分而治之方法法與軟件設(shè)計的模塊化方法非常相似。為解決一個大問題，可以（1）把它分解成兩個或多個更小的問題；（2）分別解決每個小問題；（3）把各小問題的解答組合起來，即可得到原問題的解。小問題通常與原問題相似或同質(zhì)，因而可以遞歸地使用分而治之策略解決。10/8/2023第四章分治法

——1通常，子問題與原始問題“同質(zhì)”10/8/2023通常，子問題與原始問題“同質(zhì)”10/6/20232例[找偽幣]假設(shè)16枚金幣中有一枚是偽造的，真假金幣的區(qū)別僅是重量不同(偽幣輕一些），利用一個沒有砝碼的天平作工具，找出這枚偽造的金幣。

方法1：比較硬幣1和2的重量，有一個輕則找到；否則比較硬幣3和4，依次比較下去，直到找到。最多8次比較。方法2：利用分治法。16個硬幣分為兩組，每組8個，比較重量，偽幣在輕的一組。將輕的一組再分為兩組，每組4個……繼續(xù)劃分下去，依次每組2個，每組1個，此時找到。10/8/2023例[找偽幣]假設(shè)16枚金幣中有一枚是偽造的，真假金幣的3算法4.1分治策略的抽象化控制procedureDANDC(p,q)globaln,A(1:n);integerm,p,q;//1≤p≤q≤n//ifSMALL(p,q)thenreturn(G(p,q))elsem←DIVIDE(p,q)//p≤m＜q//return(COMBINE(DANDC(p,m),DANDC(m+1,q)))endifendDANDC注：k=2:二分是最常用的分解策略；SMALL(p,q)：布爾函數(shù)，判斷輸入規(guī)模q-p+1是否足夠小而無需再進一步分就可求解；G(p,q)：對輸入規(guī)模為q-p+1的子問題求解（SMALL(p,q)為真時）；DIVIDE(p.q)：對輸入規(guī)模為q-p+1的子問題進一步分解，返回值為[p,q]區(qū)間進一步的分割點（SMALL(p,q)不為真時）；COMBINE(x,y)：子結(jié)果的合并函數(shù)，將區(qū)間[p,m]和[m+1,q]上的子問題的解合并成上級區(qū)間[p,q]上的“較完整”的解。當(dāng)p=1,q=n時，就得到整個問題的解。2.分治策略的抽象化控制10/8/2023算法4.1分治策略的抽象化控制注：2.分治策略的抽象化4DANDC的計算時間若所分成的兩個子問題的輸入規(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é)果進行合并的時間（該公式針對具體問題有各種不同的變形）10/8/2023DANDC的計算時間10/6/202354.2二分檢索（折半查找）1.問題的描述已知一個按非降次序排列的元素表a1,a2,…,an,判定某給定的元素x是否在該表中出現(xiàn)。若是，則找出x在表中的位置并返回其所在下標(biāo)若非，則返回0值。10/8/20234.2二分檢索（折半查找）1.問題的描述10/6/2026分治求解策略分析：定義問題的形式描述：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上的求解可再次采用分治方法劃分后求解（遞歸過程）10/8/2023分治求解策略分析：10/6/202372.二分檢索算法算法4.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=010/8/20232.二分檢索算法算法4.3二分檢索注：10/6/20238例2.1：設(shè)A(1:9)=(-15，-6，0，7，9，23，54，82，101)在A中檢索x=101，-14，82。執(zhí)行軌跡見下表1表1運行軌跡示例x=101x=-14x=82lowhighmidlowhighmidlowhighmid19519519569714269789811189899921找不到找到

找到

成功的檢索不成功的檢索成功的檢索10/8/2023例2.1：設(shè)A(1:9)=(-15，-6，0，7，9，23，93.算法的正確性證明定理4.1過程BINSRCH(A,n,x,j)能正確運行證明：1）在具體指定A中的數(shù)據(jù)元素及x的數(shù)據(jù)類型后，算法中的所有運算都能按要求正確運行——即首先滿足確定性和能行性2）終止性算法初始部分置low←1,high←n

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

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

因low,high,mid都是整型變量，故按照上述規(guī)則，在有限步內(nèi)，或找到某個mid，有A(mid)=x；或變得low>high，在A中沒有找到任何元素等于x，算法終止。10/8/20233.算法的正確性證明10/6/2023104.性能分析1）空間特性n+5個空間位置——О(n)2)時間特性區(qū)分以下情況，并進行相應(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ù)最多，計算時間最長成功/不成功檢索的平均情況：一般情況下的計算時間10/8/20234.性能分析1）空間特性10/6/202311實例分析（例4.1）頻率計數(shù)特征while循環(huán)體外語句的頻率計數(shù)為1集中考慮while循環(huán)中的x與A中元素的比較（其它運算的頻率計數(shù)與之有相同的數(shù)量級）假定只需一次比較就可確定case語句控制是三種情況的哪一種。查找每個元素所需的元素比較次數(shù)統(tǒng)計如下：A⑴⑵⑶⑷⑸⑹⑺⑻⑼元素-15-6079235482101成功檢索比較次數(shù)323413234

不成功檢索比較次數(shù)333443334410/8/2023實例分析（例4.1）頻率計數(shù)特征12成功檢索最好：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次10/8/202310/6/202313二元比較樹算法執(zhí)行過程的主體是x與一系列中間元素A(mid)比較。可用一棵二元樹描述這一過程，并稱之為二元比較樹。構(gòu)造：比較樹由稱為內(nèi)結(jié)點和外結(jié)點的兩種結(jié)點組成：內(nèi)結(jié)點：表示一次元素比較，用圓形結(jié)點表示，存放一個mid值；代表一次成功檢索；外結(jié)點：在二分檢索算法中表示一種不成功檢索的情況，用方形結(jié)點表示。路徑：表示一個元素的比較序列。例4.1的二元比較樹10/8/2023二元比較樹算法執(zhí)行過程的主體是x與一系列中間元素A(mid)14基于二元比較樹的分析若x在A中出現(xiàn)，則算法的執(zhí)行過程在一個圓形的內(nèi)結(jié)點處結(jié)束。若x不在A中出現(xiàn)，則算法的執(zhí)行過程在一個方形的外結(jié)點處結(jié)束——外結(jié)點不代表元素的比較，因為比較過程在該外結(jié)點的上一級的內(nèi)結(jié)點處結(jié)束。

例4.1的二元比較樹10/8/2023基于二元比較樹的分析例4.1的二元比較樹10/6/202315定理4.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-110/8/2023定理4.2若n在區(qū)域[2k-1,2k)中，則對于一次成功16BINSRCH計算復(fù)雜度的理論分析1）不成功檢索的最好、最壞和平均情況的計算時間均為——外結(jié)點處在最末的兩級上；2）最好情況下的成功檢索的計算時間為最壞情況下的成功檢索的計算時間為10/8/2023BINSRCH計算復(fù)雜度的理論分析1）不成功檢索的最好、最壞173）平均情況下的成功檢索的計算時間分析利用外部結(jié)點和內(nèi)部結(jié)點到根距離和之間的關(guā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)=10/8/20233）平均情況下的成功檢索的計算時間分析10/6/2023184.以比較為基礎(chǔ)檢索的時間下界問題：設(shè)n個元素的數(shù)組A(1:n)有A(1)<A(2)<…<A(n)。檢索一給定元素x是否在A中出現(xiàn)。定理4.2給出了二分檢索算法的時間下界，是否預(yù)計還存在有以元素比較為基礎(chǔ)的另外的檢索算法，它在最壞情況下比二分檢索算法在計算時間上有更低的數(shù)量級?以比較為基礎(chǔ)的算法：假定算法中只允許進行元素間的比較，而不允許對它們實施其它運算。10/8/20234.以比較為基礎(chǔ)檢索的時間下界問題：設(shè)n個元素的數(shù)組A(119注：每個內(nèi)結(jié)點表示一次元素的比較。每棵比較樹中恰好含有n個內(nèi)結(jié)點，分別與n個不同i值相對應(yīng)；每個外結(jié)點對應(yīng)一次不成功的檢索，并恰好又n+1個外結(jié)點對應(yīng)于n+1中不成功檢索的情況。任何以比較為基礎(chǔ)的檢索算法，其執(zhí)行過程都可以用二元比較樹來描述。10/8/2023注：每個內(nèi)結(jié)點表示一次元素的比較。每棵比較樹中恰好含有n個內(nèi)20以比較為基礎(chǔ)的有序檢索問題最壞情況的時間下界定理4.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,即10/8/2023以比較為基礎(chǔ)的有序檢索問題最壞情況的時間下界證明：從21任何一種以比較為基礎(chǔ)的算法，在最壞情況下的計算時間都不低于Ο(logn)。因此，不可能存在最壞情況比二分檢索數(shù)量級還低的算法。二分檢索是解決檢索問題的最優(yōu)的最壞情況算法。10/8/2023任何一種以比較為基礎(chǔ)的算法，在最壞情況下的計算時間都不低于Ο224.3找最大和最小元素問題描述：給定含有n個元素的集合，在其中找出最大和最小元素。10/8/20234.3找最大和最小元素問題描述：給定含有n個元素的集合，在231.直接找最大和最小元素算法4.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

算法的性能：只考慮算法中的比較運算，以此代表算法的執(zhí)行特征；該算法最好、最壞、平均情況下均需要做2(n-1)次元素比較10/8/20231.直接找最大和最小元素算法的性能：10/6/202324STRAITMAXMIN算法的一種簡單改進形式: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次10/8/2023STRAITMAXMIN算法的一種簡單改進形式:10/6/2252.分治求解策略記問題的一個實例為：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è)計策略，得到以下算法：10/8/20232.分治求解策略10/6/2023263.一種遞歸求解策略算法4.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)endcaseendMAXMIN10/8/20233.一種遞歸求解策略算法4.6遞歸求取最大和最小元素1027例：在A(1:9)=(22,13,-5,-8,15,60,17,31,47)上執(zhí)行算法4.6每個結(jié)點內(nèi)的值分別是：i,j,fmax,fmin遞歸調(diào)用遞歸調(diào)用分解過程遞歸調(diào)用的返回10/8/2023例：在A(1:9)=(22,13,-5,-8,15,6028性能分析(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-210/8/2023性能分析(T(n)表示元素比較數(shù)）10/6/202329性能分析1）與STRAITMAXMIN算法相比，比較次數(shù)減少了25%（3n/2-2:2n-2)。已經(jīng)達到了以元素比較為基礎(chǔ)的找最大最小元素的算法計算時間的下界：2）存在的問題：空間占用量大

?有

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

?i,j,fmax,fmin和返回地址五個值。時間可能不比預(yù)計的理想如果元素A(i)和A(j)的比較與i和j的比較相差不大時，算法MAXMIN不可取。10/8/2023性能分析10/6/202330假設(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Ｎ算法。10/8/2023假設(shè)元素的比較與i和j的比較時間相同（整型數(shù)）。31結(jié)論：如果A中的元素間的比較代價遠比整型數(shù)（下標(biāo)）的比較昂貴，則分治方法將產(chǎn)生一個效率較高的算法；反之，可能僅得到一個低效的算法。故，分治策略只能看成一個較好的但并不總是成功

的算法設(shè)計指導(dǎo)。10/8/2023結(jié)論：如果A中的元素間的比較代價遠比整型數(shù)10/6/202332思考題：最大子段和問題求數(shù)列的最大子段和。給定n個元素的整數(shù)列(可能為負整數(shù))a1，a2，…，an，求形如ai，ai+1，aj，i，j=1，2，…，n，i<=j的子段，使其和為最大。例如，當(dāng)(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2) max_sum=20，best_i=2，best_j=410/8/2023思考題：最大子段和問題求數(shù)列的最大子段和。 max_sum33若用一般的二分法解決該實例？分解為兩組(-2,11,-4)和(13,-5,-2)1113不獨立，子問題中間有公共子問題10/8/2023若用一般的二分法解決該實例？分解為兩組(-2,11,-434對重疊子問題專門處理“三”分治情形1情形2情形3將a[1..n]分為長度相等的2段a[1..(n/2)]和a[(n/2)+1..n],分別求這2段最大子段和,則a[1.n]最大子段和有3種情形:1)a[1..n]的最大子段和與a[1..(n/2)]的最大子段和相同；2)a[1..n]的最大子段和與a[(n/2)+1..n]的最大字段和相同;3)a[1..n]的最大字段和為a[i..j],且1≤i≤(n/2),(n/2)+1≤j≤n。情況1)和情況2)可分別遞歸求得。對于情況3）,a[(n/2)]與a[(n/2)+1]一定在最大子段中。因此,可以計算出a[i..(n/2)]最大值s1和a[(n/2)+1..j]最大值s2。則s1+s2即為情況3)時最優(yōu)值。10/8/2023對重疊子問題專門處理“三”分治情形1情形2情形3將a[1..35“三”分治情形1情形2情形3對分解得到的左右子段，求左右子段內(nèi)部的最大子段和；左子段中滿足以下條件的最大的子段和s1：以任何位置i開始，結(jié)尾處n/2結(jié)束；右子段中滿足以下條件的最大的子段和s2：以起始位置n/2+1開始，任何位置j結(jié)束；原問題最大子段和是左右子段內(nèi)最大和與兩個子段最大值求和s1+s2中的大者。10/8/2023“三”分治情形1情形2情形3對分解得到的左右子段，求原問題最364.4歸并分類1.分類問題——排序給定一n個元素的集合A，按照某種方法將A中的元素按非降或非增次序排列。分類：內(nèi)排序，外排序常見內(nèi)排序方法：冒泡排序插入排序歸并排序快速排序堆排序…[例]輸入：（8，5，4，9）輸出：（4，5，8，9）或（9，8，5，4）10/8/20234.4歸并分類1.分類問題——排序[例]10/6/372.插入分類

算法4.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)10/8/20232.插入分類(8,5,4,9)10/6/202338性能分析：最壞情況：輸入數(shù)據(jù)按非增次序排列,每次內(nèi)層while循環(huán)執(zhí)行j次（j=2,3,…,n)。則有，最好情況：輸入數(shù)據(jù)已按非降序排列，不進入while循環(huán)，則最好情況下計算時間為Ω(n)10/8/2023性能分析：10/6/2023393.分治策略求解

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

10/8/20233.分治策略求解10/6/202340算法4.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)//歸并已分類的兩子集合//endifendMERGESORT10/8/2023算法4.8歸并分類10/6/202341算法4.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中//endMERGE10/8/2023算法4.9使用輔助數(shù)組歸并兩個已分類的集合10/6/242性能分析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)

10/8/2023性能分析10/6/202343歸并分類示例設(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，86125442386145052010/8/2023歸并分類示例設(shè)A=（310，285，179，652，351，442）歸并過程首先進入左分枝的劃分與歸并。首先形成的劃分狀態(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）進入右分枝的劃分與歸并過程（略）10/8/20232）歸并過程10/6/2023453）用樹結(jié)構(gòu)描述歸并分類過程10/8/20233）用樹結(jié)構(gòu)描述歸并分類過程10/6/2023464.歸并分類算法的改進1）算法4.8存在的問題遞歸層次太深在MERGESORT的執(zhí)行過程中，當(dāng)集合僅含有兩個元素時，仍要進一步做遞歸調(diào)用，直至每個集合僅含有一個元素時才退出遞歸調(diào)用。在集合含有僅相當(dāng)少的元素時，較深層次的遞歸調(diào)用使得時間過多地消耗在處理遞歸上。元素在數(shù)組A和輔助數(shù)組B之間的頻繁移動每次歸并，都要首先將A中的元素移到B中，在由B復(fù)制到A的對應(yīng)位置上。10/8/20234.歸并分類算法的改進1）算法4.8存在的問題10/6/2472）改進措施針對遞歸層次問題采用能在小規(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)。10/8/20232）改進措施10/6/202348例：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)系取得。10/8/2023例：10/6/202349改進后的歸并分類模型算法4.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//endifendMERGESORT110/8/2023改進后的歸并分類模型算法4.10使用鏈接信息數(shù)組的歸并分50算法4.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)endMERGE110/8/2023算法4.11使用鏈接表歸并已分類的集合10/6/202351MERGESORT1的調(diào)用在初次調(diào)用時，待分類的n個元素放于A(1:n)中。LINK(1:n)初始化為0；初次調(diào)用：callMERGESORT1(1,n,p)p作為按分類次序給出A中元素的指示表的指針。3）改進歸并分類算法示例設(shè)元素表：（50，10，25，30，15，70，35，55）采用MERGESORT1對上述元素表分類（不做小規(guī)模集合的單獨處理）下表給出在每一次調(diào)用MERGESORT1結(jié)束后，LINK數(shù)組的變化情況。10/8/2023MERGESORT1的調(diào)用10/6/202352在上表的最后一行，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)10/8/2023在上表的最后一行，p=2返回，得到鏈表（2，5，3，4，7，535.以比較為基礎(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)，進入下一級的左分支若A(i)>A(j)，進入下一級的右分支10/8/20235.以比較為基礎(chǔ)分類的時間下界任何以關(guān)鍵字54算法在外部結(jié)點終止。從根到某外結(jié)點的路徑代表某個特定輸入情況下一種唯一的分類排序序列。路徑長度表示生成該序列代表的分類表所需要的比較次數(shù)。而最長的路徑代表算法在最壞情況下的執(zhí)行情況，該路徑的長度即是算法在最壞情況下所作的比較次數(shù)。故，以比較為基礎(chǔ)的分類算法的最壞情況下界等于該算法對應(yīng)的比較樹的最小高度。10/8/2023算法在外部結(jié)點終止。10/6/202355①由于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)

10/8/2023①由于n個關(guān)鍵字有n!種可能的排列，所以二元比較樹564.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ù)地對待排序集合進行劃分達到分類目的的分類算法。10/8/20234.5快速分類任何一個基于比較來確定兩個元素相對位置的排序57劃分過程（PARTITION）的算法描述算法4.12用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//endPARTITION10/8/2023劃分過程（PARTITION）的算法描述算法4.12用A58注：算法對集合A(m:p-1)進行劃分。并使用待劃分區(qū)間的第一個元素A(m)作為劃分元素A(p)不在劃分區(qū)間內(nèi)，但被定義，且A(p）≥A(m)，用于限界10/8/2023注：10/6/202359例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+∞劃分元素定位于此交換劃分元素10/8/2023例2.5劃分實例劃分元素定位于此交換劃分元素10/6/260經(jīng)過一次“劃分”后，實現(xiàn)了對集合元素的調(diào)整：其中一個子集合的所有元素均小于等于另外一個子集合的所有元素。按同樣的策略對兩個子集合進行分類處理。當(dāng)子集合分類完畢后，整個集合的分類也完成了。這一過程避免了子集合的歸并操作。這一分類過程稱為快速分類。10/8/2023經(jīng)過一次“劃分”后，實現(xiàn)了對集合元素的調(diào)整：其中613.快速分類通過反復(fù)使用劃分過程PARTITION實現(xiàn)對集合元素分類的算法。算法4.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

//進入時，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)用endifendQUICKSORT10/8/20233.快速分類10/6/2023624.快速分類分析統(tǒng)計的對象：元素的比較次數(shù)，記為：C(n)兩點假設(shè)

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

②PARTITION中的劃分元素v是隨機選取的（針對平均情況的分析）隨機選取劃分元素：在劃分區(qū)間[m,p]隨機生成某一坐標(biāo)：i←RANDOM(m,p-1)；調(diào)換A(m)與A(i):v←A(i);A(i)←A(m);i←m作用：將隨機指定的劃分元素的值依舊調(diào)換到A(m)位置。之后，算法主體不變，仍從A(m)開始執(zhí)行劃分操作。10/8/20234.快速分類分析10/6/202363遞歸層次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)按照遞增或遞減順序排列）10/8/2023遞歸層次QuickSort(1,n)QuickSort(1,64最壞情況分析記最壞情況下的元素比較次數(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)10/8/2023最壞情況分析10/6/202365平均情況分析

平均情況是指集合中的元素以任一一種順序排列，且任選所有可能的元素作為劃分元素進行劃分和分類，在這些所有可能的情況下，算法執(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

10/8/2023平均情況分析10/6/202366化簡上式可得：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)10/8/2023化簡上式可得：10/6/2023675.快速分類算法的迭代模型消去遞歸（略）6.快速分類與歸并分類比較兩者平均情況時間都是Ο(nlogn），平均情況下哪種快一些？實驗證明快速分類要快一些10/8/20235.快速分類算法的迭代模型消去遞歸（略）10/6/2023684.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)中。10/8/20234.6選擇問題1.問題描述10/6/202369舉例在四人中找第二高（即第三矮）吳宗憲，曾志偉，古天樂，周潤發(fā)10/8/2023舉例在四人中找第二高（即第三矮）10/6/2023703.利用PARTITION實現(xiàn)的選擇算法算法描述算法4.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//在進入循環(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是新的下界//endcaserepeatendSELECT10/8/20233.利用PARTITION實現(xiàn)的選擇算法算法描述10/6/71算法分析兩點假設(shè)①A中的元素互異②隨機選取劃分元素，且選擇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。10/8/2023算法分析10/6/2023721)最壞情況SELECT的最壞情況時間是Ο(n2)

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

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

10/8/2023定理4.4SELECT的平均計算時間TA(n)是Ο(n)75令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)10/8/2023令c≥R(1)。利用數(shù)學(xué)歸納法證明，對所有n≥2764.最壞情況是Ο(n)的選擇算法1）采用兩次取中間值的規(guī)則精心選取劃分元素首先，將參加劃分的n個元素分成組，每組有r個元素(r≥1)。（多余的個元素忽略不計）然后，對這組每組的r個元素進行分類并找出其中間元素mi,1≤i≤，共得個中間值。之后，對這個中間值分類，并找出其中間值mm。將mm作為劃分元素執(zhí)行劃分。2）算法描述10/8/20234.最壞情況是Ο(n)的選擇算法1）采用兩次取中間值的規(guī)則77算法4.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))endcaseendSELECT210/8/2023算法4.16使用二次取中規(guī)則得選擇算法的說明性描述10/78例：設(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的非降次序排列10/8/2023例：設(shè)n=35,r=7。分為n/r=5個元素組79由于r個元素的中間值是第小元素。則，至少有個mi小于或等于mm；至少有個mi大于或等于mm。則，至少有個元素小于或等于（或大于或等于）mm。

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

故，這樣的v可近似平均地劃分A中的n個元素。10/8/2023由于r個元素的中間值是第小元802)算法分析記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)⑥cas