計(jì)算機(jī)算法設(shè)計(jì)與分析：4第四章分治法

1、第四章分治法24.1 一般方法4.2 二分檢索4.3 找最大和最小元素(略)4.4 歸并分類(lèi)4.5 快速分類(lèi)(略)4.6 選擇問(wèn)題(略)4.7 斯特拉森矩陣乘法主要內(nèi)容34.1 一般方法分治法適用的問(wèn)題分治法的求解思想分治策略DANDC的抽象化控制分治策略DANDC的計(jì)算時(shí)間4問(wèn)題(n個(gè)輸入)n取值相當(dāng)大，直接求解往往非常困難，甚至無(wú)法求出。子問(wèn)題1子問(wèn)題2子問(wèn)題k解1解2解k整個(gè)問(wèn)題的解將n個(gè)輸入分解成k個(gè)不同子集，得到k個(gè)不同的可獨(dú)立求解的子問(wèn)題。在求出子問(wèn)題的解之后，能找到適當(dāng)?shù)姆椒ò阉鼈兒喜⒊烧麄€(gè)問(wèn)題的解。分治法適用的問(wèn)題5分治法的求解思想思想：將整個(gè)問(wèn)題分成若干個(gè)小問(wèn)題后分而治之。通

2、常，由分治法所得到的子問(wèn)題與原問(wèn)題具有相同的類(lèi)型?？梢苑磸?fù)使用分治策略，直到可以直接求解子問(wèn)題為止。適合采用遞歸過(guò)程來(lái)表示。分（divide）治（conquer）合（combine）6子問(wèn)題的個(gè)數(shù)K顯然有K1, K越大越好么?蚯蚓的故事蚯蚓一家這天很無(wú)聊，小蚯蚓想了想，把自己切成兩段，打羽毛球去了。蚯蚓媽媽覺(jué)得這方法法不錯(cuò)，就把自己切成四段，打麻將去了。沒(méi)過(guò)一會(huì)，蚯蚓爸爸就把自己切成了肉末。蚯蚓媽媽哭著說(shuō)：你怎么那么傻，切得那么碎會(huì)死的。蚯蚓爸爸弱弱地說(shuō)：突然想踢足球 7分治策略DANDC的抽象化控制procedure DANDC(p,q)global n, A(1 n); integer m

3、, p, q; /1pqn/if SMALL(p,q) then return(G(p,q) else mDIVIDE(p,q) return(COMBINE (DANDC(p,m), DANDC(m1,q)endifend DANDC判斷輸入規(guī)模qp1是否足夠小,可直接求解G是直接求解該規(guī)模問(wèn)題的函數(shù)分割函數(shù), pmq, 原問(wèn)題被分為A(p m)和A(m1 q)兩個(gè)子問(wèn)題合并函數(shù),將兩個(gè)子問(wèn)題的解合并為原問(wèn)題的解原問(wèn)題為A(1n) , 最初調(diào)用函數(shù)應(yīng)該是DANDC(1, n).8分治策略DANDC的計(jì)算時(shí)間 假設(shè)所分成的兩個(gè)子問(wèn)題的輸入規(guī)模大致相等，則分治策略DANDC的計(jì)算時(shí)間可表示為：

4、T(n)是輸入規(guī)模為n的分治策略的計(jì)算時(shí)間g(n)是對(duì)足夠小的輸入規(guī)模能直接計(jì)算出答案的時(shí)間f(n)是COMBINE函數(shù)合成原問(wèn)題解的計(jì)算時(shí)間g(n)n足夠小2T(n/2)f(n)否則T(n)=94.2 二分檢索二分檢索問(wèn)題描述二分檢索求解原理二分檢索算法二分檢索實(shí)例二分檢索算法正確性證明二分檢索算法所需的空間和時(shí)間二元比較樹(shù)算法BINSRCH的計(jì)算時(shí)間以比較為基礎(chǔ)檢索的時(shí)間下界10二分檢索問(wèn)題描述已知一個(gè)按非降序排列的元素表a1, a2, , an，判定某個(gè)給定元素x是否在該表中出現(xiàn)，若是，則找出該元素在表中的位置，并將此下標(biāo)賦給變量j，否則，將j置成0。11二分檢索求解原理將檢索問(wèn)題表示為

5、：I(n, a1, , an, x)， 選取一個(gè)下標(biāo)k，可得到三個(gè)子問(wèn)題：I1 (k1, a1, , ak1, x)I2 (1, ak, x)I3 (nk, ak1, , an, x)二分檢索通常對(duì)所求解的問(wèn)題（或子問(wèn)題）選擇中間元素的下標(biāo)，k (n1)/212procedure BINSRCH(A, n, x, j) integer low, high, mid, j, n; low1; highn while lowhigh do mid (lowhigh)/2 /*取中間值*/ case :xA(mid): highmid1 /*在前一半尋找*/ :xA(mid): lowmid1 /*

6、在后一半尋找*/ : else: jmid; return; /*檢索成功, 結(jié)束*/ endcase repeat j0 /*檢索失敗*/end BINSRCH二分檢索算法13檢索x9, 9A(5), 一次比較, 成功, 最好情況156079235482101A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) A(9)檢索x15, 15A(5), 15A(2), 15A(1), 3次比較, 成功檢索x101, 101A(9), 4次比較, 成功檢索x8, 8A(5), 8A(2), 8A(3), 8A(4), 4次比較, 不成功檢索二分檢索實(shí)例設(shè)在A(1:9)中順

7、序放了以下9個(gè)元素：14二分檢索算法正確性證明程序的正確性證明至今還是一個(gè)尚未解決的課題。這里僅給出BINSRCH的非形式證明。如果n0，則不進(jìn)入循環(huán)，j0，算法終止。否則就會(huì)進(jìn)入循環(huán)與數(shù)組A中的元素進(jìn)行比較。成功情況：若xAmid，則jmid，檢索成功，算法終止。不成功情況：按下述方式縮小檢索區(qū)總可以在有限步內(nèi)使lowhigh，說(shuō)明x不在A中，j0，算法終止。若xA(mid)，則縮小到A(low)和A(mid1)之間檢索。若xA(mid)，則縮小到A(mid1)和A(n)之間檢索。15二分檢索算法所需的空間和時(shí)間所需空間: 用n個(gè)位置存放數(shù)組A，還有l(wèi)ow, high, mid, x, j五

8、個(gè)變量需要存儲(chǔ)，共需空間 n5。所需時(shí)間： 需要分別考慮以下幾種情況：成功檢索的最好情況、平均情況、最壞情況不成功檢索的最好情況、平均情況、最壞情況16-15-6079235482101A1 A2 A3 A4 A5 A6 A7 A8 A93334433344成功比較次數(shù)：失敗比較次數(shù)：成功檢索有n種情況，不成 功檢索有n1種情況。集中考慮x和A中元素比較?？梢杂靡豢枚容^樹(shù)來(lái)描 述算法的執(zhí)行過(guò)程。122333344最好最壞平均成功1425/9失敗3434/1017二元比較樹(shù)內(nèi)結(jié)點(diǎn)表示一次元素的比較,存放一個(gè)mid值外結(jié)點(diǎn)表示不成功檢索的一種情況592-61-15307544762388291

9、01一條路徑表示一個(gè)元素的比較序列算法執(zhí)行過(guò)程實(shí)質(zhì)上就是x與一系列中間元素A(mid)的比較過(guò)程。18算法BINSRCH的計(jì)算時(shí)間定理4.2：若n在區(qū)域2k1, 2k)中，則對(duì)于一次成功的檢索，二分檢索算法至多作k次比較，而對(duì)于一次不成功的檢索，或者作k1次比較或者作k次比較。證明：P75(logn)(logn)(logn)(logn)(logn)(1)不成功的檢索成功的檢索最壞情況平均情況最好情況計(jì)算時(shí)間19求成功檢索的平均比較數(shù)內(nèi)部路徑長(zhǎng)度I：由根到所有內(nèi)部節(jié)點(diǎn)的距離之和；外部路徑長(zhǎng)度E：由根到所有外部節(jié)點(diǎn)的距離之和；容易證明EI2n；S(n)是成功比較的平均比較次數(shù)，S(n)In1;U(

10、n)是不成功比較的平均比較次數(shù)，U(n)E(n1);S(n)(11/n)U(n)1(U(n)(logn)思路：利用外部節(jié)點(diǎn)與內(nèi)部節(jié)點(diǎn)到根的距離和之間的一種簡(jiǎn)單關(guān)系，由不成功檢索的平均數(shù)求出成功檢索的平均比較數(shù)。20算法BINSRCH的變型將BINSRCH的case語(yǔ)句用if語(yǔ)句來(lái)替換。procedure BINSRCH(A, n, x, j) integer low, high, mid, j, n; low1; highn while lowhigh do mid(lowhigh)2 case :xA(mid): highmid1 :xA(mid): lowmid1 : else: jmid

11、; return; endcase repeat j0 end BINSRCHif xA(mid) then highmid-1 else if xA(mid) then lowmid1 else jmid; return; endifendif 最壞情況下，x總是比較兩次。21將BINSRCH的case語(yǔ)句用if語(yǔ)句來(lái)替換。procedure BINSRCH1(A, n, x, j) integer low, high, mid, j, n; low1; highn1 /high總比可能的取值大1 while lowhigh1 do mid(lowhigh)2 if xA(mid) /在循環(huán)

12、中只比較一次 then highmid else lowmid /xA(mid) endif repeat if xA(low) then jlow /x出現(xiàn) else j0 /x不出現(xiàn) end BINSRCH1最好、最壞和平均情況時(shí)間對(duì)于成功和不成功的檢索都是(logn) 。算法BINSRCH的變型procedure BINSRCH(A, n, x, j) integer low, high, mid, j, n; low1; highn while lowhigh do mid(lowhigh)2 case :xA(mid): highmid1 :xA(mid): lowmid1 : el

13、se: jmid; return; endcase repeat j0 end BINSRCH22以比較為基礎(chǔ)檢索的時(shí)間下界思考：對(duì)于已排序的n個(gè)元素，檢索某元素x是否出現(xiàn)時(shí)，是否存在以比較為基礎(chǔ)的檢索算法，在最壞情況下該算法的計(jì)算時(shí)間比二分檢索算法的計(jì)算時(shí)間更低。對(duì)于以比較為基礎(chǔ)的檢索算法的分析，采取構(gòu)建二元比較樹(shù)的方式。只進(jìn)行元素間的比較而不實(shí)施其他運(yùn)算。23二元比較樹(shù)-順序檢索n個(gè)元素存在如下關(guān)系：A(1)A(2)A(n)，檢索某一給定元素x是否在A中出現(xiàn)x:A(1)x:A(2)x:A(n)不成功不成功不成功不成功線性檢索24二元比較樹(shù)-二分檢索x:A(n1)2)x:A(3(n1)4)x

14、:A(n1)4)x:A(n)x:A(n1)21)x:A(n1)21)x:A(1)不成功不成功不成功不成功不成功不成功不成功不成功25以比較為基礎(chǔ)檢索的時(shí)間下界定理4.3: 設(shè)A(1:n)含有n(n1)個(gè)不同的元素，排序?yàn)锳(1)A(2)A(n)；又設(shè)用以比較為基礎(chǔ)去判斷是否xA(1:n)的任何算法在最壞情況下所需的最小比較次數(shù)是FIND(n)，那么FIND(n)log(n1) .證明P77結(jié)論：二分檢索是解決檢索問(wèn)題的最優(yōu)的最壞情況算法。定理表明: 任何一種以比較為基礎(chǔ)的算法，其最壞情況下的計(jì)算時(shí)間都不可能低于O(logn)，也就是不可能存在其最壞情況下計(jì)算時(shí)間比二分檢索算法的計(jì)算時(shí)間數(shù)量級(jí)還

15、低的算法。26思考題證明EI2n。證明BINSRCH1的最好、最壞和平均情況時(shí)間對(duì)于成功和不成功的檢索都是(logn)。三分（多分）檢索會(huì)得到更優(yōu)的結(jié)果嗎？274.3 找最大和最小元素問(wèn)題描述：在含有n個(gè)不同元素的集合中同時(shí)找出 它的最大和最小元素procedure STRAITMAXMIN(A, n, max, min)int i, n;maxmin A1;for i 2 to n do if Aimax then maxAi;endif; if Aimin then minAi;endif; end STRAITMAXMIN直接算法：依次比較n1個(gè)元素，同時(shí)記錄下最大、最小的元素if Ai

16、max then maxAi;else if Aimin then minAi;endif直接算法的時(shí)間復(fù)雜度在最好、最壞、平均情況下均為2(n1)改進(jìn)后的計(jì)算時(shí)間:(元素升序)最好情況為(n1)(元素降序)最壞情況為2(n1)平均情況為32(n1)改進(jìn)28采用分治策略求最大最小元素I(n,A(1),A(n)劃分為I1=(n2 ,A(1),A( n 2 ) )I2=( n n2 ,A(n2 +1 ),A(n) )結(jié)果的合并29procedure MAXMIN( i, j, fmax, fmin)int i, j; global n, A(1:n);case ij: fmaxfminAi i j

17、1: if AiAj then fmaxAj; fminAi; else fmaxAi; fminAj; else: mid(ij)2; call MAXMIN( i, mid, gmax, gmin) call MAXMIN(mid1, j, hmax, hmin) fmax max(gmax, hmax); fmin min(gmin, hmin); endcaseend MAXMIN分治法求最大和最小元素只有一個(gè)或兩個(gè)元素時(shí)遞歸調(diào)用部分兩個(gè)子問(wèn)題的答案進(jìn)行合并4.3 找最大和最小元素30A(1)(2)(3)(4)(5)(6)(7)(8)(9)元素2213-5-815601731471,9

18、,1,3,4,5,3,3,1,2,1,5,6,9,8,9,6,7, 22,13 -5,-5 22,-515,-8 22,-8 60,-860,1760,17 47,31實(shí)例: A(1:n)，n9，元素具體如下表所示：4.3 找最大和最小元素31過(guò)程MAXMIN的時(shí)間復(fù)雜度MAXMIN的元素比較次數(shù)當(dāng)n2k (k是某個(gè)正整數(shù))時(shí)，有T(n)3n22T(n)= 2T(n/2)2 = 2(2T(n/4)2)2 = 4T(n/4)42 = 2k1T(2)( 2k1 2k2222 ) =2k12k2 =3n/22與直接算法的比較次數(shù)2(n1)相比，比較次數(shù)減少了25 %。0 n11 n2T(n)T( n

19、2 ) T(n2 )2 n24.3 找最大和最小元素32可以證明：任何一種以比較為基礎(chǔ)的找最大和最小元素的算法，其元素比較次數(shù)的下界為 3n2 2但是不代表該算法最優(yōu)，理由如下：MAXMIN算法分析MAXMIN所需的存儲(chǔ)空間比直接算法多4.3 找最大和最小元素給出n個(gè)元素，則MAXMIN算法有 logn 1級(jí)的遞歸，每次遞歸都需要保存i、j、fmax、fmin和返回地址5個(gè)值。直接算法需要空間為：n3，用n個(gè)位置存放數(shù)組A，還有i、max、min三個(gè)變量需要存儲(chǔ)33元素A(i)和A(j)的比較與i和j的比較時(shí)間相差不大時(shí)，過(guò)程MAXMIN不可取。 設(shè)MAXMIN的頻率計(jì)數(shù)為C(n)，n2k ,

20、 k為整數(shù), 當(dāng)n2時(shí), 有: C(n)5n23 4.3 找最大和最小元素C(n) 2C(n2)3 2(2C(n4)3)3 4C(n4)63 2k1C(2)3( 2k22k3222120 ) 2k3(2k11) 2k32k13 5n232 n2C(n)=2C( n2 )3 n234直接算法的比較次數(shù)為2(n1)，加上實(shí)現(xiàn)for循環(huán)需要的比較次數(shù)，則為3(n1)，雖然3(n1)略大于 5n23，但MAXMIN算法還有遞歸所帶來(lái)的時(shí)間開(kāi) 銷(xiāo)， 這種情況下直接算法要快一些。結(jié)論：如果數(shù)組A的元素之間的比較遠(yuǎn)比整型變量的比較代價(jià)昂貴，則分治法產(chǎn)生效率較高的算法；反之則得到一個(gè)效率較低的程序。4.3 找

21、最大和最小元素354.4 歸并分類(lèi)問(wèn)題描述及一般方法思想(直接插入法)直接插入算法描述及實(shí)例歸并分類(lèi)算法思想、描述及實(shí)例合并算法思想、描述及實(shí)例歸并分類(lèi)算法的計(jì)算時(shí)間歸并分類(lèi)算法的缺點(diǎn)及改進(jìn)方法以比較為基礎(chǔ)分類(lèi)的時(shí)間下界36一般方法(直接插入法)for j2 to n do將A(j)放入已分類(lèi)集合A(1:j1)repeat問(wèn)題描述及一般方法思想問(wèn)題描述：給定一個(gè)含有n個(gè)元素的集合，把它們按一定的次序分類(lèi)(如非降次序)最壞情況下，為了插入A(j)，有可能移動(dòng)A(1:j1)中的所有元素。37procedure INSERTIONSORT(A, n)A(0) for j 2 to n do item

22、 A(j); i j1; while ( itemA(i) do A(i1)A(i); ii1; repeat A(i1) item;repeat end INSERTIONSORT數(shù)組元素的比較和移動(dòng)將本次考慮的元素插入相應(yīng)位置可能執(zhí)行0j次(j2,3n)最好情況 (n)最壞情況的計(jì)算時(shí)間：2n(n(n1)/2)1(n2)用item保存當(dāng)前元素值算法4.7 插入分類(lèi)算法描述38A0A1A2A3A4A5639413639449, A4A3; 936, A2A1; 6496, 不用移動(dòng)119, A5A4; 964313, A1346, A3A2;43, A2416, A4A3;14, A3A2;

23、13, A2A1;1, A11注：加一個(gè)元素A0從元素A2開(kāi)始比較插入分類(lèi)的一個(gè)實(shí)例procedure INSERTIONSORT(A, n)A(0) for j 2 to n do item A(j); i j1; while ( itemA(i) do A(i1)A(i); ii1; repeat A(i1) item;repeat end INSERTIONSORT39可能執(zhí)行0j次(j2,3n)最好情況 (n)最壞情況的計(jì)算時(shí)間：2n=(n(n1)/2)1(n2)算法4.7 插入分類(lèi)算法描述有沒(méi)有其他算法？它的最壞情況的計(jì)算時(shí)間要好于插入分類(lèi)算法。40分治策略設(shè)計(jì)歸并分類(lèi)算法分：將A(

24、1),A(n)平均分為2個(gè)子集合： A(1),A(n2 )和A(n21),A(n)治：遞歸調(diào)用分類(lèi)算法，將2個(gè)子集合分類(lèi)合：將2個(gè)分類(lèi)的子集合并為一個(gè)分類(lèi)集合41遞歸調(diào)用，分別對(duì)分解出來(lái)的兩個(gè)子問(wèn)題排序合并兩個(gè)已排好的序列，得到原問(wèn)題的解Procedure MERGESORT(low, high)int low, high, mid;if (lowhigh) then mid (lowhigh)2 call MERGESORT(low, mid) call MERGESORT(mid1,high) call MERGE(low, mid, high) end MERGESORT算法4.8歸并分

25、類(lèi)算法描述42歸并分類(lèi)實(shí)例A1A2A3A4A563941A1A2A3639A4A541A1A263A393636914A16A23A44A5113469431,54,51,35,54,43,31,21,12,2表示一次調(diào)用時(shí)的low和high的值只含單個(gè)元素的子集合1，1，24，4，51，2，31，3，5表示MERGE調(diào)用時(shí)low, mid, high 的值MERGESORT(low, high)MERGE(low,mid,high)44合并函數(shù)MERGE算法思想 A(low) A(mid)A(mid1) A(high) B(low) B(high)jhi 如果h mid 且 j high，那

26、么B(i) min(A(h), A(j)(2) 如果hmid 且 j high，那么B(i) A(j)(3) 如果hmid 且 j high，那么B(i) A(h)45procedure MERGE(low, mid, high)int h,i,j, k, low, mid, high; global A(low : high); local B(low : high);hlow; ilow; jmid1;while (hmid and jhigh) do if (A(h) A(j) then B(i) A(h); hh1; else B(i) A(j); jj1; ；endif ii1;re

27、peat if (hmid) then for kj to high do B(i)A(k);ii1 else for kh to mid do B(i)A(k);ii1 for k low to high do A(k) B(k);end MERGE處理兩個(gè)已分類(lèi)的序列剩余元素處理過(guò)程將已分類(lèi)的集合復(fù)制到A數(shù)組算法4.9MERGE算法描述46一個(gè)合并的例子A1A2A3A4A563941B1B2B3B4B53636hjihjii(1) low1，mid1，high2A1A2A3A4A536941B1B2B3B4B536369369(2) low1，mid2，high3hji1312323333

28、4447hji454(3) low4，mid4，high5465566A1A2A3A4A536941B1B2B3B4B53694141A1A2A3A4A536914B1B2B3B4B5369141346913469(4) low1，mid3，high5hji14115225326436546648歸并分類(lèi)的計(jì)算時(shí)間T(n)a n1 , a是常數(shù)2T(n2)cn n1 , c是常數(shù)當(dāng) n2k時(shí)，可得T(n) 2(2T(n/4)+cn/2)+cn 22T(n/4)+2cn 22(2T(n/8)+cn/4)+2cn 23T(n/8)+3cn 2kT(1)+kcn an+cnlogn如果2kn2k+1

29、，有T(n)T(2k1)則有T(n)O(nlogn)歸并2個(gè)子數(shù)組所需的元素比較次數(shù)在n/2到n1之間49時(shí)間: 當(dāng)子集合的元素很少時(shí)，算法的很多時(shí)間消耗在 遞歸的處理上。改進(jìn): 當(dāng)子集合的元素個(gè)數(shù)適當(dāng)少時(shí)，采用在小規(guī)模 集合上能有效工作的插入分類(lèi)算法進(jìn)行排序，而不是繼續(xù)劃分，以此克服上述缺點(diǎn)帶來(lái)的時(shí)間消耗?？臻g: 輔助數(shù)組B的使用增加了算法的空間，且每次 調(diào)用MERGE時(shí)，都需要將B中的結(jié)果復(fù)制回A 中，消耗了一部分時(shí)間。改進(jìn): 用一個(gè)鏈接數(shù)組LINK(1:n)代替B，LINK中的 元素為A中元素的下標(biāo)，它指示下一個(gè)元素所在 的下標(biāo)位置。歸并分類(lèi)算法的缺點(diǎn)50 LINK(1:n)為一鏈接數(shù)組

30、，取值范圍為1, 2, , n。可看成是A元素的指針，在分類(lèi)表中它指向下一個(gè)元素所在的下標(biāo)位置，用0表示結(jié)束。(1)(2)(3)(4)(5)(6)(7)(8)34018706q2的表為(2, 4, 1, 3) A(2)A(4) A(1)A(3)r5的表為(5, 8 , 6, 7) A(5)A(8)A(6)A(7)(1)(2)(3)(4)(5)(6)(7)(8)4332693523588946數(shù)組A:數(shù)組LINK:關(guān)于LINK數(shù)組 實(shí)例：下面是一個(gè)LINK集合，包含了兩個(gè)已分類(lèi)的子集合。q和r表示兩個(gè)子集合的起始處：q2，r5qr51procedure MERGESORT1(low, high,

31、 p)global A(low:high), LINK(low:high)if (highlow116 ) then call INSERTIONSORT(A, LINK, low, high, p);else mid (lowhigh)2 ; call MERGESORT1(low, mid, q); call MERGESORT1(mid1, high, r); call MERGE1(q, r, p);endif end MEGESORT1當(dāng)集合元素小于16時(shí), 調(diào)用修改的插入分類(lèi)算法歸并分類(lèi)遞歸調(diào)用合并兩個(gè)子問(wèn)題的解改進(jìn)的歸并分類(lèi)算法52procedure MERGE1(q, r, p

32、)global n, A(1:n), LINK(0:n); int i, j, k;i q; j r; k 0;while (i0 and j0) do if (A(i)A(j) then LINK(k)i;ki;iLINK(i); else LINK(k)j;kj;jLINK(j);if (i0) then LINK(k)j; else LINK(k)i;pLINK(0);end MERGE1當(dāng)q和r非空時(shí)進(jìn)行以下操作: 加入一個(gè)關(guān)鍵字的下標(biāo)到LINK數(shù)組中處理剩下的關(guān)鍵字使用LINK數(shù)組的歸并函數(shù)53(1)(2)(3)(4)(5)(6)(7)(8)5010253015703555數(shù)組A:M

33、SORT1(1, 8, p)if (8115 ) then ISTSORT(A,LINK,1,8,p);else mid (18)24 ; MSORT1(1, 4, q); MSORT1(5, 8, r); MERGE1(q, r, p);end MSORT1 MSORT1(1, 4, q)if (4115 ) then ISTSORT(A,LINK,1,4,p);end MSORT1 返回q2MSORT1(5, 8, r)if (8515 ) then ISTSORT(A,LINK,5,8,p);end MSORT1 返回r5MERGE1(2,5,p);(0)(1)(2)(3)(4)(5)(

34、6)(7)(8)000000000數(shù)組LINK:034170862554012345678003417086數(shù)組LINK:MERGE1(2, 5, p)i2; j5; k0;while (i0 and j0) do if (A2A5) then LINK02; k2; i3; 2534718123456785010253015703555if (A3A5) else LINK25; k5; j7; if (A3A7) then LINK53; k3; i4; if (A4A7) then LINK34; k4; i1; if (A1A7) else LINK47; k7; j8; if (A1

35、A8) then LINK71; k1; i0; if (i0) then LINK18;pLINK02;數(shù)組A:2534718655思考題改進(jìn)的歸并分類(lèi)算法的計(jì)算時(shí)間是多少？歸并過(guò)程可以采用自底向上的設(shè)計(jì)方式來(lái)取消對(duì)?？臻g的需要，試給出算法描述。56 任何以關(guān)鍵字比較為基礎(chǔ)的分類(lèi)算法，最壞情況下的時(shí)間下界都是(nlogn)，因此從數(shù)量級(jí)的角度上看, 歸并分類(lèi)是最壞情況下的最優(yōu)算法。 采用二元比較樹(shù)證明以比較為基礎(chǔ)分類(lèi)的時(shí)間下界57對(duì)3個(gè)關(guān)鍵字分類(lèi)的二元比較樹(shù)1:21:31:32:32:31,2,31,3,23,1,22,1,32,3,13,2,1A(1)A(2)A(2)A(3)A(1)A(3

36、)A(2)A(3)A(1)A(3)表示一次比較一種可能的分類(lèi)序列假設(shè)參加分類(lèi)的n個(gè)關(guān)鍵字A(1), , A(n)各不相同。那么任意兩個(gè)關(guān)鍵字A(i)和A(j)的比較必然導(dǎo)致A(i)A(j)或者A(i)A(j)。58分析最壞情況下比較次數(shù) 比較樹(shù)的最長(zhǎng)路徑 根到最遠(yuǎn)葉結(jié)點(diǎn)距離 樹(shù)高T(n)從根到外節(jié)點(diǎn)的每一條路徑分別與一種唯一的排列相對(duì)應(yīng)。n個(gè)關(guān)鍵字有n！種排列。 比較樹(shù)必定至少有n！ 個(gè)外節(jié)點(diǎn)。2T(n)n!2T(n)n! n(n1)(n2)(n/2) (n/2)n/2T(n)(n2)log(n2)(n4)lognT(n) (n log n)n4時(shí)，有n2 n1/2任何以關(guān)鍵字比較為基礎(chǔ)的分類(lèi)

37、算法，最壞情況下的時(shí)間下界都是(nlogn)。594.5 快速分類(lèi)快速分類(lèi)的基本思想：選取數(shù)組A中的某個(gè)元素 tAs，然后將其他元素 重新排列，使A中所有在t以前出現(xiàn)的元素都小于或等于t，而在t之后出現(xiàn)的元素都大于或等于t。這個(gè)重新整理的過(guò)程稱(chēng)為劃分，t稱(chēng)為劃分元素。A1A2As1AsAs1An劃分元素t經(jīng)過(guò)一次劃分后A1A2AjtAkAn每個(gè)元素都小于或等于t每個(gè)元素都大于或等于t60A1A2A3A4A5A6A75392718 第1次劃分，選tA1，即t5，劃分后得到如下結(jié)果： A1A2A3A4A5A6A72315798 第2次劃分，選tA1，即t2，劃分后結(jié)果： A1A2A3A4A5A6A

38、71235798 第3次劃分，選tA5，即t7，劃分后沒(méi)有變化 第4次劃分，選tA6，即t9，劃分后結(jié)果： A1A2A3A4A5A6A71235798A1A2A3A4A5A6A71235789快速分類(lèi)實(shí)例61procedure QUICKSORT(low,high)int low,high; global n, A(1:n)if lowhigh then jhigh1 call PARTITION(low, j) call QUICKSORT(low, j1) call QUICKSORT(j1, high) endifend QUICKSORT快速分類(lèi)算法劃分A(low, high), 函數(shù)

39、執(zhí)行完后, j返回劃分元素的下標(biāo)遞歸調(diào)用劃分之后得到的兩個(gè)集合62procedure PARTITION(m, p)int m,p,i; global A(m:p1)vAm; im;loop loop ii1 until Aiv ; loop pp1 until Apv ; if (ip) then call INTERCHANGE(Ai, Ap) else exitrepeatAmAp; Apv;end PARTITIONPARTITION劃分過(guò)程的實(shí)現(xiàn)交換Ai和Ap結(jié)束過(guò)程時(shí), 參數(shù)p中的值為劃分元素所在位置的下標(biāo), 該值將帶回, 用于后面的QUICKSORT過(guò)程i從左向右移，直到Ai t

40、 p從右向左移，直到Apt63首先調(diào)用QUICKSORT(1,7) /low1, high7if 17 then j8; call PARTITION(1, 8); call QUICKSORT(low, j 1) call QUICKSORT(j+1, high) end QUICKSORT快速分類(lèi)實(shí)例分析過(guò)程(I)等PARTITION(1, 8)調(diào)用結(jié)束后,返回參數(shù)j的值，才能執(zhí)行遞歸調(diào)用PARTITION(m, p) /m1, p8tAm5; im1;loop(第1次) loop i until Ait ; i3 loop p until Apt ; p6 if (ip) then Ai

41、 Ap; A1A2A3A4A5A6A75392718A1A2A3A4A5A6A7531279864AmAp; 即A1A42Apt; 即A45end / p4的值帶回loop(第2次,i3, p6) loop i until Ait ; i5 loop p until Apt ; p4 if (ip) 執(zhí)行else exit loop1 A1A2A3A4A5A6A75312798A1A2A3A4A5A6A72315798遞歸調(diào)用QUICKSORT(low, j1) 即QUICKSORT(1, 3)遞歸調(diào)用QUICKSORT(j1,high) 即QUICKSORT(5, 7)快速分類(lèi)實(shí)例分析過(guò)程(II)65快速分類(lèi)算法的分析 I ：時(shí)間復(fù)雜性假設(shè)前提互不相同；隨機(jī)選取劃分元素劃分單元隨機(jī)選取的改進(jìn)快速分類(lèi)的性能取決于劃分的對(duì)稱(chēng)性！隨機(jī)選取更合理，因?yàn)樽詈媚苷业街虚g元素最壞情況下