[工學(xué)]第四章遞歸與分治(參考版)
2024-10-16 17:50本頁面
【正文】 大整數(shù)乘法的分治策略改進(jìn) 。 大整數(shù)乘法的分治策略改進(jìn) 改進(jìn)分治策略的時間復(fù)雜性分析： 得 T(n)的遞歸方程為： ??????)()2/(3)(1)1(nOnTnTT用換名和遞推法解得： T(n)=O(nlog3)。則有： ??????)()2/(4)(1)1(nOnTnTT用換名和遞推法解得： T(n)=O(n2)， 同直接乘積的 時間復(fù)雜性。 n/2位 A B X= n/2位 C D Y= X=A*10n/2+B Y=C*10n/2+D 大整數(shù)乘法的分治策略 治理步、組合步： BDBCADACDCBAYXnnnn???????????2/2/2/10)(10)10(*)10(*計算包括 4次 n/2個十進(jìn)制整數(shù)乘積， 2次移位， 3次加。 關(guān)于矩陣乘積 大整數(shù)乘法 問題描述： 設(shè) X、 Y是 n位十進(jìn)制大整數(shù)，用軟件 方法計算 X*Y。 目前最好的計算時間上界是 Ο ()。或許應(yīng)當(dāng) 研究 3 3或5 5矩陣的更好算法 。 根據(jù) Strassen矩陣乘法 ,得其遞歸方程為： ????????2418)2/(7)(25)2(nnTnTT求解該方程： Strassen矩陣乘積時間復(fù)雜性分析 )()()2()()7l o g()(l o g)7()2()7(27418725)()(2418)1(7)(25)1(),2(T)k(g,2n og7l og221212kknOnOOnTkOnTOTOigbcbkgkgkggkkkkkiiikkkiikkk???????????????????????????????用遞推法求解得：得令Strassen矩陣乘積時間復(fù)雜性分析 Hopcroft和 Kerr已經(jīng)證明 (1971)，計算 2個２ ２矩陣的乘積， 7次乘法是必要的。 矩陣乘積分治策略時間復(fù)雜性分析 上述矩陣乘積分治策略對 n階矩陣乘積計算了 8個 n/2 矩陣乘積， Stassen矩陣乘法改進(jìn)了其中的治理步和 綜合步，用如下方法進(jìn)行： Strassen矩陣乘積 M1 = A11*(B12B22) M2 = (A11+A12)*B22 M3 = (A21+A22)*B11 M4 = A22*(B21B11) M5 = (A11+A22)*(B11+B22) M6 = (A12A22)*(B21+B22) M7 = (A11A21)*(B11+B12) C11 = M5+M4M2+M6 C12 = M1+M2 C21 = M3+M4 C22 = M5+M1M3M7 共計算 7個 n/2階矩陣乘積， 18個 n/2階矩陣加減。 Strassen矩陣乘積 矩陣乘積的分治策略： 直接解： n=2 劃分步： n=2k,將各矩陣分解為 4個 n/2階矩陣，即 A 1 1A 2 1A 1 2A 2 2B 1 1B 2 1B 1 2B 2 2C 1 1C 2 1C 1 2C 2 2 治理步、組合步： C11 = A11*B11+A12*B21 C12 = A11*B12+A12*B22 C21 = A21*B11+A22*B21 C22 = A21*B21+A22*B22 ?????????????????????????????48843773266215514321876587654321?????????????????62516521 ????????????????? 26 1565 21 ????????????????? 48 3787 43?????????????????84738743D1 D2 5： C11 1 2 3 4 6 7 D1 8 9 D2 10:C12 矩陣乘積分治策略舉例： C11
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1