第三講分治法3遞歸與策略

32~3[找出偽幣]給你一個(gè)裝有16個(gè)硬幣的袋子。16個(gè)硬幣中有一個(gè)是的，并且那個(gè)1211111一 分治任何一個(gè)可以用計(jì)算機(jī)求解的問題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問題的規(guī)模越n1時(shí)，不需任何計(jì)算。2時(shí)，只要作一次比較即可排好序。33次比較即n有時(shí)是相當(dāng)?shù)摹個(gè)子問題，1<k≤n，且這些子問題都可解，并可利用這些子（分而治之2、分治法所能解決的問題一般具有以下幾個(gè)特征簡問題的求{{}分解成k個(gè)子問題p1,p2 pkDC(pi}kk=2自一種平衡(alancig)子問題的思，它幾乎總是問題規(guī)模不等的做法要好。二 例棋盤?，F(xiàn)在任意給定一個(gè)2k×2k的特殊棋盤，要用右下圖所示的L型骨牌來無的覆23233221341154455設(shè)X和Y都是n位的二進(jìn)制整數(shù)，現(xiàn)在要計(jì)算它們的乘積XY。我們可以用小學(xué)所學(xué)XY的算法，但是這樣做計(jì)算步驟太多，顯得效率較低。見教P25，T(n)=O(n2)。如果將每2個(gè)1位數(shù)的乘法或加法看作一步運(yùn)算，那么這種方法要作O(n2)步運(yùn)算才能求出乘積XY。下面我們用分治法來設(shè)計(jì)一個(gè)更有效的大整數(shù)乘積算法。nX和Y2n/2位(為簡單起見，假設(shè)n2的冪)由此，X=A2n/2+B，Y=C2n/2+D。這樣，XY 如果按式(1)計(jì)算XY，則須進(jìn)行4次n/2位整數(shù)的乘法(AC，AD，BC和BD)3n位的整數(shù)加法(分別對(duì)應(yīng)于式(1)中的加號(hào))2次移位(分別對(duì)應(yīng)于式(1)2n2n/2)。所有這些加法和移位共用O(n)步運(yùn)算。設(shè)T(n)2個(gè)n位整數(shù)相乘所需的運(yùn)算總數(shù)，則由式(1)，我們有:T(n)=O(n2)。因此，用(1)X和Y的乘積并不比小學(xué)生的方法更有XY寫成另一種形式:XY=AC2n+[(A-B)(D- 雖然，式(3)看起來比式(1)3n/2位整數(shù)的乘法(AC，BD和(A-B)(D-C))，62次移位。由此可得:用解遞歸方程的套用法馬上可得其解為T(n)=O(nlog3)=O(n159)。intMULT(intX，int X和Y22nXY{intS=sign(X)*sign(Y{SXY的符號(hào)乘積}Y=abs(Y{XY分別取絕對(duì)值}if(n==1)if(X==1)return{

returnA=Xn/2位;B=X的右邊n/2位;C=Y的左邊n/2位;D=Yn/2位;returnS;}}X=314l,Y=5327XY的計(jì)算過程可列表如下，其中帶'號(hào)的數(shù)值是AC，BD，和(A-B)(D-C)之后才填入的。D-C=- A1-D1-C1=-(A1-B1)(D1-C1)=-AC=1500+(15+3-A2-D2-(A2-B2)(D2-|A- A3- 3、StrassenAB2n×n的矩陣，則它們的乘積C=AB同樣是一個(gè)n×n的矩陣。AB的乘積矩陣CC[i,j]定義為:A和BCCC[i,j]n個(gè)n-1Cn20(n3)。60年代末，Strassen2階矩陣乘積所需的計(jì)算時(shí)間改進(jìn)到O(nlog7)=O(n2.18)n2A，BC4個(gè)n/2×n/2C=AB重寫為:由此可得 n=222階方陣的乘積可以直接用(2)-(3)8次加法。當(dāng)子矩陣的階大于2時(shí)，為求2個(gè)子矩陣的積，可以繼續(xù)將子矩陣分塊，直到子矩陣的階降為2。這樣，就產(chǎn)生了一個(gè)分治降階的遞歸算法。依此算法，計(jì)算2個(gè)n階方陣的乘積轉(zhuǎn)化為計(jì)算8n/2階方陣的乘積和4n/2階方陣的加法。2n/2×n/2矩陣的加法顯然可以在c*n2/4時(shí)間內(nèi)完成，這里c是一個(gè)常數(shù)。因此，上述分治法的計(jì)算時(shí)間T(n)應(yīng)該滿足：T(n3。因此，該方法并不比用原始定義直接計(jì)算更有效。究其原因，乃是由于式5并沒有減少矩陣的乘法次數(shù)。而矩陣乘法耗費(fèi)的時(shí)間要比矩陣加減法耗費(fèi)的時(shí)間多得多。要想改進(jìn)矩陣乘法的計(jì)算時(shí)間復(fù)雜性，必須減少子矩陣乘法運(yùn)算的次數(shù)。按照上述分治法的思想可以看出，要想減少乘法運(yùn)算次數(shù)，關(guān)鍵在于計(jì)228次的乘法運(yùn)算。Strssn2277次乘法是7次乘法后，再做若干次加、減法就可以得到:=(A11+A22)(B11+B22)+A11(B12-B22)-(A21+A22)B11-(A11--A11B22-A21B11-A22B11-A11B11-由(2)式便知其正確性Strassen7n/218T(n)滿足如下的遞歸方程按照解遞歸方程的套用法，其解為T(n)=O(nlog7)≈O(n2.81)。由此可見nn-1ijij1≤i≤n，1≤j≤n-1。nn/2

2 8

785 ）圖 塊分別為選手1至選手4和選手5選手83天的比賽日程。據(jù)此，將左上角小塊中的角，這樣我們就分別安排好了選手1至選手4選手58在后4天的比賽日程。依voidmatchtable(inta[][N],int{intn=1,for(inti=1;i<=k;n*=for(inti=0;i<n;i++)for(ints=0s<k; k{n/=for(intt=0t<n;t每個(gè)階段有t{for(i