算法第四章課件

1、4.1 一般方法4.2 二分檢索4.3 找最大和最小元素4.4 歸并分類4.5 快速分類4.6 選擇問題4.7 斯特拉森矩陣乘法第四章 分治法4.1 一般方法分治法的思想: 將一個(gè)輸入規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同，然后遞歸的求解這些子問題，最后用適當(dāng)?shù)姆椒▽⒏髯訂栴}的解合并成原問題的解。問題(N個(gè)輸入)子問題1子問題2子問題K子問題1子問題2子問題k相同類型合并解分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。步驟：分（devide）二分為主多分比二分更好嗎？ 治（conquar）遞歸調(diào)用，當(dāng)規(guī)

2、模足夠小時(shí)直接處理 組（combine）分治法問題特征：問題規(guī)模小到一定的程度就非常容易解決所有問題的共性特征2) 問題可分解為若干個(gè)規(guī)模較小的同類問題遞歸策略 分3) 子問題的解可以合并為該問題的解若不具備，可用貪心或動(dòng)態(tài)規(guī)劃4) 子問題是相互獨(dú)立的保證采用分治法效率高，否則更適合采用動(dòng)態(tài)規(guī)劃分治策略DANDC的抽象化控制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) return(COMBINE( DANDC(p,m

3、), DANDC(m+1,q)endifend DANDC判斷輸入規(guī)模q-p+1是否足夠小,可直接求解G是求解該規(guī)模問題的函數(shù)分割函數(shù), pmq, 原問題被分為A(p:m)和A(m+1:q)兩個(gè)子問題合并函數(shù),將兩個(gè)子問題的解合并為原問題的解原問題為A(1:n) , 最初調(diào)用函數(shù)應(yīng)該是DANCE(1,n); DANDC(p,q)是計(jì)算A(p:q)子問題的解4.1 一般方法k分法的復(fù)雜性分析一個(gè)分治法將規(guī)模為n的問題分成k個(gè)規(guī)模為nm的子問題去解。設(shè)分解閾值n0=1，且解規(guī)模為1的問題耗費(fèi)1個(gè)單位時(shí)間。再設(shè)將原問題分解為k個(gè)子問題以及將k個(gè)子問題的解合并為原問題的解需用f(n)個(gè)單位時(shí)間。用T(

4、n)表示該分治法解規(guī)模為|P|=n的問題所需的計(jì)算時(shí)間，則有：通過迭代法求得方程的解：注意：遞歸方程及其解只給出n等于m的方冪時(shí)T(n)的值，但是如果認(rèn)為T(n)足夠平滑，那么由n等于m的方冪時(shí)T(n)的值可以估計(jì)T(n)的增長速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)minmi+1時(shí)，T(mi)T(n)T(mi+1)。 procedure BINSRCH(A, n, x, j) int low, high, mid, j, n; low1; highn; while （low=high） do mid(low+high)/2; /*取中間值*/ case xAmid: lowmid+1 /*

5、尋找后一半*/ else: jmid; return; /*檢索成功, 結(jié)束*/ endcase repeat j0; /*檢索失敗*/end BINSRCH二分檢索算法檢索x=9, 9=A5, 一次比較就成功, 最好情況-15-6079235482101A1 A2 A3 A4 A5 A6 A7 A8 A9檢索x=-15, -15A5, -15A5, 101A7, 101A8, 101= A9, 4次比較, 成功檢索x=8, 8A2, 8A3, 8A4, 4次比較, 不成功檢索二分檢索實(shí)例:設(shè)在A(1:9)中順序放了以下9個(gè)元素：用五個(gè)特性判斷是否是一個(gè)算法根據(jù)算法的描述，滿足五個(gè)特性，是算法

6、證明算法是否正確如果n=0，則不進(jìn)入循環(huán)，j=0，算法終止否則就會進(jìn)入循環(huán)與數(shù)組A中的元素進(jìn)行比較如果x=Amid，則j=mid，檢索成功，算法終止否則，若xA(mid)，則縮小到A(mid+1)和A(n)之間檢索按上述方式縮小檢索區(qū)總可以在有限步內(nèi)使lowhigh如果出現(xiàn)這種情況，說明x不在A中，j=0，算法終止二分檢索算法正確性證明：-15-6079235482101A1 A2 A3 A4 A5 A6 A7 A8 A93234132343334433344成功檢索有n種情況，不成功檢索有n+1種情況成功：不成功：不論檢索是否成功，算法的執(zhí)行過程都是x與一系列中間元素Amid的比較過程，我們

7、可以用一棵二元比較樹來描述算法的執(zhí)行過程二元比較樹內(nèi)結(jié)點(diǎn)表示一次元素的比較,存放一個(gè)mid值外結(jié)點(diǎn)表示不成功檢索的一種情況592-61-1530754476238829101一條路徑表示一個(gè)元素的比較序列4.2 二分檢索Notes: E=I+2n 的證明1.在 n=1 時(shí)顯然成立2.設(shè) 內(nèi)節(jié)點(diǎn)為 n-1 時(shí)成立，3. 內(nèi)節(jié)點(diǎn)為 n 時(shí) 把最遠(yuǎn)的內(nèi)節(jié)點(diǎn)（i級）拿掉，替換為一個(gè)外節(jié)點(diǎn)E=E 2i +(i-1) = E i - 1 I=I (i-1) E=I+2n-2= E=E+i+1= I+2n-1+i = I (i-1) +2n-1+i=I+2n成功檢索平均比較數(shù) S(n) = I/n+1不成功

8、檢索平均比較數(shù) U(n) = E/(n+1)推導(dǎo)得：S(n)=(1+1/n)U (n)-1S(n)=(logn) 關(guān)于確切比較次數(shù)的討論：BINSRCH的一次比較假設(shè)不合理，是為了降低分析復(fù)雜度的權(quán)宜之計(jì)，但對近似表示無影響實(shí)際上應(yīng)該用（*）替代BINSRCH相應(yīng)語句每次循環(huán)固定一次比較的BINSRCH1算法的提出對于成功檢索：最好最壞平均BINSRCH 1 log(n)log(n)BINSRCH(*) 22 log(n)1.5 log(n)BINSRCH1log(n)+1log(n)+1 log(n)+1以比較為基礎(chǔ)檢索的時(shí)間下界思考: 對于已排序的n個(gè)元素, 檢索某元素x是否出現(xiàn), 是否存

9、在以比較為基礎(chǔ)的檢索算法, 在最壞情況下該算法的計(jì)算時(shí)間比二分檢索算法的計(jì)算時(shí)間更低對于以比較為基礎(chǔ)的檢索算法的分析，采取構(gòu)建二元比較樹的方式。二元比較樹-順序檢索有n個(gè)如下關(guān)系的元素:A(1)A(2)A(n),檢索一給定元素X是否在A中出現(xiàn)X:A(1)X:A(2)X:A(n)不成功不成功不成功不成功線性檢索以比較為基礎(chǔ)檢索的時(shí)間下界定理4.3: 設(shè)A(1:n)含有n(n1)各不同的元素，排序?yàn)锳(1)A(2)max then max Ai; if Aimax then max=Ai;else if Aimin then min=Ai;直接算法的時(shí)間復(fù)雜度在最好、最壞、平均情況下均為2(n-1

10、)改進(jìn)后的計(jì)算時(shí)間:(元素升序)最好情況為(n-1)(元素降序)最壞情況為2(n-1)平均情況為3/2(n-1)改進(jìn)采用分治策略求最大最小元素I=(n,A(1),A(n)劃分為I1=( n/2 ,A(1),A( n/2 ) )I2=( n-n/2 ,A( n/2 +1 ),A(n) )結(jié)果的合并分治法求最大和最小元素procedure MAXMIN( i, j, fmax, fmin)int i, j; global n, A(1:n);case i= j: fmax fmin Ai i= j-1: if Ai24.3 找最大和最小元素可以證明: 任何一種以比較為基礎(chǔ)的找最大和最小元素的算法，

11、其元素比較次數(shù)的下界為 3n/2 -2但是不代表該算法最優(yōu)，理由如下：MAXMIN算法分析MAXMIN所需的存儲空間比直接算法多4.3 找最大和最小元素給出n個(gè)元素，則MAXMIN算法有 logn +1級的遞歸，每次遞歸都需要保存i, j, fmax, fmin和返回地址5個(gè)值直接算法需要空間為: n+3, 用n個(gè)位置存放數(shù)組A，還有i, max, min三個(gè)變量需要存儲元素A(i)和A(j)的比較與i和j的比較時(shí)間相差不大時(shí)，過程MAXMIN不可取。 設(shè)MAXMIN的頻率計(jì)數(shù)為C(n)，n=2k , k為整數(shù), 當(dāng)n2時(shí), 有: C(n)=5n/2-3 4.3 找最大和最小元素C(n)= 2

12、C(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 n2直接算法的比較次數(shù)為2(n-1), 加上實(shí)現(xiàn)for循環(huán) 需要的比較次數(shù), 則為3(n-1), 雖然3(n-1)略大于 5n/2-3, 但MAXMIN算法還有遞歸所帶來的時(shí)間 開銷, 這種情況下直接算法要快一些結(jié)論: 如果數(shù)組A的元素之間的比較遠(yuǎn)比整型變量的比較代價(jià)昂貴，分治算法略優(yōu)于直接比較算法。4.3 找最大和最小元素一般

13、方法(插入法)For j2 to n do將A(j)放入已分類A(1:j-1)4.4 歸并分類問題描述: 給定一個(gè)含有n個(gè)元素的集合， 把它們按一定的次序分類(如非降次序)procedure INSERTIONSORT(A, n)A0 -;for j 2 to n do item Aj; i j-1; while ( itemAi) do Ai+1 Ai; i i-1; Ai+1 item; end INSERTIONSORT插入分類算法描述數(shù)組元素的移動(dòng)插入排好序的值可能執(zhí)行0j次(j=2,3n)最好情況(n)最壞情況的計(jì)算時(shí)間：2+n=(n(n+1)/2)-1=(n2)用item保存當(dāng)前元

14、素值4.4 歸并分類4.4 歸并分類A0A1A2A3A4A5-639413639449, A4=A3; 936, 不用移動(dòng)11-, A1=343, A2=416, A4=A3;14, A3=A2;1-, A1=1注：加一個(gè)元素A0從元素A2開始比較分：平均分為2個(gè)子集合治：遞歸調(diào)用分類算法，將2個(gè)子集合分類組：將2個(gè)分類的子集合并為一個(gè)分類集合4.4 歸并分類分治策略設(shè)計(jì)歸并分類算法A1A2A3A4A563941A1A2A3639A4A541A1A263A393636914A16A23A44A51分治策略設(shè)計(jì)歸并排序算法134694.4 歸并分類遞歸調(diào)用，分別對分解出來的兩個(gè)子問題排序合并兩個(gè)

15、已排好的序列，得到原問題的解歸并排序算法描述Procedure MERGESORT(low,high)int low, high, mid;if (lowmid) then for kj to high do BiAk;ii+1 else for kh to mid do BiAk;ii+1 for k low to high do Ak Bk;end MERGE處理兩個(gè)已分類的序列剩余元素處理過程將已分類的集合復(fù)制到A數(shù)組4.4 歸并分類A1A2A3A4A563941low=1; mid=1; high=2; h=1; i=1; j=2; while (hmid and jhigh) do

16、if A1 A2 then else B1=A2; j=j+1=3 i=i+1=2; B1B2B3B4B53636if (hmid) then else for k=1 to 1 do B2=A1; i=i+1=3; for k=1 to 2 do Ak=Bk; 4.4 歸并分類low=1; mid=2; high=3; h=1; i=1; j=3; while (hmid and jhigh) do if A1 A3 then B1=A1; h=h+1=2 i=i+1=2; if A2 A3 then B2=A2; h=h+1=3 i=i+1=3; if (hmid) then for k=

17、3 to 3 do B3=A3; i=i+1=4 for k=1 to 3 do Ak=Bk;A1A2A3A4A536941B1B2B3B4B5363693694.4 歸并分類low=4; mid=4; high=5; h=4; i=4; j=5; while (hmid and jhigh) do if A4 A5 then else B4=A5; j=j+1=6 i=i+1=5; for k=4 to 5 do Ak=Bk; if (hmid) then else for k=4 to 4 do B5=A4; i=i+1=6; A1A2A3A4A536941B1B2B3B4B5369141

18、44.4 歸并分類low=1; mid=3; high=5; h=1; i=1; j=4; while (hmid and jhigh) do if A1 A4 then else B1=A4; j=j+1=5 i=i+1=2; if (hmid) then else for k=2 to 3 do B4=A2; i=i+1=5 for k=1 to 5 do Ak=Bk; B5=A3; i=i+1=6 if A2 A5 then else B3=A5; j=j+1=6 i=i+1=4; if A1 A5 then B2=A1; h=h+1=2 i=i+1=3; A1A2A3A4A536914

19、B1B2B3B4B53691413469134694.4 歸并分類歸并分類的計(jì)算時(shí)間T(n)=a n=1 , a是常數(shù)(a=0)2T(n/2)+cn n1 , c是常數(shù)當(dāng) n=2k時(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，有T(n)T(2k+1)則有T(n)=O(nlogn)歸并2個(gè)子數(shù)組所需的元素比較次數(shù)在n/2到n-1之間4.4 歸并分類歸并分類算法的缺點(diǎn)缺點(diǎn)1: 當(dāng)子集合的元素很少時(shí)，算法的很多時(shí)間消耗

20、 在了遞歸的處理上。改進(jìn): 當(dāng)子集合的元素個(gè)數(shù)適當(dāng)少時(shí)，采用在小規(guī)模 集合上能有效工作的插入分類算法克服上述缺點(diǎn) 帶來的時(shí)間消耗。缺點(diǎn)2: 輔助數(shù)組B的使用增加了算法的空間，且每次 調(diào)用MERGE時(shí)，都得將B中的結(jié)果復(fù)制到A中，消耗了一部分時(shí)間。改進(jìn): 用一個(gè)鏈接數(shù)組LINK(1:n)代替B，LINK中的 元素為A中元素的指針，它指向下一個(gè)元素所在 的下標(biāo)位置。4.4 歸并分類關(guān)于LINK數(shù)組LINK(1:n)為一鏈接數(shù)組，取值范圍為1, 2, , n。可看成是A元素的指針，在分類表中它指向下一個(gè)元素所在的下標(biāo)位置，用0表示結(jié)束。實(shí)例: 下面是一個(gè)LINK集合，包含了兩個(gè)已分類的 子集合。q和

21、r表示兩個(gè)子集合的起始處:q=2,r=51234567803417086q=2的表為(2, 3, 4, 1) A2A3A4A1r=5的表為(5, 7, 8, 6) A5A7A8A6123456785010253015703555數(shù)組A:數(shù)組LINK:4.4 歸并分類procedure 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)/2 ; call MERGE

22、SORT1(low, mid, q); call MERGESORT1(mid+1, high, r); call MERGE1(q, r, p); end MEGESORT1改進(jìn)的歸并分類算法當(dāng)集合元素小于16時(shí), 調(diào)用修改的插入分類算法歸并分類遞歸調(diào)用合并兩個(gè)子問題的解4.4 歸并分類使用LINK數(shù)組的歸并函數(shù)procedure MERGE1(q, r, p)global n, A(1:n), LINK(0:n); int i, j, k;i q; j r; k 0;while (i0 and j0) do if (AiAj) then LINKki;ki;iLINKi; else LIN

23、Kkj;kj;jLINKj;if (i=0) then LINKkj; else LINKki;p LINK0;end MERGE1當(dāng)q和r非空時(shí)進(jìn)行以下操作: 加入一個(gè)關(guān)鍵字的下標(biāo)到LINK數(shù)組中處理剩下的關(guān)鍵字4.4 歸并分類123456785010253015703555數(shù)組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, p)if

24、(4-1+15 ) then ISTSORT(A,LINK,1,4,p);end MSORT1 返回p=2MSORT1(5, 8, p)if (8-5+15 ) then ISTSORT(A,LINK,5,8,p);end MSORT1 返回p=5MERGE1(2,5,p);012345678000000000數(shù)組LINK:034170864.4 歸并分類012345678003417086數(shù)組LINK:MERGE1(2, 5, p)i=2; j=5; k=0;while (i0 and j0) do if (A2A5) then LINK0=2; k=2; i=3; 253471812345

25、6785010253015703555if (A3A5) else LINK2=5; k=5; j=7; if (A3A7) then LINK5=3; k=3; i=4; if (A4A7) then LINK3=4; k=4; i=1; if (A1A7) else LINK4=7; k=7; j=8; if (A1A8) then LINK7=1; k=1; i=0; if (i=0) then LINK1=8;p=LINK0=2;4.4 歸并分類取消棧使用自然合并排序算法思想12345678501025301570355515023410253056157078355512341025

26、3050567815355570123456781015253035505570首先 對數(shù)組A進(jìn)行一遍掃描, 找出所有已排好序的子數(shù)組段然后將相鄰的子數(shù)組段兩兩合并, 重復(fù)這種合并過程, 直到整個(gè)數(shù)組排好序4.4 歸并分類 任何以關(guān)鍵字比較為基礎(chǔ)的分類算法，最壞情況下的時(shí)間下界都是(nlogn)，因此從數(shù)量級的角度上看, 歸并算法是最壞情況下的最優(yōu)算法。采用二元比較樹證明之以比較為基礎(chǔ)分類的時(shí)間下界4.4 歸并分類對3個(gè)關(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)

27、A(1)A(3)表示一次比較一種可能的分類序列4.4 歸并分類分類算法的二元比較樹：內(nèi)節(jié)點(diǎn)表示關(guān)鍵詞的一次比較葉節(jié)點(diǎn)表示分類的一種可能結(jié)果2T(n)葉結(jié)點(diǎn)實(shí)際數(shù) n!滿二叉樹外節(jié)點(diǎn)數(shù) n!種可能的全排列2T(n)n! (n/2) n/2T(n) (n/2)log (n/2) (n/4)log nT(n) = (n log n)最壞情況下比較次數(shù)=比較樹的最長路徑=根到最遠(yuǎn)葉結(jié)點(diǎn)距離=樹高T(n)4.4 歸并分類4.5 快速分類快速分類的基本思想：選取數(shù)組A中的某個(gè)元素 t=As，然后將其他元素 重新排列，使A中所有在t以前出現(xiàn)的元素都小于或等于t，而在t之后出現(xiàn)的元素都大于或等于t。這個(gè)重新整

28、理的過程成為劃分，t稱為劃分元素。A1A2As-1AsAs+1An劃分元素t經(jīng)過一次劃分后A1A2AjtAkAn每個(gè)元素都小于或等于t每個(gè)元素都大于或等于t4.5 快速分類快速分類實(shí)例A1A2A3A4A5A6A75392718 第1次劃分，選t=A1，即t=5，劃分后得到如下結(jié)果： A1A2A3A4A5A6A72315798 第2次劃分，選t=A1，即t=2，劃分后結(jié)果： A1A2A3A4A5A6A71235798 第3次劃分，選t=A5，即t=7，劃分后沒有變化 第4次劃分，選t=A6，即t=9，劃分后結(jié)果： A1A2A3A4A5A6A71235798A1A2A3A4A5A6A7123578

29、94.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快速分類算法劃分A(low,high), 函數(shù)執(zhí)行完后, j返回劃分元素的下標(biāo)遞歸調(diào)用劃分之后得到的兩個(gè)集合4.5 快速分類PARTITION劃分過程的實(shí)現(xiàn)procedure PARTITION(m, p)int m,p,i; gl

30、obal 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;end PARTITION交換Ai和Ap結(jié)束過程時(shí), 參數(shù)p中的值為劃分元素所在位置的下標(biāo), 該值將帶回, 用于后面的QUICKSORT過程i從左向右移，直到Ai t p從右向左移，直到Apt首先調(diào)用QUICKSORT(1,7) /low=1,high=7if 17 then j=8; call PARTITION(1, 8); c

31、all QUICKSORT(low, j-1) call QUICKSORT(j+1, high) end QUICKSORT4.5 快速分類快速分類實(shí)例分析過程等PARTITION(1, 8)調(diào)用結(jié)束后,返回參數(shù)j的值,才能執(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 (i0時(shí)，將2k2k棋盤分割為4個(gè)2k-12k-1 子棋盤(a)所示。特殊方格必位于4個(gè)較小子棋盤之一中，其余3個(gè)子棋盤中無特殊方格。為了將這3個(gè)無特殊方格的子棋

32、盤轉(zhuǎn)化為特殊棋盤，可以用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤的會合處，如 (b)所示，從而將原問題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為棋盤11。 2k-12k-1 2k2k用到的骨牌數(shù)為（ 4k -1）/3tr棋盤左上角方格的行號,tc棋盤左上角方格的列號dr特殊方格所在的行號,tc特殊方格所在的列號void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌號 s = size/2; / 分割棋盤 / 覆蓋左上角子棋盤 if (dr tr + s