算法分析第四章

1、1第四章第四章分治法分治法24.1 一般方法一般方法4.2 二分檢索二分檢索4.3 找最大和最小元素找最大和最小元素4.4 歸并分類歸并分類4.5 快速分類快速分類4.6 選擇問題選擇問題4.7 斯特拉森矩陣乘法斯特拉森矩陣乘法主要內(nèi)容主要內(nèi)容3輸入規(guī)模相當(dāng)大時，直接求解很困難。輸入規(guī)模相當(dāng)大時，直接求解很困難。分析問題的特征，選擇適當(dāng)?shù)脑O(shè)計(jì)策略。分析問題的特征，選擇適當(dāng)?shù)脑O(shè)計(jì)策略。將一個難以直接解決的大問題，分割成一些規(guī)模將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。較小的相同問題，以便各個擊破，分而治之。4.1 一般方法一般方法4分治法的思想分治法的思想

2、: 將一個輸入規(guī)模為將一個輸入規(guī)模為n的問題分解為的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨(dú)立且與個規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題性質(zhì)相同，求出這些子問題解后，可以用原問題性質(zhì)相同，求出這些子問題解后，可以用適當(dāng)?shù)姆椒▽⒏髯訂栴}的解合并成原問題的解。適當(dāng)?shù)姆椒▽⒏髯訂栴}的解合并成原問題的解。問題問題(n個輸入個輸入)子問題子問題1子問題子問題2子問題子問題k子問題子問題1子問題子問題2子問題子問題k相同類型相同類型合并解合并解5步驟：步驟：分（分（divide）二分為主二分為主多分比二分更好嗎？多分比二分更好嗎？ 治（治（conquer）遞歸調(diào)用，當(dāng)規(guī)模足夠小時直接處理

3、遞歸調(diào)用，當(dāng)規(guī)模足夠小時直接處理 合（合（combine）4.1 一般方法一般方法6分治策略分治策略DANDC的抽象化控制的抽象化控制procedure DANDC(p,q)global n, A(1:n); integer m, p, q; /1 p q n/if SMALL(p,q) then return(G(p,q) else mDIVIDE(p,q) return(COMBINE (DANDC(p,m), DANDC(m+1,q)endifend DANDC判斷輸入規(guī)模判斷輸入規(guī)模q p+1是否足夠小是否足夠小,可直接求解可直接求解G是直接求解該規(guī)模問題的函數(shù)是直接求解該規(guī)模問題的函

4、數(shù)分割函數(shù)分割函數(shù), p m q, 原問題被分為原問題被分為A(p:m)和和A(m+1:q)兩個子問題兩個子問題合并函數(shù)合并函數(shù),將兩個子問題的解合并為原問題的解將兩個子問題的解合并為原問題的解原問題為原問題為A(1:n) , 最初調(diào)用函數(shù)應(yīng)該是最初調(diào)用函數(shù)應(yīng)該是DANDC(1, n); DANDC(p, q)是計(jì)算是計(jì)算A(p: q)子問題的解子問題的解.4.1 一般方法一般方法7二分策略二分策略DANDC的計(jì)算時間的計(jì)算時間倘若所分成的兩個子問題的輸入規(guī)模大致相等倘若所分成的兩個子問題的輸入規(guī)模大致相等,則分治策略則分治策略DANDC的計(jì)算時間可表示為：的計(jì)算時間可表示為： 說明：說明：T

5、(n)：輸入規(guī)模為：輸入規(guī)模為n時，分治策略的計(jì)算時間時，分治策略的計(jì)算時間g(n)：對足夠小的輸入規(guī)模能直接計(jì)算出答案的時間：對足夠小的輸入規(guī)模能直接計(jì)算出答案的時間f(n)：COMBINE函數(shù)合成原問題解的計(jì)算時間函數(shù)合成原問題解的計(jì)算時間g(n)n足夠小足夠小2T(n/2)+f(n)否則否則T(n)=4.1 一般方法一般方法8一個分治法將規(guī)模為一個分治法將規(guī)模為n的問題分成的問題分成k個規(guī)模為個規(guī)模為n/m的子問題去解。的子問題去解。設(shè)分解閾值設(shè)分解閾值n0=1，且解規(guī)模為，且解規(guī)模為1的問題需耗費(fèi)常數(shù)時間。再設(shè)將的問題需耗費(fèi)常數(shù)時間。再設(shè)將原問題分解為原問題分解為k個子問題以及將個子問

6、題以及將k個子問題的解合并為原問題的個子問題的解合并為原問題的解需用解需用f(n) 時間。用時間。用T(n)表示該分治法解規(guī)模為表示該分治法解規(guī)模為|P|=n的問題所的問題所需的計(jì)算時間，則有：需的計(jì)算時間，則有：11)()/() 1 ()(nnnfmnkTOnT通過迭代法求得方程的解：通過迭代法求得方程的解：1log0log)/()(nmjjjkmmnfknnT注意注意：遞歸方程及其解只給出遞歸方程及其解只給出n等于等于m的方冪時的方冪時T(n)的值，但的值，但是如果認(rèn)為是如果認(rèn)為T(n)足夠平滑，那么由足夠平滑，那么由n等于等于m的方冪時的方冪時T(n)的值的值可以估計(jì)可以估計(jì)T(n)的增

7、長速度。通常假定的增長速度。通常假定T(n)是單調(diào)上升的，從是單調(diào)上升的，從而當(dāng)而當(dāng)minmi+1時，時，T(mi)T(n)T(mi+1). 9問題描述問題描述: 已知一個按已知一個按非降序排列非降序排列的元素表的元素表a1, a2, , an , 判定某個給定元素判定某個給定元素x是否在該表中出現(xiàn)，若是是否在該表中出現(xiàn)，若是, 則找則找出該元素在表中的位置出該元素在表中的位置,并將下標(biāo)值賦給并將下標(biāo)值賦給j, 否則置否則置j為為0.二分檢索原理二分檢索原理將將二分檢索二分檢索問題表示為：問題表示為：I=(n, a1, , an, x)選取一個下標(biāo)選取一個下標(biāo)k，可得到三個子問題：，可得到三個

8、子問題：vI1=(k 1, a1, , ak-1, x)vI2=(1, ak , x)vI3=(n k, ak+1, , an, x)4.2 二分檢索二分檢索對所求解的問題（或子問題）所選的下標(biāo)都是對所求解的問題（或子問題）所選的下標(biāo)都是中間元素的下標(biāo)：中間元素的下標(biāo)：k= (n+1) /2 10procedure BINSRCH(A, n, x, j) integer low, high, mid, j, n; low1; highn while low high do mid (low+high)/2 /*取中間值取中間值*/ case :xA(mid): lowmid+1 /*在后一半尋

9、找在后一半尋找*/ : else: jmid; return; /*檢索成功檢索成功, 結(jié)束結(jié)束*/ endcase repeat j0 /*檢索失敗檢索失敗*/end BINSRCH二分檢索算法二分檢索算法11檢索檢索x=9, 9=A(5), 一次比較就成功一次比較就成功, 最好情況最好情況 15 6079235482101A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) A(9)檢索檢索x= 15, 15A(5), 15A(5), 101A(7), 101A(8), 101= A(9), 4次比較次比較, 成功成功檢索檢索x=8, 8A(2), 8A(3),

10、8A(4), 4次比較次比較, 不成功檢索不成功檢索二分檢索實(shí)例二分檢索實(shí)例:設(shè)在設(shè)在A(1:9)中順序放了以下中順序放了以下9個元素：個元素：12用五個特性判斷是否是一個算法用五個特性判斷是否是一個算法證明算法正確性證明算法正確性n假定：比較運(yùn)算能恰當(dāng)?shù)貓?zhí)行，過程中所有的語假定：比較運(yùn)算能恰當(dāng)?shù)貓?zhí)行，過程中所有的語句按要求工作句按要求工作n初始狀態(tài)：初始狀態(tài)：low=1, high=n, n 0, A(1) A(n).nn=0nn0二分檢索算法正確性證明：二分檢索算法正確性證明：13二分檢索算法所需的空間和時間二分檢索算法所需的空間和時間v所需空間所需空間: 用用n個位置存放數(shù)組個位置存放數(shù)

11、組A，還有，還有l(wèi)ow, high, mid, x, j五個五個 變量需要存儲，變量需要存儲，共需空間共需空間 n+5v所需計(jì)算時間所需計(jì)算時間: 對于計(jì)算時間，需要分別考慮以下幾種情況：對于計(jì)算時間，需要分別考慮以下幾種情況： 成功檢索成功檢索的最好情況、平均情況、最壞情況的最好情況、平均情況、最壞情況 不成功檢索不成功檢索的最好情況、平均情況、最壞情況的最好情況、平均情況、最壞情況4.2 二分檢索二分檢索14-15-6079235482101A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) A(9)3234132343334433344成功檢索有成功檢索有n種

12、情況，不成功檢索有種情況，不成功檢索有n+1種情況種情況成功：成功：不成功：不成功：不論檢索是否成功，算法的執(zhí)行過程都是不論檢索是否成功，算法的執(zhí)行過程都是x與一系列與一系列中間元素中間元素A(mid)的比較過程，可以用一棵二元比較的比較過程，可以用一棵二元比較樹來描述算法的執(zhí)行過程。樹來描述算法的執(zhí)行過程。15二元比較樹二元比較樹內(nèi)結(jié)點(diǎn)內(nèi)結(jié)點(diǎn)表示一表示一次元素的比較次元素的比較,存放一個存放一個mid值值外結(jié)點(diǎn)外結(jié)點(diǎn)表示不成功表示不成功檢索的一種情況檢索的一種情況592-61-1530754476238829101一條路徑表一條路徑表示一個元素示一個元素的比較序列的比較序列4.2 二分檢索二

13、分檢索16二分檢索的時間復(fù)雜度二分檢索的時間復(fù)雜度定理定理4.2: 若若n在區(qū)域在區(qū)域2k- -1, 2k)中，則對于一次成功的檢中，則對于一次成功的檢索，二分檢索算法至多作索，二分檢索算法至多作k次比較，而對于一次不成次比較，而對于一次不成功的檢索，或者作功的檢索，或者作k 1次比較或者作次比較或者作k次比較。次比較。4.2 二分檢索二分檢索證明：考察二分檢索算法執(zhí)行過程的二元比較樹：證明：考察二分檢索算法執(zhí)行過程的二元比較樹：成功檢索內(nèi)結(jié)點(diǎn)，不成功檢索外結(jié)點(diǎn)成功檢索內(nèi)結(jié)點(diǎn)，不成功檢索外結(jié)點(diǎn)由于由于2k 1 n 2k,內(nèi)結(jié)點(diǎn)級數(shù)內(nèi)結(jié)點(diǎn)級數(shù) k，外結(jié)點(diǎn)級數(shù)，外結(jié)點(diǎn)級數(shù) k+1 成功檢索所需要的

14、元素比較次數(shù)成功檢索所需要的元素比較次數(shù)=級數(shù)級數(shù)，不成功檢索所需要的元素比較次數(shù)不成功檢索所需要的元素比較次數(shù)=級數(shù)級數(shù) 1.17二分檢索的時間復(fù)雜度二分檢索的時間復(fù)雜度對前面二分檢索實(shí)例對前面二分檢索實(shí)例n=9, n 23, 24), 已分析過成功檢已分析過成功檢索和不成功檢索的各種情況下的比較次數(shù)索和不成功檢索的各種情況下的比較次數(shù) 4, 易知易知: (logn)(logn)(logn)(logn)(logn)(1)不成功的檢索不成功的檢索成功的檢索成功的檢索最壞情況最壞情況平均情況平均情況最好情況最好情況計(jì)算時間計(jì)算時間4.2 二分檢索二分檢索內(nèi)部路徑長度內(nèi)部路徑長度I：由根到所有內(nèi)部

15、結(jié)點(diǎn)的距離之和：由根到所有內(nèi)部結(jié)點(diǎn)的距離之和外部路徑長度外部路徑長度E：由根到所有外部結(jié)點(diǎn)的距離之和：由根到所有外部結(jié)點(diǎn)的距離之和18關(guān)于確切比較次數(shù)的討論：關(guān)于確切比較次數(shù)的討論：BINSRCH的的case語句：元素比較次數(shù)的假定不合語句：元素比較次數(shù)的假定不合理，但對時間的近似表示無影響。理，但對時間的近似表示無影響。實(shí)際上可以用實(shí)際上可以用if語句替代語句替代BINSRCH相應(yīng)相應(yīng)case語句語句If xA(mid) then low mid+1 else j mid; return endifendif 每次循環(huán)固定一次比較的每次循環(huán)固定一次比較的BINSRCH1算法算法Case:xA

16、(mid): lowmid+1 : else: jmid; return; endcase19procedure BINSRCH1(A, n, x, j) integer low, high, mid, j, n; low1; highn+1 / high總比可能的取值大總比可能的取值大1 / while lowhigh 1 do mid (low+high)/2 if xA(mid) then highmid else lowmid / x A(mid) / endif repeat if x=A(low) then jlow / 檢索成功檢索成功 / else j0 / 檢索失敗檢索失敗

17、/ endifend BINSRCH二分檢索算法二分檢索算法20檢索檢索x=9, low=1, high=10, mid=5, x=9 A(5)=9; low=5, high=10, mid=7, x=9 A(7)=54; low=5, high=7, mid=6, x=9 A(6)=23; low=5, high=6, low=high-1,退出退出while循環(huán)循環(huán); x=A(5), j=low=5, 程序結(jié)束程序結(jié)束. 15 6079235482101A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) A(9)二分檢索實(shí)例二分檢索實(shí)例:設(shè)在設(shè)在A(1:9)中順

18、序放了以下中順序放了以下9個元素：個元素：21以比較為基礎(chǔ)檢索的時間下界以比較為基礎(chǔ)檢索的時間下界思考思考: 對于已排序的對于已排序的n個元素個元素, 檢索某元素檢索某元素x是否出現(xiàn)是否出現(xiàn), 是否存在以比較為基礎(chǔ)的檢索算法是否存在以比較為基礎(chǔ)的檢索算法, 在在最壞情況最壞情況下該下該算法比二分檢索算法在計(jì)算時間上有算法比二分檢索算法在計(jì)算時間上有更低的數(shù)量級更低的數(shù)量級?對于以比較為基礎(chǔ)的檢索算法的分析，采取構(gòu)建二對于以比較為基礎(chǔ)的檢索算法的分析，采取構(gòu)建二元比較樹的方式。元比較樹的方式。22二元比較樹二元比較樹-順序檢索順序檢索n個元素存在如下關(guān)系的個元素存在如下關(guān)系的:A(1)A(2)A

19、(n),檢檢索一給定元素索一給定元素x是否在是否在A中出現(xiàn)中出現(xiàn)x:A(1)x:A(2)x:A(n)不成功不成功不成功不成功不成功不成功不成功不成功線性檢索線性檢索23二元比較樹二元比較樹-二分檢索二分檢索X:A( (n+1)/2 )X:A( 3(n+1)/4 )X:A( (n+1)/4 )X:A(n)X:A( (n+1)/2 +1)X:A( (n+1)/2 -1)X:A(1)不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功24以比較為基礎(chǔ)檢索的時間下界以比較為基礎(chǔ)檢索的時間下界v定理定理4.3: 設(shè)設(shè)A(1:n)含有含有n(n 1)個不同的元素

20、，排序個不同的元素，排序?yàn)闉锳(1)A(2)max then max Ai; if Aimax then max=Ai;else if Aimin then min=Ai;v直接算法的時間復(fù)雜度在最好、最壞、平均情況下均為直接算法的時間復(fù)雜度在最好、最壞、平均情況下均為2(n- -1)改進(jìn)后的計(jì)算時間改進(jìn)后的計(jì)算時間:(元素升序元素升序)最好情況為最好情況為(n-1)(元素降序元素降序)最壞情況為最壞情況為2(n-1)平均情況為平均情況為3/2(n-1)改進(jìn)改進(jìn)26采用分治策略求最大最小元素采用分治策略求最大最小元素I=(n,A(1),A(n)劃分為劃分為I1=( n/2 ,A(1),A( n

21、/2 ) )I2=( n- n/2 ,A( n/2 +1 ),A(n) )結(jié)果的合并結(jié)果的合并27分治法求最大和最小元素分治法求最大和最小元素procedure MAXMIN( i, j, fmax, fmin)int i, j; global n, A(1:n);case i= j: fmax fmin Ai i= j- -1: if Ai212210nnjj4.3 找最大和最小元素找最大和最小元素30可以證明可以證明: 任何一種以比較為基礎(chǔ)的找最大和最小元任何一種以比較為基礎(chǔ)的找最大和最小元素的算法，其元素比較次數(shù)的下界為素的算法，其元素比較次數(shù)的下界為 3n/2 - -2但是不代表該算法

22、最優(yōu)，理由如下：但是不代表該算法最優(yōu)，理由如下：MAXMIN算法分析算法分析vMAXMIN所需的存儲空間比直接算法多所需的存儲空間比直接算法多4.3 找最大和最小元素找最大和最小元素給出給出n個元素，則個元素，則MAXMIN算法有算法有 logn +1級的遞歸，級的遞歸，每次遞歸都需要保存每次遞歸都需要保存i, j, fmax, fmin和返回地址和返回地址5個值個值直接算法需要空間為直接算法需要空間為: n+3, 用用n個位置存放數(shù)組個位置存放數(shù)組A，還有還有i, max, min三個變量需要存儲三個變量需要存儲31v元素元素A(i)和和A(j)的比較與的比較與i和和j的比較時間相差不大時，

23、的比較時間相差不大時，過程過程MAXMIN不可取。不可取。 設(shè)設(shè)MAXMIN的頻率計(jì)數(shù)為的頻率計(jì)數(shù)為C(n)，n=2k , k為整數(shù)為整數(shù), 當(dāng)當(dāng)n2時時, 有有: C(n)=5n/2-3 4.3 找最大和最小元素找最大和最小元素C(n)= 2C(n/2)+3 = 2(2C(n/4)+3)+3 = 4C(n/4)+6+3 = 2k-1C(2)+3*( 2k-2 +2k-3+22+21+20 ) =2k+3*(2k-1-1) =2k+3*2k-1-3 =5n/2-32 n=2C(n)=2C( n/2 )+ 3 n212210nnjj32v直接算法的比較次數(shù)為直接算法的比較次數(shù)為2(n-1), 加

24、上實(shí)現(xiàn)加上實(shí)現(xiàn)for循環(huán)循環(huán) 需要的比較次數(shù)需要的比較次數(shù), 則為則為3(n-1), 雖然雖然3(n-1)略大于略大于 5n/2-3, 但但MAXMIN算法還有遞歸所帶來的時間算法還有遞歸所帶來的時間 開銷開銷, 這種情況下直接算法要快一些這種情況下直接算法要快一些結(jié)論結(jié)論: 如果數(shù)組如果數(shù)組A的元素之間的比較遠(yuǎn)比整型的元素之間的比較遠(yuǎn)比整型變量的比較代價昂貴，則分治法產(chǎn)生效率較高變量的比較代價昂貴，則分治法產(chǎn)生效率較高的算法；反之則得到一個效率較低的程序。的算法；反之則得到一個效率較低的程序。4.3 找最大和最小元素找最大和最小元素33 直接方法直接方法(插入法插入法)for j2 to n

25、 do將將A(j)放入已分類集合放入已分類集合A(1:j 1)repeat4.4 歸并分類歸并分類問題描述問題描述: 給定一個含有給定一個含有n個元素的集合，個元素的集合， 把它們按一定的次序分類把它們按一定的次序分類(如非降次序如非降次序)34procedure INSERTIONSORT(A, n)A(0) for j 2 to n do item A(j); i j 1; while ( itemA(i) do A(i+1) A(i); ii 1; repeat A(i+1) item;repeat end INSERTIONSORT插入分類算法描述插入分類算法描述數(shù)組元素的比較和移動數(shù)

26、組元素的比較和移動將本次考慮的元素將本次考慮的元素插入相應(yīng)位置插入相應(yīng)位置可能執(zhí)行可能執(zhí)行0j次次(j=2,3n)最好情況最好情況 (n)最壞情況的計(jì)算時間：最壞情況的計(jì)算時間：2+n=(n(n+1)/2) 1= (n2)用用item保存保存當(dāng)前元素值當(dāng)前元素值4.4 歸并分類歸并分類35分：平均分為分：平均分為2個子集合個子集合治：遞歸調(diào)用分類算法，將治：遞歸調(diào)用分類算法，將2個子集合分類個子集合分類合：將合：將2個分類的子集合并為一個分類集合個分類的子集合并為一個分類集合4.4 歸并分類歸并分類分治策略設(shè)計(jì)歸并分類算法分治策略設(shè)計(jì)歸并分類算法36遞歸調(diào)用，分別對分解遞歸調(diào)用，分別對分解出來

27、的兩個子問題排序出來的兩個子問題排序合并兩個已排好的序合并兩個已排好的序列，得到原問題的解列，得到原問題的解歸并排序算法描述歸并排序算法描述Procedure MERGESORT(low,high)int low, high, mid;if (lowmid) then for kj to high do B(i)A(k);i i+1 else for kh to mid do B(i)A(k);ii+1 for k low to high do A(k) B(k);end MERGE處理兩個已處理兩個已分類的序列分類的序列剩余元素剩余元素處理過程處理過程將已分類的集合復(fù)制到將已分類的集合復(fù)制到

28、A數(shù)組數(shù)組4.4 歸并分類歸并分類38MERGESORT執(zhí)行過程執(zhí)行過程1,54,51,35,54,43,31,21,12,2表示一次調(diào)用時的表示一次調(diào)用時的low和和high的值的值只含單個元只含單個元素的子集合素的子集合1, 1, 24, 4, 51, 2, 31, 3, 5表示表示MERGE調(diào)用時調(diào)用時low, mid, high 的值的值4.4 歸并分類歸并分類39A(1)A(2)A(3)A(4)A(5)310285179652351low=1; mid=1; high=2; h=1; i=1; j=2; while (h mid and j high) do if A(h) A(j)

29、 then else B(i)A(j); jj+1=3 ; ii+1=2; B(1)B(2)B(3)B(4)B(5)285310285310if (hmid) then else for k=1 to 1 do B(i)A(h); ii+1=3; for k=1 to 2 do A(k)B(k); 4.4 歸并分類歸并分類40low=1; mid=2; high=3; h=1; i=1; j=3; while (h mid and j high) do if A(h) A(j) then else B(i)A(j); jj+1=4 ii+1=2; if (hmid) then else for

30、 k=h to mid do B(2)A(k);ii+1=3 B(3)A(k); ii+1=4 for k=1 to 3 do A(k)B(k);A(1)A(2)A(3)A(4)A(5)285310179652351B(1)B(2)B(3)B(4)B(5)1792853101792853104.4 歸并分類歸并分類41low=4; mid=4; high=5; h=4; i=4; j=5; while (h mid and j high) do if A(h) A(j) then else B(i)A(j); jj+1=6 ii+1=5; for k=4 to 5 do A(k)B(k); i

31、f (hmid) then else for k=4 to 4 do B(5)A(4); ii+1=6; A(1)A(2)A(3)A(4)A(5)179285310652351B(1)B(2)B(3)B(4)B(5)3516523516524.4 歸并分類歸并分類42low=1; mid=3; high=5; h=1; i=1; j=4; while (h mid and j high) do if A(h) A(j) then B(i)A(h); hh+1=2 ; ii+1=2; if (hmid) then for k=4 to 5 do B(4)A(4); ii+1=5 for k=1

32、to 5 do A(k)B(k); B(5)A(5); ii+1=6 if A(h) A(j) then B(i)A(h); hh+1=4 ; ii+1=4; if A(h) A(j) then B(i)A(h); hh+1=3 ; ii+1=3; A(1)A(2)A(3)A(4)A(5)179285310351652B(1)B(2)B(3)B(4)B(5)1792853103516521792853103516524.4 歸并分類歸并分類43歸并分類的計(jì)算時間歸并分類的計(jì)算時間T(n)=a n=1 , a是常數(shù)是常數(shù)2T(n/2)+cn n1 , c是常數(shù)是常數(shù)當(dāng)當(dāng) n=2k時，可得時，可得

33、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，有有T(n) T(2k+1)則有則有T(n)=O(nlogn)歸并歸并2個子數(shù)組所需的元素個子數(shù)組所需的元素比較次數(shù)在比較次數(shù)在n/2到到n-1之間之間4.4 歸并分類歸并分類44歸并分類算法的缺點(diǎn)歸并分類算法的缺點(diǎn)缺點(diǎn)缺點(diǎn)1: 當(dāng)子集合的元素很少時，算法的很多時間消耗當(dāng)子集合的元素很少時，算法的很多時間消耗 在遞歸的處理上。在遞歸的處理上。改進(jìn)改進(jìn): 當(dāng)子集合的元素個數(shù)

34、適當(dāng)少時，采用在小規(guī)模當(dāng)子集合的元素個數(shù)適當(dāng)少時，采用在小規(guī)模 集合上能有效工作的集合上能有效工作的插入分類算法進(jìn)行排序，插入分類算法進(jìn)行排序，而不是繼續(xù)劃分，以此而不是繼續(xù)劃分，以此克服上述缺點(diǎn)帶來的時克服上述缺點(diǎn)帶來的時間消耗。間消耗。缺點(diǎn)缺點(diǎn)2: 輔助數(shù)組輔助數(shù)組B的使用增加了算法的空間，且每次的使用增加了算法的空間，且每次 調(diào)用調(diào)用MERGE時，都需要將時，都需要將B中的結(jié)果復(fù)制回中的結(jié)果復(fù)制回A 中，消耗了一部分時間。中，消耗了一部分時間。改進(jìn)改進(jìn): 用一個用一個鏈接數(shù)組鏈接數(shù)組LINK(1:n)代替代替B，LINK中的中的 元素為元素為A中元素的下標(biāo)，它指示下一個元素所在中元素的下

35、標(biāo)，它指示下一個元素所在 的下標(biāo)位置。的下標(biāo)位置。4.4 歸并分類歸并分類45關(guān)于關(guān)于LINK數(shù)組數(shù)組LINK(1:n)為一鏈接數(shù)組，取值范圍為為一鏈接數(shù)組，取值范圍為1, 2, , n?？煽闯墒强煽闯墒茿元素的指針，在分類表中它指向下一個元素的指針，在分類表中它指向下一個元素所在的下標(biāo)位置，用元素所在的下標(biāo)位置，用0表示結(jié)束。表示結(jié)束。實(shí)例實(shí)例: 下面是一個下面是一個LINK集合，包含了兩個已分類的集合，包含了兩個已分類的 子集合。子集合。q和和r表示兩個子集合的起始處表示兩個子集合的起始處:q=2,r=5(1) (2) (3) (4)(5)(6)(7)(8)34018706q=2的表為的表

36、為(2, 4, 1, 3) A(2) A(4) A(1) A(3)r=5的表為的表為(5, 8 , 6, 7) A(5) A(8) A(6) A(7)(1) (2) (3) (4)(5)(6)(7)(8)4332693523588946數(shù)組數(shù)組A:數(shù)組數(shù)組LINK:4.4 歸并分類歸并分類46procedure MERGESORT1(low, high, p)global A(low:high), LINK(low:high)if (high low+116 ) then call INSERTIONSORT(A, LINK, low, high, p);else mid (low+high)

37、/2 ; call MERGESORT1(low, mid, q); call MERGESORT1(mid+1, high, r); call MERGE1(q, r, p);endif end MEGESORT1改進(jìn)的歸并分類算法改進(jìn)的歸并分類算法當(dāng)集合元素小于當(dāng)集合元素小于16時時, 調(diào)用修改調(diào)用修改的插入分類算法的插入分類算法歸并分類歸并分類遞歸調(diào)用遞歸調(diào)用合并兩個子問題的解合并兩個子問題的解4.4 歸并分類歸并分類47使用使用LINK數(shù)組的歸并函數(shù)數(shù)組的歸并函數(shù)procedure MERGE1(q, r, p)global n, A(1:n), LINK(0:n); int i, j

38、, k;i q; j r; k 0;while (i 0 and j 0) do if (A(i) A(j) then LINK(k)i;ki;iLINK(i); else LINK(k)j;kj;jLINK(j);if (i=0) then LINK(k)j; else LINK(k)i;pLINK(0);end MERGE1當(dāng)當(dāng)q和和r非空時進(jìn)行以下非空時進(jìn)行以下操作操作: 加入一個關(guān)鍵字加入一個關(guān)鍵字的下標(biāo)到的下標(biāo)到LINK數(shù)組中數(shù)組中處理剩下的關(guān)鍵字處理剩下的關(guān)鍵字4.4 歸并分類歸并分類48(1) (2) (3) (4)(5)(6)(7) (8)5010253015703555數(shù)組數(shù)

39、組A:MSORT1(1, 8, p)if (8-1+15 ) then ISTSORT(A,LINK,1,8,p);else mid= (1+8)/2=4 ; MSORT1(1, 4, q); MSORT1(5, 8, r); MERGE1(q, r, p);end MSORT1 MSORT1(1, 4, q)if (4-1+15 ) then ISTSORT(A,LINK,1,4,p);end MSORT1 返回返回q=2MSORT1(5, 8, r)if (8-5+15 ) then ISTSORT(A,LINK,5,8,p);end MSORT1 返回返回r=5MERGE1(2,5,p)

40、;(0) (1) (2) (3) (4)(5)(6)(7) (8)000000000數(shù)組數(shù)組LINK:034170864.4 歸并分類歸并分類2 549(0)(1)(2)(3)(4)(5)(6)(7)(8)003417086數(shù)組數(shù)組LINK:MERGE1(2, 5, p)i=2; j=5; k=0;while (i 0 and j 0) do if (A(2) A(5) then LINK(0)=2; k=2; i=LINK(2)=3; 2534718(1) (2) (3) (4)(5)(6)(7) (8)5010253015703555if (A(3) A(5) else LINK(2)=5

41、; k=5; j=7; if (A(3) A(7) then LINK(5)=3; k=3; i=4; if (A(4) A(7) then LINK(3)=4; k=4; i=1; if (A(1) A(7) else LINK(4)=7; k=7; j=8; if (A(1) A(8) then LINK(7)=1; k=1; i=0; if (i=0) then LINK(1)=8;p=LINK(0)=2;4.4 歸并分類歸并分類504.4 歸并分類歸并分類討論：討論：1. 可以消去遞歸，取消棧的使用，例如：可以消去遞歸，取消棧的使用，例如： 采用由底向上的方法，將元素兩兩配對；采用由底

42、向上的方法，將元素兩兩配對； 自然合并排序法；自然合并排序法；2. 空間代價空間代價3. 適合于并行計(jì)算，采用并行或?qū)Ｓ眉呻娐穼?shí)現(xiàn)數(shù)據(jù)排序適合于并行計(jì)算，采用并行或?qū)Ｓ眉呻娐穼?shí)現(xiàn)數(shù)據(jù)排序操作時，派生出許多算法，例如奇偶合并排序，雙調(diào)合并操作時，派生出許多算法，例如奇偶合并排序，雙調(diào)合并排序等。排序等。(1) (2) (3) (4)(5)(6)(7)(8)501025301570355551(1) (2) (3) (4)(5)(6)(7) (8)5010253015703555(1)50(2)(3)(4)102530(5)(6)1570(7)(8)3555(1) (2) (3)(4)1025

43、3050(5)(6)(7) (8)15355570(1) (2) (3) (4)(5)(6)(7) (8)1015253035505570首先首先 對數(shù)組對數(shù)組A進(jìn)行進(jìn)行一遍掃描一遍掃描, 找出所有找出所有已排序的子數(shù)組段已排序的子數(shù)組段然后將相鄰的子數(shù)然后將相鄰的子數(shù)組段兩兩合并組段兩兩合并, 重復(fù)重復(fù)這種合并過程這種合并過程, 直到直到整個數(shù)組排好序整個數(shù)組排好序4.4 歸并分類歸并分類52 任何以關(guān)鍵字比較為基礎(chǔ)的分類算法，最壞情況任何以關(guān)鍵字比較為基礎(chǔ)的分類算法，最壞情況下的時間下界都是下的時間下界都是 (nlogn)，因此從數(shù)量級的角度上因此從數(shù)量級的角度上看看, 歸并分類是歸并分類

44、是最壞情況下的最優(yōu)算法最壞情況下的最優(yōu)算法。采用二元比較樹證明采用二元比較樹證明以比較為基礎(chǔ)分類的時間下界以比較為基礎(chǔ)分類的時間下界4.4 歸并分類歸并分類53對對3個關(guān)鍵字分類的二元比較樹個關(guān)鍵字分類的二元比較樹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)A(2)A(3)A(1)A(3)表示一表示一次比較次比較一種可能的一種可能的分類序列分類序列54 2T(n) 葉結(jié)點(diǎn)實(shí)際數(shù)葉結(jié)點(diǎn)實(shí)際數(shù) n!滿二叉樹滿二叉樹 n關(guān)鍵詞全排列關(guān)鍵詞全排列n1時，時，n! (n/2) n/2n 4有，有，T(n) (n

45、/2)log (n/2) (n/4)log nT(n) = (n log n)最壞情況下比較次數(shù)最壞情況下比較次數(shù)=比較樹的最長路徑比較樹的最長路徑=根到最遠(yuǎn)葉結(jié)點(diǎn)距離根到最遠(yuǎn)葉結(jié)點(diǎn)距離=樹高樹高T(n)4.4 歸并分類歸并分類554.5 快速分類快速分類快速分類的基本思想：快速分類的基本思想：選取數(shù)組選取數(shù)組A中的某個元素中的某個元素 t=As，然后將其他元素，然后將其他元素 重新排列，使重新排列，使A中所有在中所有在t以前出現(xiàn)的元素都小于以前出現(xiàn)的元素都小于或等于或等于t，而在，而在t之后出現(xiàn)的元素都大于或等于之后出現(xiàn)的元素都大于或等于t。這這個重新整理的過程稱為劃分，個重新整理的過程稱為

46、劃分，t稱為劃分元素。稱為劃分元素。A1A2As-1AsAs+1An劃分元素劃分元素t經(jīng)過一次經(jīng)過一次劃分后劃分后A1A2AjtAkAn每個元素都小于或等于每個元素都小于或等于t每個元素都大于或等于每個元素都大于或等于t564.5 快速分類快速分類快速分類實(shí)例快速分類實(shí)例A1A2A3A4A5A6A75392718 第第1次劃分，選次劃分，選t=A1，即，即t=5，劃分后得到如下結(jié)果：，劃分后得到如下結(jié)果： A1A2A3A4A5A6A72315798 第第2次劃分，選次劃分，選t=A1，即，即t=2，劃分后結(jié)果：，劃分后結(jié)果： A1A2A3A4A5A6A71235798 第第3次劃分，選次劃分，

47、選t=A5，即，即t=7，劃分后沒有變化，劃分后沒有變化 第第4次劃分，選次劃分，選t=A6，即，即t=9，劃分后結(jié)果：，劃分后結(jié)果： A1A2A3A4A5A6A71235798A1A2A3A4A5A6A71235789574.5 快速分類快速分類procedure QUICKSORT(low,high)int low,high; global n, A(1:n)if lowhigh then jhigh+1 call PARTITION(low, j) call QUICKSORT(low, j-1) call QUICKSORT(j+1, high) endifend QUICKSORT快

48、速分類算法快速分類算法劃分劃分A(low,high), 函數(shù)執(zhí)函數(shù)執(zhí)行完后行完后, j返回劃分元素返回劃分元素的下標(biāo)的下標(biāo)遞歸調(diào)用劃遞歸調(diào)用劃分之后得到分之后得到的兩個集合的兩個集合584.5 快速分類快速分類PARTITION劃分過程的實(shí)現(xiàn)劃分過程的實(shí)現(xiàn)procedure PARTITION(m, p)int m,p,i; global A(m:p-1)vAm; im;loop loop ii+1 until Aiv ; loop pp- -1 until Apv ; if (ip) then call INTERCHANGE(Ai, Ap) else exitrepeatAmAp; Apv

49、;end PARTITION交換交換Ai和和Ap結(jié)束過程時結(jié)束過程時, 參數(shù)參數(shù)p中的值為劃分元中的值為劃分元素所在位置的下標(biāo)素所在位置的下標(biāo), 該值將帶回該值將帶回, 用用于后面的于后面的QUICKSORT過程過程i從左向右移，直到從左向右移，直到Ai t p從右向左移，直到從右向左移，直到Apt59首先調(diào)用首先調(diào)用QUICKSORT(1,7) /low=1,high=7if 17 then j=8; call PARTITION(1, 8); call QUICKSORT(low, j-1) call QUICKSORT(j+1, high) end QUICKSORT4.5 快速分類快速

50、分類快速分類實(shí)例分析過程快速分類實(shí)例分析過程等等PARTITION(1, 8)調(diào)調(diào)用結(jié)束后用結(jié)束后,返回參數(shù)返回參數(shù)j的的值值,才能執(zhí)行遞歸調(diào)用才能執(zhí)行遞歸調(diào)用PARTITION(m, p) /m=1, p=8t=Am=5; i=m=1;loop(第第1次次) loop i+ until Ait ; i=3 loop p- until Apt ; p=6 if (ip) then Ai Ap; A1 A2 A3 A4A5A6A75392718A1 A2 A3 A4A5A6A75312798604.5 快速分類快速分類Am=Ap; 即即A1=A4=2Ap=t; 即即A4=5end / p=4的值

51、帶回的值帶回loop(第第2次次,i=3,p=6) loop i+ until Ait ; i=5 loop p- until Apt ; p=4 if (i p) 執(zhí)行執(zhí)行else exit loop1 A1 A2 A3 A4A5A6A75312798A1A2A3A4A5A6A72315798遞歸調(diào)用遞歸調(diào)用QUICKSORT(low, j-1) 即即QUICKSORT(1, 3)遞歸調(diào)用遞歸調(diào)用QUICKSORT(j+1,high) 即即QUICKSORT(5, 7)61快速分類算法的分析快速分類算法的分析 I ：時間復(fù)雜性時間復(fù)雜性假設(shè)前提假設(shè)前提互不相同；隨機(jī)選取劃分元素互不相同；隨機(jī)

52、選取劃分元素劃分單元隨機(jī)選取的改進(jìn)劃分單元隨機(jī)選取的改進(jìn)快速分類的性能取決于劃分的對稱性！快速分類的性能取決于劃分的對稱性！隨機(jī)選取更合理，因?yàn)樽詈媚苷业街虚g元素隨機(jī)選取更合理，因?yàn)樽詈媚苷业街虚g元素最壞情況下：最壞情況下：劃分算法比較次數(shù)為元素?cái)?shù)劃分算法比較次數(shù)為元素?cái)?shù):p-m+1:p-m+1第第i i級的比較次數(shù)：級的比較次數(shù)：n-i+1 (n-i+1 (實(shí)際上是固定的實(shí)際上是固定的) )最壞情況下級數(shù)為最壞情況下級數(shù)為n-1(n-1(每次取最小或最大值）每次取最小或最大值） 總和：總和：n+(n-1)+= O(nn+(n-1)+= O(n2 2) )平均情況下：平均情況下：劃分元素最終位置機(jī)會均等，劃分元素最終位置機(jī)會均等，運(yùn)用概率公式得：運(yùn)用概率公式得：62 快速分類算法的分析快速分類算法的分析 II ：?？臻g使用：棧空間使用遞歸算法：最壞情況下遞歸算法：最壞情況下 O(n) O(n) 改進(jìn)的迭代算法：改進(jìn)的迭代算法：每次選擇小的文件繼續(xù)處理每次選擇小的文件繼續(xù)處理（較小的文件在處理過程中相對迭代次數(shù)少，可能（較小的文件在處理過程中相對迭代次數(shù)少，