計(jì)算機(jī)算法設(shè)計(jì)與分析課件：第二章 分治法

1、第二章 分治法 2.1 一般方法 一、面向的問(wèn)題類(lèi)：一個(gè)問(wèn)題的輸入規(guī)模較大，直接求解較困難或無(wú)法直接求出。 二、分治法方法：將n個(gè)輸入分成k個(gè)不同子集合，如果可以將這k子問(wèn)題獨(dú)立求解，并且在求出了這些子問(wèn)題的解之后，還可以有合適的方法把它們合并成整個(gè)問(wèn)題的解。這種方法就是分治法。由分治法所得到的子問(wèn)題與原問(wèn)題具有相同的類(lèi)型。如果得到的子問(wèn)題相對(duì)來(lái)說(shuō)還太大，則可反復(fù)使用分治策略將這些子問(wèn)題分成更小的同類(lèi)的子問(wèn)題，直至產(chǎn)生出不用進(jìn)一步細(xì)分就可求解的子問(wèn)題。 三、分治法三個(gè)步驟 劃分（divide）：將原問(wèn)題分解成一系列原問(wèn)題的子問(wèn)題。 解決（conquer）:解各子問(wèn)題。（若子問(wèn)題足夠小，則可直接

2、求解） 合并（combine）:將子問(wèn)題的結(jié)果合并成原問(wèn)題的解。 分治法的關(guān)鍵在尋找恰當(dāng)?shù)暮喜⒎椒ā?四、分治策略的抽象化控制過(guò)程 Divide-and-Conquer(P) 1. if |P|n0 2. then return(ADHOC(P) 3. 將P分解為較小的子問(wèn)題 P1 ,P2 ,.,Pk 4. for i1 to k 5. do yi Divide-and-Conquer(Pi) 遞歸解決Pi 6. T MERGE(y1,y2,.,yk) 合并子問(wèn)題 7. return(T)其中|P|表示問(wèn)題P的規(guī)模；n0為一閾值，表示當(dāng)問(wèn)題P的規(guī)模不超過(guò)n0時(shí)，問(wèn)題已容易直接解出，不必再繼續(xù)分

3、解。ADHOC(P)是該分治法中的基本子算法，用于直接解小規(guī)模的問(wèn)題P。因此，當(dāng)P的規(guī)模不超過(guò)n0時(shí)，直接用算法ADHOC(P)求解。算法MERGE(y1,y2,.,yk)是該分治法中的合并子算法，用于將P的子問(wèn)題P1 ,P2 ,.,Pk 的相應(yīng)的解y1,y2,.,yk合并為P的解。書(shū)中分治策略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), D

4、ANDC(m+1,q)endifend DANDC判斷輸入規(guī)模q-p+1是否足夠小,可直接求解G是求解該規(guī)模問(wèn)題的函數(shù)分割函數(shù), pmq, 原問(wèn)題被分為A(p:m)和A(m+1:q)兩個(gè)子問(wèn)題合并函數(shù),將兩個(gè)子問(wèn)題的解合并為原問(wèn)題的解原問(wèn)題為A(1:n) , 最初調(diào)用函數(shù)應(yīng)該是DANDC(1,n); DANDC(p,q)是計(jì)算A(p:q)子問(wèn)題的解2分策略DANDC的計(jì)算時(shí)間倘若所分成的兩個(gè)子問(wèn)題的輸入規(guī)模大致相等,則分治策略DANDC的計(jì)算時(shí)間可表示為：說(shuō)明：T(n)是輸入規(guī)模為n的分治策略的計(jì)算時(shí)間g(n)是對(duì)足夠小的輸入規(guī)模能直接計(jì)算出答案的時(shí)間f(n)是COMBINE函數(shù)合成原問(wèn)題解的

5、計(jì)算時(shí)間g(n)n足夠小2T(n/2)+f(n)否則T(n)=k分法的復(fù)雜性分析一個(gè)分治法將規(guī)模為n的問(wèn)題分成k個(gè)規(guī)模為nm的子問(wèn)題去解。設(shè)分解閾值n0=1，且解規(guī)模為1的問(wèn)題耗費(fèi)1個(gè)單位時(shí)間。再設(shè)將原問(wèn)題分解為k個(gè)子問(wèn)題以及將k個(gè)子問(wèn)題的解合并為原問(wèn)題的解需用f(n)個(gè)單位時(shí)間。用T(n)表示該分治法解規(guī)模為|P|=n的問(wèn)題所需的計(jì)算時(shí)間，則有：通過(guò)迭代法求得方程的解： 注意：遞歸方程及其解只給出n等于m的方冪時(shí)T(n)的值，但是如果認(rèn)為T(mén)(n)足夠平滑，那么由n等于m的方冪時(shí)T(n)的值可以估計(jì)T(n)的增長(zhǎng)速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)minmi+1時(shí)，T(mi)T(n)T(

6、mi+1)。 2.2 二分檢索一、問(wèn)題描述 已知一個(gè)按非降序排列的順序表有n個(gè)元素，要求判定某個(gè)給定的元素x是否在該表中出現(xiàn)。若出現(xiàn)，找出在表中位置，否則返回0. 二、二分檢索方法 1.問(wèn)題形式化 設(shè)該問(wèn)題為I（n,a1,an,x） 2.選取下標(biāo)k，使用分治策略將I分解為三個(gè)子問(wèn)題： I1（ k-1,a1,ak-1,x） I2（1,ak,x） I3（n-k,ak+1,an,x ） 3.根據(jù)ak與x的關(guān)系，或問(wèn)題可得解，或?qū)1或I3繼續(xù)進(jìn)行分治。I（n,a1,an,x）procedure BINSRCH(A, n, x, j) integer low, high, mid, j, n; low

7、1; highn while lowhigh do mid /*取中間值*/ case :xA(mid): lowmid+1 /*尋找后一半*/ : else: jmid; return; /*檢索成功, 結(jié)束*/ endcase repeat j0 /*檢索失敗*/end BINSRCH三、二分檢索算法low+(high-low)檢索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

8、, 8A3, 8A4, 4次比較, 不成功檢索二分檢索實(shí)例:設(shè)在A(1:9)中順序放了以下9個(gè)元素：用五個(gè)特性判斷是否是一個(gè)算法根據(jù)算法的描述，滿(mǎn)足五個(gè)特性，是算法說(shuō)明算法是否正確如果n=0，則不進(jìn)入循環(huán)，j=0，算法終止否則就會(huì)進(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)這種情況，說(shuō)明x不在A中，j=0，算法終止四、二分檢索算法正確性說(shuō)明：五、二分檢索算法所需的空間和時(shí)間所需空間: 用n個(gè)位置存放數(shù)組A，還有l(wèi)ow, high,

9、mid, x, j五個(gè) 變量需要存儲(chǔ)，共需空間 n+5所需計(jì)算時(shí)間: 對(duì)于計(jì)算時(shí)間，需要分別考慮以下幾種情況： 成功檢索的最好情況、平均情況、最壞情況 不成功檢索的最好情況、平均情況、最壞情況1、二元判定樹(shù) 2、二分法二元判定樹(shù)內(nèi)結(jié)點(diǎn)表示一次元素的比較,存放一個(gè)mid值外結(jié)點(diǎn)表示不成功檢索的一種情況592-61-1530754476238829101一條路徑表示一個(gè)元素的比較序列3、擴(kuò)展二叉樹(shù)與二叉判定樹(shù)4、E=I+2n 的證明E:外部路徑長(zhǎng)度 I：內(nèi)部路徑長(zhǎng)度 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級(jí)）拿掉，替換為一個(gè)外節(jié)點(diǎn)

10、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+2n5、檢索結(jié)果與判定樹(shù)的關(guān)系 最壞的成功檢索與不成功檢索的比較次數(shù)（定理4.2 p75）: 若n在區(qū)域2k-1, 2k)中，則對(duì)于一次成功的檢索，二分檢索算法至多作k次比較，而對(duì)于一次不成功的檢索，或者作k-1次比較或者作k次比較。6、在各種情況下成功檢索（ Imin的計(jì)算）和不成功檢索情況 六、以比較為基本操作的有序表檢索的最壞時(shí)間下界 定理4.3 p77: 設(shè)A(1:n)含有n(n1)各不同的元素，排序?yàn)锳(1)A(2)max

11、 then max Ai; if Aimax then max=Ai;else if Aimin then min=Ai;直接算法的時(shí)間復(fù)雜度在最好、最壞、平均情況下均為2(n-1)改進(jìn)后的計(jì)算時(shí)間:(元素升序)最好情況為(n-1)(元素降序)最壞情況為2(n-1)平均情況為3/2(n-1)改進(jìn)三、分治求取最大和最小元素procedure MAXMIN( i, j, fmax, fmin)int i, j; global n, A(1:n);case i= j: fmax fmin Ai i= j-1: if Ai2可以證明: 任何一種以比較為基礎(chǔ)的找最大和最小元素的算法，其元素比較次數(shù)的下界

12、為 3n/2 -2五、MAXMIN算法分析MAXMIN所需的存儲(chǔ)空間比直接算法多給出n個(gè)元素，則MAXMIN算法有 logn +1級(jí)的遞歸，每次遞歸都需要保存i, j, fmax, fmin和返回地址5個(gè)值直接算法需要空間為: n+3, 用n個(gè)位置存放數(shù)組A，還有i, max, min三個(gè)變量需要存儲(chǔ)元素A(i)和A(j)的比較與i和j的比較時(shí)間相差不大時(shí)，過(guò)程MAXMIN不可取。 設(shè)MAXMIN的時(shí)間復(fù)雜度為C(n)，n=2k , k為整數(shù), 當(dāng)n2時(shí), 有: C(n)=5n/2-3 C(n)= 2C(n/2)+3 = 2(2C(n/4)+3)+3 = 4C(n/4)+6+3 = 2k-1C

13、(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 2.4 歸并排序 一、簡(jiǎn)單排序算法回顧 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; repeat Ai+1 item repeatend INSERTIONSORT二、插入分類(lèi)算法及特點(diǎn)數(shù)組元素的移動(dòng)插入排好序的值可能執(zhí)行0j次(j=2,3n)最好情況(n)最壞

14、情況的計(jì)算時(shí)間：2+n=(n(n+1)/2)-1=(n2)用item保存當(dāng)前元素值遞歸調(diào)用，分別對(duì)分解出來(lái)的兩個(gè)子問(wèn)題排序合并兩個(gè)已排好的序列，得到原問(wèn)題的解三、歸并排序的分治思想及主算法描述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è)已分類(lèi)的序列剩余元素處理過(guò)程將已分類(lèi)的集合復(fù)制到A數(shù)組A1A2A3A4A563

15、941A1A2A3639A4A541A1A263A393636914A16A23A44A51五、歸并過(guò)程實(shí)例13469MRGESORT執(zhí)行過(guò)程1,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 的值六、歸并分類(lèi)的時(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 =

16、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之間 七、缺陷分析 當(dāng)分治遞歸到子集規(guī)模較小時(shí)系統(tǒng)開(kāi)銷(xiāo)過(guò)大； 使用了與待分類(lèi)元素所占空間相同的輔助空間， 并反復(fù)進(jìn)行了元素移動(dòng)。 八、針對(duì)性改進(jìn) 當(dāng)子集規(guī)模達(dá)到一定小程度時(shí)，不再進(jìn)行細(xì)分遞歸，改為直接的簡(jiǎn)單排序（插入排序）； 使用靜態(tài)的鏈接結(jié)構(gòu)存儲(chǔ)待分類(lèi)元素，減少空間的開(kāi)銷(xiāo)和元素移動(dòng)。 關(guān)于靜態(tài)數(shù)組LINKLINK(1:n)為一鏈接數(shù)組，取值范圍為1, 2, , n?？煽闯墒茿元素的指針，在分類(lèi)表中它

17、指向下一個(gè)元素所在的下標(biāo)位置，用0表示結(jié)束。實(shí)例: 下面是一個(gè)LINK集合，包含了兩個(gè)已分類(lèi)的 子集合。q和r表示兩個(gè)子集合的起始處:q=2,r=51234567803417086q=2的表為(2, 3, 4, 1) A2A3A4A1r=5的表為(5, 7, 8, 6) A5A7A8A6123456785010253015703555數(shù)組A:數(shù)組LINK:procedure MERGESORT1(low, high, p) global A(low:high), LINK(low:high) if (high-low+116 ) then call INSERTIONSORT(A, LINK,

18、 low, high, p); else mid(low+high)/2 ; call MERGESORT1(low, mid, q); call MERGESORT1(mid+1, high, r); call MERGE1(q, r, p); endifend MEGESORT1改進(jìn)的歸并分類(lèi)算法當(dāng)集合元素小于16時(shí), 調(diào)用修改的插入分類(lèi)算法歸并分類(lèi)遞歸調(diào)用合并兩個(gè)子問(wèn)題的解使用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 0while (i0 and j0)

19、 do if (AiAj) then LINKki;ki;iLINKi else LINKkj;kj;jLINKj endifrepeatif (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)鍵字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);

20、 MERGE1(q, r, p); end MSORT1 MSORT1(1, 4, p)if (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:03417086012345678003417086數(shù)組LINK:MERGE1(2, 5, p)i=2; j=5; k=0;while (i0 and j0) do if (A2A

21、5) then LINK0=2; k=2; i=3; 2534718123456785010253015703555if (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;變型方法-自然合并排序算法思想1234567850102530157035551

22、50234102530561570783555123410253050567815355570123456781015253035505570首先 對(duì)數(shù)組A進(jìn)行一遍掃描, 找出所有已排好序的子數(shù)組段然后將相鄰的子數(shù)組段兩兩合并, 重復(fù)這種合并過(guò)程, 直到整個(gè)數(shù)組排好序 九、比較類(lèi)分類(lèi)算法時(shí)間復(fù)雜度下界 比較類(lèi)排序算法過(guò)程=二叉判定樹(shù)模型 使用基本操作比較=構(gòu)建二叉判定樹(shù)中的一個(gè)節(jié)點(diǎn) 算法對(duì)所有輸入情況的排序=對(duì)所有輸入情況進(jìn)行二叉判定樹(shù)構(gòu)造 任意給定輸入序列排序=二叉判定樹(shù)根到葉的路徑（或逆） 對(duì)任意n個(gè)元素進(jìn)行正確排序=二叉判定樹(shù)至少能區(qū)分n！種情況時(shí)間復(fù)雜度以比較次數(shù)來(lái)計(jì)算=葉到根路徑長(zhǎng)

23、最壞情況的時(shí)間復(fù)雜度下界：最矮的二叉判定樹(shù)高度 平均情況復(fù)雜度的下界：最好的二叉判定樹(shù)的根到葉長(zhǎng)的加權(quán)平均 對(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)A(2)A(3)A(1)A(3)表示一次比較一種可能的分類(lèi)序列2.5 快速分類(lèi)1、快速分類(lèi)的分治思想：選取數(shù)組A中的某個(gè)元素 t=As，然后將其他元素 重新排列，使A中所有在t以前出現(xiàn)的元素都小于或等于t，而在t之后出現(xiàn)的元素都大于或等于t。這個(gè)重新整理的過(guò)程成為劃分，t稱(chēng)為劃分元素。A1A2As-1AsAs+1An劃分元素

24、t經(jīng)過(guò)一次劃分后A1A2AjtAkAn每個(gè)元素都小于或等于t每個(gè)元素都大于或等于tprocedure 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二、快速分類(lèi)算法劃分A(low,high), 函數(shù)執(zhí)行完后, j返回劃分元素的下標(biāo)遞歸調(diào)用劃分之后得到的兩個(gè)集合三、劃分過(guò)程PARTITION的實(shí)現(xiàn)procedure

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

26、j=8; call PARTITION(1, 8); call QUICKSORT(low, j-1) call QUICKSORT(j+1, high) end QUICKSORT快速分類(lèi)實(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 (ip) then Ai Ap; A1A2A3A4A5A6A75392718A1A2A3A4A5A6A75312798Am=Ap;

27、 即A1=A4=2Ap=t; 即A4=5end / p=4的值帶回loop(第2次,i=3,p=6) loop i+ until Ait ; i=5 loop p- until Apt ; p=4 if (ip) 執(zhí)行else exit loop1 A1A2A3A4A5A6A75312798A1A2A3A4A5A6A72315798遞歸調(diào)用QUICKSORT(low, j-1) 即QUICKSORT(1, 3)遞歸調(diào)用QUICKSORT(j+1,high) 即QUICKSORT(5, 7) 四、快速分類(lèi)算法的的時(shí)空分析 ： 時(shí)間復(fù)雜性：假設(shè)前提互不相同；隨機(jī)選取劃分元素最壞情況下： 劃分算法比

28、較次數(shù)為元素?cái)?shù):p-m+1 第i級(jí)的比較次數(shù)：n-i+1 （每次取最小或最大值） 總和：n+(n-1)+= O(n2) 平均情況下： 劃分元素最終位置機(jī)會(huì)均等O(nlogn) ， 劃分單元隨機(jī)選取的改進(jìn) 快速分類(lèi)的性能取決于劃分的對(duì)稱(chēng)性！最好能找到中間元素 時(shí)間復(fù)雜性：棧空間使用 遞歸算法：最壞情況下 O(n) 改進(jìn)的迭代算法：每次選擇小的文件繼續(xù)處理（較小的文件在處理過(guò)程中相對(duì)迭代次數(shù)少，可能產(chǎn)生的?？臻g占用少） O(log n)五、快速分類(lèi)的迭代模型 2.6 選擇問(wèn)題 一、問(wèn)題的描述 p91 二、選擇問(wèn)題的解決思想 三、選擇問(wèn)題的分治算法 p91 四、算法的時(shí)間分析 p93 五、算法的改進(jìn) p94 六、改進(jìn)算法的實(shí)現(xiàn) p962.7 二進(jìn)制位乘問(wèn)題 一、問(wèn)題描述 設(shè)X和Y是兩個(gè)n位的二進(jìn)制數(shù)，求X與Y的乘積。取操作為位運(yùn)算。 為了簡(jiǎn)化討論不妨假定n是2的整次冪。 按傳統(tǒng)的乘法須O(n2)次