計(jì)算機(jī)算法基礎(chǔ)課程

1、第二章 分治法（Divide and Conquer) “分”而治之2.1 一般方法n 對(duì)大規(guī)模問(wèn)題的求解 n 利用分治法求解大規(guī)模問(wèn)題 1.分治策略基本思想 當(dāng)問(wèn)題的規(guī)模較大而無(wú)法直接求解時(shí)，將整個(gè)問(wèn)題分成若干個(gè)小問(wèn)題，然后分而治之。 可用遞歸過(guò)程描述。一般情況下，子問(wèn)題與原始問(wèn)題“同質(zhì)”算法2.1 分治策略的抽象化控制procedure DANDC(p,q) global n.A(1:n); integer m,p,q; /1pqn/ if SMALL(p,q) then return(G(p,q) else mDIVIDE(p,q) /pmq/ return(COMBINE(DANDC(

2、p,m), DANDC(m+1,q) endifend DANDC 注：k=2: 二分是最常用的分解策略；SMALL(p,q)：布爾函數(shù)，判斷輸入規(guī)模q-p+1是否足夠小而無(wú)需再進(jìn)一步分就可求解；G(p,q)： 當(dāng)SMALL(p,q)為真時(shí)，對(duì)輸入規(guī)模為q-p+1的子問(wèn)題求解；DIVIDE(p.q)：當(dāng)規(guī)模q-p+1還較大時(shí)，對(duì)規(guī)模為q-p+1的子問(wèn)題進(jìn)一步分解，返回值為p,q區(qū)間進(jìn)一步的分割點(diǎn)；COMBINE(x,y)：子結(jié)果的合并函數(shù)，將區(qū)間p,m和m+1,q上的子問(wèn)題的解合并成區(qū)間p,q上的“較完整”的解。當(dāng)p=1,q=n時(shí)，就得到整個(gè)問(wèn)題的解。2. 分治策略的抽象化控制過(guò)程n DAND

3、C的計(jì)算時(shí)間 若所分成的兩個(gè)子問(wèn)題的規(guī)模大致相等，則DANDC總的計(jì)算時(shí)間可用遞歸關(guān)系式表示如下： g(n) n足夠小 T(n) = 2T(n/2) + f(n) 否則 注： T(n)：表示輸入規(guī)模為n的DANDC計(jì)算時(shí)間 g(n)：表示對(duì)足夠小的輸入規(guī)模直接求解的計(jì)算時(shí)間 f(n)：表示COMBINE對(duì)兩個(gè)子區(qū)間的子結(jié)果進(jìn)行合并 的時(shí)間 （該公式針對(duì)具體問(wèn)題有各種不同的變形）2.2 二分檢索（折半查找）1. 問(wèn)題的描述 已知一個(gè)按非降次序排列的元素表a1, a2, ,an，判定某給定的元素x是否在該表中出現(xiàn)。 若是，則找出x在表中的位置并返回其所在位置 的下標(biāo) 若非，則返回0值。問(wèn)題的形式描

4、述： I=(n, a1, a2, ,an,x)n 問(wèn)題分解：選取下標(biāo)k，由此將I分解為3個(gè)子問(wèn)題： I1=(k-1, a1, a2, ,ak-1,x) I2=(1, ak,x) I3=(n-k, ak+1, a2, ,an,x) 對(duì)于I2，若ak=x，則有解k，對(duì)I1、I3不用再求解；否則， 若xak，則只在I3中求解，對(duì)I1不用求解； 對(duì)I1 、I3的求解可再次采用分治方法求解2. 二分檢索 二分檢索：每次選取中間元素的下標(biāo)算法2.3 二分檢索procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low1; highn; while low

5、high do mid case :xA(mid):low mid+1 :else:jmid;return endcase repeat j0end BINSRCHhigh)/2(low注： 給定一個(gè)按非降次序排列的元素?cái)?shù)組A(1:n)，n1,判斷x是否出現(xiàn)。若是，置j，使得x=A(j)若非，j=0例2.1：設(shè)A(1:9)=(-15，-6，0，7，9，23，54，82，101) 在A中檢索x=101，-14，82。執(zhí)行軌跡見(jiàn)下表1表1 運(yùn)行軌跡示例x=101x=-14x=82lowhighmidlowhighmidlowhighmid195195195697142697898111898999

6、21找不到找到找到成功的檢索不成功的檢索成功的檢索定理2.1 過(guò)程BINSRCH(A,n,x,j)能正確運(yùn)行證明：1）在具體指定A中的數(shù)據(jù)元素及x的數(shù)據(jù)類型后，算法中的所有運(yùn)算都 能按要求正確運(yùn)行即首先滿足確定性和能行性2）終止性 算法初始部分置low1, highn 若n=0，不進(jìn)入循環(huán)，j置0，算法終止 否則，進(jìn)入循環(huán)，計(jì)算mid, 或 x=A(mid)，j置為mid，算法終止； 或xA(mid)，置lowmid+1，進(jìn)入下次循環(huán)；搜索范圍實(shí)際縮小 為mid+1, high，對(duì)low, mid-1區(qū)間不做進(jìn)一步搜索； 因low, high, mid都是整型變量，故按照上述規(guī)則，在有限步內(nèi)，

7、或找到某個(gè)mid，有A(mid) = x；或變得lowhigh，在A中沒(méi)有找到任何元素等于x，算法終止。3. 性能分析1）空間特性 n+5個(gè)空間位置(A,x,j, mid,low,high)(n)2) 時(shí)間特性 區(qū)分以下情況進(jìn)行分析 成功檢索：指所檢索的x恰好在A中出現(xiàn)。 由于A中共有n個(gè)元素，故成功檢索恰好有n種可能的情況 不成功檢索：指x不出現(xiàn)在A中。 根據(jù)取值，不成功檢索共有n+1種可能的情況（取值區(qū)間）： xA(1) 或 A(i)xA(i+1),1iA(n) 成功/不成功檢索的最好情況：執(zhí)行步數(shù)最少，計(jì)算時(shí)間最短成功/不成功檢索的最壞情況：執(zhí)行步數(shù)最多，計(jì)算時(shí)間最長(zhǎng)成功/不成功檢索的平

8、均情況：一般情況下計(jì)算時(shí)間的平均值實(shí)例分析（例2.1）運(yùn)算的頻率計(jì)數(shù)1. while循環(huán)體外語(yǔ)句的頻 率計(jì)數(shù)為12. 集中考慮while循環(huán)中x與A 中元素的比較運(yùn)算 其它運(yùn)算的頻率計(jì)數(shù) 與比較運(yùn)算相同的數(shù)量級(jí) 3. case語(yǔ)句的分析：假定只 需一次比較就可確定case 語(yǔ)句控制是三種情況的哪 一種。procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low1; highn; while lowhigh do mid case :xA(mid):low mid+1 :else:jmid;return endcase repeat j0en

9、d BINSRCHhigh)/2(low實(shí)例分析（例2.1）查找每個(gè)元素所需的元素比較次數(shù)統(tǒng)計(jì)如下： A 元素 -15 -6 0 7 9 23 54 82 101成功檢索比較次數(shù) 3 2 3 4 1 3 2 3 4 不成功檢索比較次數(shù) 3 3 3 4 4 3 3 3 4 4成功檢索 最好：1次 最壞：4次 平均：（3+2+3+4+1+3+2+3+4）/92.77次n不成功檢索 最好：3次 最壞：4次 平均：(3+3+3+4+4+3+3+3+4+4)/10 = 3.4次二元比較樹(shù) 算法執(zhí)行過(guò)程的主體是x與一系列中間元素A(mid)比較?？捎靡豢枚獦?shù)描述這一過(guò)程，稱為二元比較樹(shù)n結(jié)點(diǎn)：分為內(nèi)結(jié)點(diǎn)

10、和外結(jié)點(diǎn)兩種內(nèi)結(jié)點(diǎn)：代表一次元素比較 用 圓形結(jié)點(diǎn)表示 存放一個(gè) mid值(下標(biāo)) 代表成功檢索情況外結(jié)點(diǎn)：用方形結(jié)點(diǎn)表示， 表示不成功檢索情況n路徑：代表檢索中元素的比較序列例2.1的二元比較樹(shù)二元比較樹(shù)的查找過(guò)程p 若x在A中出現(xiàn)，則算法的執(zhí)行過(guò) 程在一個(gè)圓形的內(nèi)結(jié)點(diǎn)處結(jié)束p 若x不在A中出現(xiàn)，則算法的執(zhí)行 過(guò)程在一個(gè)方形的外結(jié)點(diǎn)處結(jié)束 注：外結(jié)點(diǎn)不代表元素的比較，因 為比較過(guò)程在該外結(jié)點(diǎn)的上一 級(jí)的內(nèi)結(jié)點(diǎn)處結(jié)束。 例2.1的二元比較樹(shù)定理2.2 若n在區(qū)域2k-1,2k)中，則對(duì)于一次成功的檢索， BINSRCH至多做k次比較；對(duì)于一次不成功的檢索， 或者做k-1次比較，或者做k次比較。

11、證明要點(diǎn)： 二分檢索中，每次mid取中值，故其二元比較樹(shù)是一種“結(jié)點(diǎn)平衡”的樹(shù)， 當(dāng)2k-1n2k時(shí)，結(jié)點(diǎn)分布情況為： 內(nèi)結(jié)點(diǎn)：1至k級(jí) 外結(jié)點(diǎn)：k級(jí)或k+1級(jí)， 外部結(jié)點(diǎn)在相鄰的兩級(jí)上最深一層或倒數(shù)第2層比較過(guò)程： 成功檢索在內(nèi)結(jié)點(diǎn)處結(jié)束，不成功檢索在外結(jié)點(diǎn)處結(jié)束 成功檢索在i級(jí)的某個(gè)內(nèi)結(jié)點(diǎn)終止時(shí)，所需要的元素比較次數(shù)是i 不成功檢索在i級(jí)的外部結(jié)點(diǎn)終止所需的元素比較次數(shù)是i-1BINSRCH的計(jì)算復(fù)雜度 n2k-1,2k) klogn1）外結(jié)點(diǎn)在最末的兩級(jí)上，故不成功檢索的最好、 最壞和平均情況的計(jì)算時(shí)間均為 2）最好情況下，成功檢索的計(jì)算時(shí)間為 最壞情況下，成功檢索的計(jì)算時(shí)間為(logn

12、)(1)(logn)3）平均情況下的成功檢索的計(jì)算時(shí)間 利用外部結(jié)點(diǎn)和內(nèi)部結(jié)點(diǎn)到根距離和之間的關(guān)系進(jìn)行推導(dǎo)。 記， 由根到所有內(nèi)結(jié)點(diǎn)的距離之和稱為內(nèi)部路徑長(zhǎng)度，記為I； 由根到所有外部結(jié)點(diǎn)的距離之和稱為外部路徑長(zhǎng)度，記為E。 則有，E=I+2n 記， U(n)是平均情況下不成功檢索的計(jì)算時(shí)間，則 U(n) = E/(n+1) S(n)是平均情況下成功檢索的計(jì)算時(shí)間，則 S(n) = I/n + 1 由 得: S(n) = (1+1/n)U(n) -1 當(dāng)n,S(n) U(n) ，而U(n) = 所以 S(n) = (logn)(logn)成功檢索最好 平均 最壞(1)(logn)(logn)不

13、成功檢索最好 平均 最壞(logn)(logn)(logn)4. 以比較為基礎(chǔ)檢索的時(shí)間下界問(wèn)題：設(shè)n個(gè)元素的有序表A(1:n)，A(1) A(2) A(n)。檢索一 給定元素x是否在A中出現(xiàn)。 問(wèn)：是否預(yù)計(jì)還存在有以元素比較為基礎(chǔ)的另外的檢索算法，它 在最壞情況下比二分檢索算法在計(jì)算時(shí)間上有更低的數(shù)量級(jí)? 以比較為基礎(chǔ)的算法：假定算法中只允許進(jìn)行元素間的比較，而不 允許對(duì)它們實(shí)施其它運(yùn)算。 內(nèi)結(jié)點(diǎn)：表示一次元素的比較，并代表成功檢索情況。每棵比較樹(shù)中恰 好含有n個(gè)內(nèi)結(jié)點(diǎn)，分別與n個(gè)不同i值相對(duì)應(yīng)；外結(jié)點(diǎn)：代表不成功檢索情況。每棵比較樹(shù)中恰好有n+1個(gè)外結(jié)點(diǎn)分別 與n+1中不成功檢索情況相對(duì)應(yīng)

14、。分析：任何以比較為基礎(chǔ)的檢索算法，其執(zhí)行過(guò)程都可以用 二元比較樹(shù)來(lái)描述。以比較為基礎(chǔ)的有序檢索問(wèn)題最壞情況的時(shí)間下界定理2.3 設(shè)A(1:n)含有 n(n1)個(gè)不同的元素，且有 A(1) A(2) max then maxA(i) endif if A(i) max then maxA(i) endif else if A(i) min then minA(i) endif repeatend STRAITMAXMIN1這使得，最好情況：按遞增次序排列，元素比較次數(shù)為n-1次最壞情況：按遞減次序排列，元素比較次數(shù)為2(n-1)次平均情況：元素比較次數(shù)為3(n-1)/2次2. 分治求解策略 記

15、問(wèn)題的一個(gè)實(shí)例為： I = (n, A(1), , A(n) 采用二（等）分法將I分成兩個(gè)子集合處理 I1 = ( , A(1), ，A( )，和 I2 = (n- , A( +1), ， A(n) 則有， MAX(I) = max(MAX(I1),MAX(I2) MIN(I) = min(MIN(I1),MIN(I2) MAX(I)和MIN(I)分別代表I中元素的最大者和最小者 采用遞歸的設(shè)計(jì)策略，得到以下算法：n/2n/2n/2n/23. 找最大最小元素的遞歸求解算法算法2.6 遞歸求取最大和最小元素procedure MAXMIN(i,j,fmax,fmin) /A(1:n)是含有n個(gè)元

16、素的全局?jǐn)?shù)組，參數(shù)i,j是整數(shù)，1i,jn，代表當(dāng)前的查找區(qū)間 / /該過(guò)程把A(i:j)中的最大和最小元素分別賦給fmax和fmin / integer i,j;global n,A(1:n) case :i=j: fmaxfminA(i) /只有一個(gè)元素 :i=j-1:if A(i)2當(dāng)n是2的冪時(shí)(n=2k),化簡(jiǎn)上式有， T(n)=2T(n/2) +2 =2(2T(n/4) + 2) + 2 =2k-1T(2) + =2k-1+2k-2 =3n/2-22)n/2T()n/2T(1ki1i2性能比較1）與STRAITMAXMIN算法相比，比較次數(shù)減少了25% （3n/2-2 : 2n-2

17、)。 已經(jīng)達(dá)到了以元素比較為基礎(chǔ)的找最大最小元素的算法 計(jì)算時(shí)間的下界：2）存在的問(wèn)題遞歸調(diào)用造成： 空間占用量大 有 級(jí)的遞歸，入棧參數(shù)： i, j, fmax, fmin和返回地址五個(gè)值。 時(shí)間可能不比預(yù)計(jì)的理想 如果元素A(i)和A(j)的比較與i和j的比較在時(shí)間上相差不大時(shí)，算法MAXMIN不可取。22/3n1logn 假設(shè)元素的比較與i和j的比較時(shí)間相同（整型數(shù)）。又設(shè)對(duì)case語(yǔ)句調(diào)整，使得僅需一次i和j的比較就能夠確定是哪種情況。 case :i=j-1:if A(i)A(j) then fmaxA(j);fminA(i) else fmaxA(i);fminA(j) /兩個(gè)元素

18、的情況 endif :else: 記此時(shí)MAXMIN的頻率計(jì)數(shù)為C(n)，n=2k (k為正整數(shù)）。則有， 2 n2 化簡(jiǎn)得， C(n) = 2C(n/2) + 3 = = 5n/2 -3按照同樣的假設(shè)，重新估算STRAITMAXMIN算法的比較次數(shù)為：3(n-1)。 STRAITMAXMIN與MAXMIN在計(jì)算時(shí)間上的差異越來(lái)越小 1/4 （25%）=1/6（16.7%）考慮MAXMIN算法遞歸調(diào)用的開(kāi)銷，此時(shí)MAXMIN算法 的效率可能還不如STRAITMAXMI算法。結(jié)論：如果A中的元素間的比較代價(jià)遠(yuǎn)比整型數(shù) （下標(biāo)）的比較昂貴，則分治方法將產(chǎn)生 一個(gè)效率較高的算法； 反之，可能僅得到一

19、個(gè)低效的算法。故，分治策略只能看成一個(gè)較好的但并不總是成功 的算法設(shè)計(jì)指導(dǎo)。2.4 歸并分類1. 分類問(wèn)題排序 給定一n個(gè)元素的集合A，按照某種方法將A中的元素按非降或非增次序排列。 分類：內(nèi)排序，外排序 常見(jiàn)內(nèi)排序方法：冒泡排序 插入排序 歸并排序 快速排序 堆排序 2. 插入分類 算法2.7 插入分類 procedure INSERTIONSORT(A,n) /將A(1：n)中的元素按非降次序分類，n1/ A(0)-/設(shè)置初始邊界值 for j2 to n do /A(1:j-1)已分類/ itemA(j);ij-1 while itemA(i) do /0ij/ A(i+1)A(i);

20、ii-1 repeat A(i+1) item; repeat end INSERTIONSORT i指示的是j之前的一位，即當(dāng)前已排序子表的最末一個(gè)元素的下標(biāo) 性能分析： 最壞情況：輸入數(shù)據(jù)按非增次序排列,每次內(nèi)層while循環(huán)執(zhí)行j次（j=2,3, n)。則有， 最好情況：輸入數(shù)據(jù)已按非降序排列，不進(jìn)入while循環(huán)，則最好情況下計(jì)算時(shí)間為(n)(n21 1)/2(n(njnj23.分治策略求解 基本設(shè)計(jì)思想：將原始數(shù)組A中的元素分成兩個(gè)子集合：A1(1: )和A2( +1 :n)。分別對(duì)這兩個(gè)子集合單獨(dú)分類，然后將已分類的兩個(gè)子序列歸并成一個(gè)含有n個(gè)元素的分類好的序列。 這樣的一個(gè)分類過(guò)

21、程稱為歸并分類。 n/2n/2算法2.8 歸并分類 procedure MERGESORT(low,high) /A(low:high)是一個(gè)全程數(shù)組，low和high分別指示當(dāng)前待分類區(qū)間的最小下標(biāo)和最大下標(biāo)，含有high-low+10個(gè)待分類的元素/ integer low,high if lowmid then for kj to high do B(i) A(k);ii+1; repeat else for kh to mid do B(i) A(k);ii+1; repeat endif for k low to high do A(k) B(k) repeat /將已歸并的集合復(fù)制

22、到A中/ end MERGE性能分析1) 過(guò)程MERGE的歸并時(shí)間與兩數(shù)組元素的總數(shù)成正比 故可表示為: cn, n為元素?cái)?shù),c為某正常數(shù)2) 過(guò)程MERGESORT的分類時(shí)間用遞推關(guān)系式表示如下: a n=1,a是常數(shù) T(n)= 2T(n/2)+cn n1, c是常數(shù)化簡(jiǎn): 若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/ 若2kn2k+1,則有T(n)T(2k+1)。所以得：T(n) = (nlogn) 遞歸調(diào)用一直進(jìn)行

23、到子區(qū)間僅含一個(gè)元素時(shí)為止歸并分類示例n設(shè)A=（310，285，179，652，351，423，861，254，450，520）n1）劃分過(guò)程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，8612544238614505202）歸并過(guò)程首先進(jìn)入左分枝的劃分與歸并。 第一次歸并前的劃分狀態(tài)是： （310 | 285 | 179 | 652，351 | 423，861，

24、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)入右分枝的劃分與歸并過(guò)程（略）3）用樹(shù)結(jié)構(gòu)描述歸并分類過(guò)程4. 歸并分類算法的改進(jìn)1）算法2.8存在的問(wèn)題l 遞歸層次太深 在MERGESORT的執(zhí)行過(guò)程中，當(dāng)集合僅含

25、有兩個(gè)元素時(shí)，仍要進(jìn)一步做遞歸調(diào)用，直至每個(gè)集合僅含有一個(gè)元素時(shí)才退出遞歸調(diào)用。 在集合含有僅相當(dāng)少的元素時(shí)，較深層次的遞歸調(diào)用使得時(shí)間過(guò)多地消耗在處理遞歸上。l 元素在數(shù)組A和輔助數(shù)組B之間的頻繁移動(dòng) 每次歸并，都要首先將A中的元素移到B中，在由B復(fù)制到A的對(duì)應(yīng)位置上。n2）改進(jìn)措施l 針對(duì)遞歸層次問(wèn)題 采用能在小規(guī)模集合上有效工作的其它算法，直接對(duì)小規(guī)模集合處理。 如INSERTIONSORT算法l 針對(duì)元素頻繁移動(dòng)問(wèn)題 采用一個(gè)稱為鏈接信息數(shù)組LINK（1：n）的數(shù)據(jù)結(jié)構(gòu)，記錄歸并過(guò)程中A中的元素相對(duì)于其排序后在分類表中位置坐標(biāo)的鏈接關(guān)系。 LINK(i)取值于1，n，是指向A的元素的指

26、針：在分類表中它指向下一個(gè)元素在A中的位置坐標(biāo)。例： LINK (1) (2) (3) (4) (5) (6) (7) (8) 6 4 7 1 3 0 8 0該表中含有兩個(gè)子表，0表示表的結(jié)束。設(shè)置表頭指針Q和R分別指向兩個(gè)子表的起始處： Q=2，R=5； 則有， 表1：Q(2，4，1，6)，經(jīng)過(guò)分類后有：A(2)A(4) A(1) A(6) 表2：R(5，3，7，8)，同樣有： A(5)A(3) A(7) A(8)n 鏈接信息表在歸并過(guò)程中的應(yīng)用： 將歸并過(guò)程中元素在A和B之間移動(dòng)的過(guò)程變成更改LINK所指示的鏈接關(guān)系，從而避免移動(dòng)元素的本身。 分類表可以通過(guò)LINK的表頭指針和讀取LINK

27、中的鏈接關(guān)系取得。改進(jìn)后的歸并分類模型算法2.10 使用鏈接信息數(shù)組的歸并分類模型procedure MERGESORT1(low,high,p) /利用鏈接信息數(shù)組LINK(1:n)將全程數(shù)組A(low:high)按非降次序分類。LINK中值表示按分類次序給出A下標(biāo)的表，并把p置于該表的開(kāi)始處/global A(low:high),LINK(low,high)if high-low+116 /當(dāng)集合中的元素個(gè)數(shù)足夠少(16)時(shí)，采用更有效的小規(guī)模集合上的分類 算法直接分類/ then call INSERTSORT1(A,LINK,low,high,p) /算法2.7的改型/ else mi

28、d call MERGESORT1(low,mid,q) /返回q表/ call MERGESORT1(mid+1,high,r) /返回r表/ call MERGE1(q,r,p) /將表q和表r歸并成表p/endifend MERGESORT1high)/2(low算法2.11 使用鏈接表歸并已分類的集合 procedure MERGE1(q,r,p) /q和r是全程數(shù)組LINK(1:n)中兩個(gè)表的指針。歸并這兩個(gè)表，得到一個(gè)由p所指示的新表。此表將 A中的元素按非降次序分類。LINK(0)被定義/ global n,A(1:n),LINK(1:n) local integer i,j,k

29、 iq;jr;k0 /新表在LINK(0)處開(kāi)始/ while i0 and j0 do /當(dāng)兩表均非空時(shí)/ if A(i) A(j) /找較小的關(guān)鍵字/ then LINK(k) i;ki;iLINK(i) /加一個(gè)新關(guān)鍵字到表中/ else LINK(k) j;kj;jLINK(j) /加一個(gè)新關(guān)鍵字到表中/ endif repeat if i=9 then LINK(k) = j else LINK(k) = i endif end MERGE1MERGESORT1 的調(diào)用 在初次調(diào)用時(shí)，待分類的n個(gè)元素放于A(1:n)中。 LINK(1:n)初始化為0； 初次調(diào)用：call MERGE

30、SORT1(1,n,p) p作為按分類次序給出A中元素的指示表的指針。3）改進(jìn)歸并分類算法示例 設(shè)元素表：（50，10，25，30，15，70，35，55） 采用MERGESORT1對(duì)上述元素表分類（不做小規(guī)模集合的單獨(dú)處理） 下表給出在每一次調(diào)用MERGESORT1結(jié)束后，LINK數(shù)組的變化情況。在上表的最后一行，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)5. 以比較為基礎(chǔ)分類的時(shí)間下界1.分類的“實(shí)質(zhì)” 給定n個(gè)記錄R1,R2,Rn,其相應(yīng)的關(guān)鍵字是k1,k2,kn。 分類就是確定1,2,n的一種排

31、列P1,P2,Pn,使得記錄的關(guān)鍵字滿足以下非遞減（或非遞增）排列關(guān)系 kP1kP2kPn 從而使n個(gè)記錄成為一個(gè)按關(guān)鍵字有序的序列： RP1,RP2,RPn 2. 以關(guān)鍵字比較為基礎(chǔ)的分類算法的時(shí)間下界 最壞情況下的時(shí)間下界為：(nlogn) 利用二元比較樹(shù)證明。 假設(shè)參加分類的n個(gè)關(guān)鍵字A(1),A(2),A(n)互異。任意兩個(gè)關(guān)鍵字的比較必導(dǎo)致A(i)A(j)的結(jié)果。 以二元比較樹(shù)描述元素間的比較過(guò)程： 若A(i)A(j)，進(jìn)入下一級(jí)的右分支 算法在外部結(jié)點(diǎn)終止。 從根到某外結(jié)點(diǎn)的路徑代表某個(gè)特定輸入情況下一種唯一的分類排序序列。路徑長(zhǎng)度表示生成該序列代表的分類表所需要的比較次數(shù)。而最長(zhǎng)

32、的路徑代表算法在最壞情況下的執(zhí)行情況，該路徑的長(zhǎng)度即是算法在最壞情況下所作的比較次數(shù)。 故，以比較為基礎(chǔ)的分類算法的最壞情況下界等于該算法對(duì)應(yīng)的比較樹(shù)的最小高度。初始集合中的元素因順序不同，將導(dǎo)致排序過(guò)程走不同的分支 由于n個(gè)關(guān)鍵字有n!種可能的排列，所以分類二元比較樹(shù)中將有 n!個(gè)外部結(jié)點(diǎn)：每個(gè)外部結(jié)點(diǎn)代表一種特定的排列，該排列對(duì)應(yīng)于某種特定輸入情況下的分類序列。 設(shè)一棵二元比較樹(shù)的所有內(nèi)結(jié)點(diǎn)的級(jí)數(shù)均小于或等于k，則該樹(shù)中最多有2k個(gè)外結(jié)點(diǎn)。 記算法在最壞情況下所作的比較次數(shù)為T(n)，則有T(n)=k：生成外結(jié)點(diǎn)所代表的分類序列所需的比較次數(shù)等于該外結(jié)點(diǎn)所在的級(jí)數(shù)-1； 根據(jù)和的分析，有：

33、 n!2T(n) 化簡(jiǎn)： 當(dāng)n1時(shí)，有n!n(n-1)(n-2)( )(n/2)n/2 當(dāng)n4時(shí)，有 T(n)(n/2)log(n/2)(n/4)logn 故，任何以比較為基礎(chǔ)的分類算法的最壞情況的時(shí)間下界為： (nlogn) n/21.劃分與快速分類 快速分類是一種基于劃分的分類方法； 劃分：選取待分類集合A中的某個(gè)元素t，按照與t的大小關(guān)系重 新整理A中元素，使得整理后t被置于序列的某位置上， 而序列中所有在t以前出現(xiàn)的元素均小于等于t，而所有出 現(xiàn)在t以后的元素均大于等于t。這一元素的整理過(guò)程稱為 劃分（Partitioning）。 元素t稱為劃分元素。 快速分類：通過(guò)反復(fù)地對(duì)待排序集合

34、進(jìn)行劃分達(dá)到分類目的的分 類算法。2.5 快速分類劃分過(guò)程（PARTITION）的算法描述算法2.2 用A(m)劃分集合A(m:p-1) procedure PARTITION(m,p) integer m,p,i; global A(m:p-1) vA(m);im /A(m)是劃分元素/ loop loop ii+1 until A(i)v repeat / i由左向右移/ loop pp-1 until A(p)v repeat /p由右向左移/ if ip then call INTERCHANGE(A(i),A(p) else exit endif repeat A(m)A(p)； A

35、(p)v /劃分元素在位置p/end PARTITION A(p)被定義，但為一限界值，不包含在實(shí)際的分類區(qū)間內(nèi)。pivv注： 算法對(duì)集合A(m:p-1)進(jìn)行劃分。并使用待劃分區(qū)間的第一 個(gè)元素A(m)作為劃分元素 A(p)不在劃分區(qū)間內(nèi)，但被定義，且A(p）A(m)，用于 限界例2.5 劃分實(shí)例 (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) i p A: 65 70 75 80 85 60 55 50 45 + 2 9 | A: 65 45 75 80 85 60 55 50 70 + 3 8 | A: 65 45 50 80 85 60 55 75 70

36、 + 4 7 | A: 65 45 50 55 85 60 80 75 70 + 5 6 | A: 65 45 50 55 60 85 80 75 70 + 6 5 | A: 60 45 50 55 65 85 80 75 70 +劃分元素定位于此交換劃分元素經(jīng)過(guò)一次“劃分”后，實(shí)現(xiàn)了對(duì)集合元素的調(diào)整： 以劃分元素為界，左邊子集合的所有元素均小于等于右邊子集合的所有元素。 按同樣的策略對(duì)兩個(gè)子集合進(jìn)行分類處理。當(dāng)子集合分類完畢后，整個(gè)集合的分類也完成了。這一過(guò)程避免了子集合的歸并操作。這一分類方法稱為快速分類。2.快速分類算法 一種通過(guò)反復(fù)使用劃分過(guò)程PARTITION實(shí)現(xiàn)對(duì)集合元素分類的算法

37、。算法2.13 快速分類 procedure QUICKSORT(p,q) /將數(shù)組A(1:n)中的元素A(p),A(q)按遞增的方式分類。 A(n+1)有定義，且假定A(n+1)+/ integer p,q;global n,A(1:n) if pq then jq+1 /進(jìn)入時(shí)，A(j)定義了劃分區(qū)間p,q的上界，首次調(diào)用時(shí)j=n+1 call PARTITION(p,j) /出口時(shí)，j帶出此次劃分后劃分元素所在的下標(biāo)位置/ call QUICKSORT(p,j-1) /對(duì)前一子集合遞歸調(diào)用 call QUICKSORT(j+1,q) /對(duì)后一子集合遞歸調(diào)用 endif end QUICK

38、SORT 3. 快速分類分析n統(tǒng)計(jì)的對(duì)象：元素的比較次數(shù)，記為：C(n)n兩點(diǎn)假設(shè) 參加分類的n個(gè)元素各不相同 PARTITION中的劃分元素v是隨機(jī)選取的（針對(duì)平均情況的分析）隨機(jī)選取劃分元素： 在劃分區(qū)間m,p-1隨機(jī)生成某一坐標(biāo)：iRANDOM(m.p-1)； 調(diào)換A(m)與A(i):vA(i);A(i) A(m);im 作用：將隨機(jī)指定的劃分元素的值調(diào)換到A(m)位置。算法主體 不變。之后，仍從A(m)開(kāi)始執(zhí)行劃分操作。遞歸層次QuickSort(1,n)QuickSort(1,j1-1)QuickSort(j1-1,n)QuickSort(1,j21-1)QuickSort(j21+

39、1, j1-1)QuickSort(j1-1,j22-1)QuickSort(j22+1,n)n個(gè)元素參加劃分和分類去掉1個(gè)第一級(jí)的劃分元素n-1個(gè)元素參加劃分和分類去掉2個(gè)第二級(jí)的劃分元素n-3個(gè)元素參加劃分和分類去掉4個(gè)第三級(jí)的劃分元素第一層第二層第三層 設(shè)在任一級(jí)遞歸調(diào)用上，調(diào)用PARTITION處理的所有元素總數(shù)為r，則，初始時(shí)r=n，以后的每級(jí)遞歸上，由于刪去了上一級(jí)的劃分元素，故r比上一級(jí)至少1：理想情況，第一級(jí)少1，第二級(jí)少2，第三級(jí)少4， ；最壞情況，每次僅減少1（每次選取的劃分元素剛好是當(dāng)前集合中最小或最大者）n 最壞情況分析 記最壞情況下的元素比較次數(shù)是Cw(n)； PAR

40、TITION一次調(diào)用中的元素比較數(shù)是p-m+1，故每級(jí)遞歸調(diào)用上， PARTITION所做的比較總數(shù)為O(r), r是任一級(jí)遞歸調(diào)用上PARTITION所處理的元素總數(shù)。 最壞情況下（元素已有序），每級(jí)遞歸調(diào)用的元素總數(shù)僅比上一級(jí)少1，故Cw(n)是r由n到2的累加和。 即：Cw(n)= = (n2)nrr1n 平均情況分析 平均情況是指集合中的元素以任意順序排列，且任選元素作為劃分元素進(jìn)行劃分和分類，在這些所有可能的情況下，算法執(zhí)行性能的平均值。 設(shè)調(diào)用PARTITION(m,p)時(shí)，所選取劃分元素v恰好是A(m:p-1)中的第i小元素（1ip-m）的概率相等。則經(jīng)過(guò)一次劃分，所留下的待分類

41、的兩個(gè)子文件恰好是A(m:j-1)和A(j+1:p-1)的概率是：1/(p-m), mjp。 記平均情況下的元素比較次數(shù)是CA(n)；則有， 其中， n+1是PARTITION第一次調(diào)用時(shí)所需的元素比較次數(shù)。 CA(0) = CA(1) = 0 nkAAnAknCkCnnC11)() 1(1)(化簡(jiǎn)上式可得： CA(n)/(n+1)= CA(n-1)/n + 2/(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) = (nlo

42、gn)13/12nkk) 1(log/11213nkenxdxnkn空間分析 最壞情況下，遞歸的最大深度為n-1. 需要?？臻g：O(n) 使用一個(gè)迭代模型可以將?？臻g總量減至O(logn)4. 快速分類算法的迭代模型 處理策略：每次在Partition將文件A(p:q)分成兩個(gè)文件 A(p:j-1)和A(j+1,q)后，先對(duì)其中較小的子文件 進(jìn)行分類。當(dāng)小的子文件分類完成后，再對(duì)較 大的子文件進(jìn)行分類。 棧：需要一個(gè)?？臻g保存目前暫不分類的較大子文件。并 在較小子文件分類完成后，從棧中退出最新的較大子 文件進(jìn)行下一步分類。 棧空間需要量：O(logn) 算法的終止：當(dāng)?？諘r(shí)，整個(gè)分類過(guò)程結(jié)束。

43、算法2.14 QuickSort2(p,q) integer STACK(1:max),top /max=2 global A(1:n);local integer j top0 loop while pq do jq+1 call PARTITION(p,j); if j p q j /先對(duì)較小的子文件分類，并將規(guī)模較大的子文件入棧 then STACK(top+1)j+1; STACK(top+2)q; qj-1 else STACK(top+1)p; STACK(top+2)j-1; pj+1 endif toptop+2 /調(diào)整棧頂指針 repeat if top=0 then ret

44、urn endif /如果棧為空，算法結(jié)束 qSTACK(top);pSTACK(top-1); toptop-2 /從棧中退出先前保存的 較大的子文件 repeat end QUICKSORT2nlog 快速分類算法迭代模型的空間分析算法2.14的最大空間是O(logn)推導(dǎo)： 設(shè)算法所需的最大?？臻g是S(n)，則有 1n 01n )2/ ) 1(2)(nSnS2.6 選擇問(wèn)題1. 問(wèn)題描述 在n個(gè)元素的表A(1:n)中確定第k小元素，1kn。2. 設(shè)計(jì)思路 利用PARTITION過(guò)程。在第一次劃分后劃分元素v測(cè)定在A(j)的位置上，則有j-1個(gè)元素小于或等于A(j)，且有n-j個(gè)元素大于或

45、等于A(j)。此時(shí)， 若k=j，則A(j)即是第k小元素；否則， 若kj，則A(1:n)中的第k小元素將出現(xiàn)在A(j+1:n)中， 但是A(j+1:n)中的第k-j小元素。3. 利用PARTITION實(shí)現(xiàn)的選擇算法n算法描述 算法2.15 找第k小元素 procedure SELECT(A,n,k) /在數(shù)組A(1:n)中找第k小元素，并將之放在A(k)中。/ integer n,k,m,r,j; m1;r n+1;A(n+1) + /A(n+1)被定義，并置為一大值，用于限界/ loop /在進(jìn)入循環(huán)時(shí)，1mkrn+1 / j r /將剩余元素的最大下標(biāo)加1后置給j / call PARTI

46、TION(m.j) /返回j,它使得A(j)是第j小的值/ case :k=j: return :kj, j+1是新的下界/ endcase repeat end SELECTn 算法分析 兩點(diǎn)假設(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小 的子集的元素?cái)?shù)將至少比上一次劃分的元素?cái)?shù)少1。1) 最壞情況 SELECT的最壞情況時(shí)間是(n2)最壞情況下的特

47、例： 輸入A恰好使對(duì)PARTITION的第i次調(diào)用選用的劃分元素是第i小元素，而k=n。 此時(shí)，（區(qū)間下界）m隨著PARTITION的每一次調(diào)用而僅增加1，j保持不變。 PARTITION最終需要調(diào)用n次。 則,n次調(diào)用的時(shí)間總量是)() ) 1(21nin2)平均情況 設(shè) 是找A(1:n)中第k小元素的平均時(shí)間。 是SELECT的平均計(jì)算時(shí)間，則有并定義則有：T(n)R(n)。nkkAnAnTnT11)()()(nTA)(max)(nTnRkAk)(nTkA對(duì)n個(gè)不同的元素，問(wèn)題實(shí)例可能的n!種不同情況，綜合考查所得的平均值在所有可能的情況下，找所有可能的k小元素某個(gè)特定的k定理2.4 SE

48、LECT的平均計(jì)算時(shí)間TA(n)是(n)證明： PARTITION的一次執(zhí)行時(shí)間是(n)。在隨機(jī)等概率選擇劃分元素時(shí)，首次調(diào)用PARTITION中劃分元素v剛好是A中第i小元素的概率為1/n，1in。 則，存在正常數(shù)c，c0,有， n2 且有， n2 1)(iTi)(nT(cn(n)TnikkAki1ikAn1kA1)(iRi)(nRmaxcnR(n)nikki1kn1(i)R(i)Rmaxcn1nk1n1knkn1劃分元素ik,將在i的前半部分求解 令令cR(1)R(1)。利用。利用數(shù)學(xué)歸納法數(shù)學(xué)歸納法證明，對(duì)所有證明，對(duì)所有n2n2，有，有R(n)4cn.R(n)4cn. 當(dāng)n=2時(shí)，由上

49、式得： 假設(shè)對(duì)所有的n, 2nm，有R(n)4cn 當(dāng)n = m時(shí)，有， 由于R(n)是n的非降函數(shù)，故當(dāng)m為偶數(shù)而k=m/2，或當(dāng)m為奇數(shù)而k=(m+1)/2時(shí)， 取得極大值。因此， 若m為偶數(shù)，則 若m為奇數(shù)，則 由于TA(n)R(n)，所以TA(n)4cn。 故，TA(n)=(n)R(1)maxR(1),212cR(n)4cn2.5c(i)R(i)Rmaxcm)(1mk1m1kmkm1nR1mm/2m2R(i)cmR(m)1mm/2m8c4cmicm1m1)/2(mm2R(i)cmR(m)1m1)/2(mm8c4cmicm(i)R(i)R1nk1n1kn1km-11m k+1m-14.

50、最壞情況是(n)的選擇算法1）采用兩次取中間值的規(guī)則精心選取劃分元素 首先，將參加劃分的n個(gè)元素分成 組，每組有r個(gè)元素(r1)。（多余的 個(gè)元素忽略不計(jì)） 然后，對(duì)這 組每組的r個(gè)元素進(jìn)行分類并找出其中間元素mi,1i ，共得 個(gè)中間值。 之后，對(duì)這 個(gè)中間值分類，并找出其中間值mm。將mm作為劃分元素執(zhí)行劃分。2）算法描述n/rn/rrnn/rn/rn/rn/rn例：設(shè) n=35, r=7。 分為n/r = 5個(gè)元素組： B1，B2，B3，B4，B5； 每組有7個(gè)元素。 B1-B5按照各組的mi的非增次 序排列。 mm = mi的中間值，1i5由圖所示有：mm中間值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B5按照mi的非降次序排列 由于r個(gè)元素的中間值是第 小元素。則， 至少有 個(gè)mi小于或等于mm； 至少有 個(gè)mi大于或等于mm。 故，至少有 個(gè)元素小于或等于（或大于或等于）