【文章內(nèi)容簡(jiǎn)介】 0 0 0 1 1 0 1 1 0 0 1 1 1 0 1 大整數(shù)的乘法 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 41 ? 。 將 n位的二進(jìn)制整數(shù)分為 2段： A n/2位 B n/2位 C n/2位 D n/2位 X= Y= 則： X=A2n/2+B（ 乘 2n/2， 相當(dāng)于左移 n/2位 ） Y=C2n/2+D 于是： XY = (A2n/2+B) (C2n/2+D) =AC2n + (AD+BC) 2n/2 + BD (1) 大整數(shù)的乘法 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 42 大整數(shù)的乘法 ?效率： ? 4次 n/2位整數(shù)乘法 (AC, AD,BC, BD)； ?3次不超過 n位整數(shù)加法； ?2次移位 (分別對(duì)應(yīng)乘以 2n和 2n/2) ?所有加法和移位共用 O(n)步計(jì)算。 時(shí)間復(fù)雜性分析 T(n)=O(n2) ?沒有改進(jìn) 11)()2/(4)1()(??????? nnnOnTOnT算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 43 改進(jìn)：把 (1)式稍作修改： XY = AC2n + ((A－ B)(D－ C)+AC+BD) 2n/2 + BD (2) 效率： ? 3次 n/2位整數(shù)乘法 (AC, BD, (A－ B)(D－ C))； ? 6次不超過 n位整數(shù)加、減法和 2次移位； 時(shí)間復(fù)雜性分析 T(n)=O(nlog3) =O() ?較大的改進(jìn) 11)()2/(3)1()(???????nnnOnTOnT大整數(shù)的乘法 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 44 大整數(shù)的乘法 Char *Mult(char X[ ],char Y[ ],int n) { //兩個(gè) n位整數(shù)相乘 S=sign(X)*sign(Y)。 //取乘積的符號(hào) X=abs(X)。 Y=abs(Y)。 if(n==1) return (S*X*Y)。 else { A=X的左邊 n/2位； B=X的右邊 n/2位； C=Y的左邊 n/2位； D=Y的右邊 n/2位； m1=Mult(A, C, n/2)。 m2=Mult(AB, DC, n/2)。 m3=Mult(B, D, n/2)。 S=S*(m1* 2n +(m1+m2+m3)*2n/2+m3)。 return S。 } } 注意 ： 該算法可改為十進(jìn)制數(shù)乘法，只需將基數(shù) 2變?yōu)?10， 即： 2n → 10n, 2n/2 → 10n/2 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 45 大整數(shù)的乘法 ?分析 ?傳統(tǒng)的方法 ： O(n2) ?效率太低 ?分治法 : O() ?較大的改進(jìn) ?更快的方法？？？ ?對(duì)于大整數(shù)乘法，它能在 O(nlogn)時(shí)間內(nèi)解決。 ?是否能找到線性時(shí)間的算法？？？ ?目前為止還沒有結(jié)果 。 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 46 大整數(shù)的乘法 ?思考： ? 乘方 an的計(jì)算方法 ?分析： ? 法 1： an =a a… a T(n)=Θ（ n） ? 法 2： / 2 / 2 1 / 2 1 / 2nnnnnnaaanaaa? ?? ???? （ ） （ ）是 偶 數(shù)是 奇 數(shù)( ) ( / 2) ( 1 ( ) ( l og )) TnT n T n n? ??? ? ?算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 47 strassen矩陣乘法 ?矩陣乘法 ?問題描述 ?An n Bn n=Cn n ?求解方法 ?傳統(tǒng)方法： O(n3) ?分治法 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 48 ?分治法 ? 將矩陣 A， B和 C中每一矩陣都分塊成 4個(gè)大小相等的子矩陣，每個(gè)子矩陣都是 n/2 n/2的方陣。 ? 由此可將方程 C=A B重寫為： 1 1 1 2 1 1 1 2 1 1 1 22 1 2 2 2 1 2 2 2 1 2 2C C A A B BC C A A B B? ? ? ? ? ???? ? ? ? ? ?? ? ? ? ? ??由此可得： 2112111111 BABAC ??2212121112 BABAC ??2122112121 BABAC ??2222122122 BABAC ??23( 1 ) 2()8 ( / 2) ( ) 2 ( ) ( )OnTnT n O n nT n O n??? ??????算 法 復(fù) 雜 性 分 析strassen矩陣乘法 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 49 strassen矩陣乘法 ? 改進(jìn)： Strassen矩陣乘法 )( 2212111 BBAM ??2212112 )( BAAM ??1122213 )( BAAM ??)( 1121224 BBAM ??))(( 221122115 BBAAM ???))(( 222122126 BBAAM ???))(( 121121117 BBAAM ???624511 MMMMC ????2112 MMC ??4321 MMC ??731522 MMMMC ???? 驗(yàn)證 :C22 = M5+M1M3M7 = (A11+A22)(B11+B22) +A11 (B12B21) (A21+A22) B11 (A11A21)(B11+B12) =A11B11+A11B22+A22B11+A22B22+A11B12 A11B22 A21B11 A22 11 A11B11 A11B12+A21B11+A21B12 =A21B12+A22B22 2112111111 BABAC ??2212121112 BABAC ??2122112121 BABAC ??2222122122 BABAC ??算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 50 strassen矩陣乘法 2( 1 ) 2()7 ( / 2) ( ) 2 OnTnT n O n n??? ????算法復(fù)雜性分析：l og 7 2. 81( ) ( ) ( )T n O n O n? ? ?算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 51 strassen矩陣乘法 ?矩陣乘法 ?傳統(tǒng)的方法 ?O(n3) ?分治法 ?O() ?O(… ) 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 52 應(yīng)用專題二 ?組合問題中的分治法 ?棋盤覆蓋問題 ?循環(huán)日程賽安排問題 ?最大子段和問題 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 53 ?問題描述： ? 在一個(gè) 2k 2k 個(gè)方格組成的棋盤中，恰有一個(gè)方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為特殊棋盤。 ? 在棋盤覆蓋問題中，要用圖示的 4種不同形態(tài)的 L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何 2個(gè) L型骨牌不得重疊覆蓋。 棋盤覆蓋問題 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 54 棋盤覆蓋問題 ?例如： ? k＝ 2時(shí)的一個(gè)特殊棋盤 2k 2k 的棋盤覆蓋中，用到的骨牌數(shù)為 (4k1)/3 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 55 ?例如： 5 5 4 4 5 1 1 4 3 1 2 2 3 3 2 棋盤覆蓋問題 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 56 ?分析： ? 當(dāng) k =0時(shí)，有 1種覆蓋方案 ? 當(dāng) k 0時(shí)，考慮采用分治策略： 棋盤覆蓋問題 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 57 ?算法實(shí)現(xiàn)（ P18） ?算法分析 : ? 設(shè) T(k)為覆蓋 2k 2k殘缺棋盤的時(shí)間 , T(k)=O(4k) 漸進(jìn)意義下的最優(yōu)算法 ???????? 00)1()1(4)1()(kkOkTOkT與所需骨牌數(shù)同階 棋盤覆蓋問題 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 58 ?還可以將棋盤覆蓋推廣到一般情況： 8 8 7 7 8 6 6 7 5 4 4 6 5 5 4 3 2 1 1 3 3 2 2 1 12 11 11 10 9