[工學(xué)]第四章遞歸與分治-資料下載頁(yè)
2024-10-13 17:50本頁(yè)面
【正文】 12)2(nnTnTT求解該方程： 矩陣乘積分治策略時(shí)間復(fù)雜性分析 )()(2222221281222212)()(2)1(8)(12)1(),2(T)k(g,2n323233223333212kknOnTigbcbkgkgkggkkkkkkiiikkkiikkk????????????????????????????????用遞推法求解得：得令時(shí)間復(fù)雜性未降低，同 多項(xiàng)式相乘，需設(shè)法降 低 n/2矩陣的乘積次數(shù)。 矩陣乘積分治策略時(shí)間復(fù)雜性分析 上述矩陣乘積分治策略對(duì) n階矩陣乘積計(jì)算了 8個(gè) 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 共計(jì)算 7個(gè) n/2階矩陣乘積， 18個(gè) n/2階矩陣加減。 設(shè) T(n)為 2個(gè) n階矩陣乘積的乘法和加法運(yùn)算次數(shù)。 根據(jù) Strassen矩陣乘法 ,得其遞歸方程為： ????????2418)2/(7)(25)2(nnTnTT求解該方程： Strassen矩陣乘積時(shí)間復(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矩陣乘積時(shí)間復(fù)雜性分析 Hopcroft和 Kerr已經(jīng)證明 (1971)，計(jì)算 2個(gè)２ ２矩陣的乘積， 7次乘法是必要的。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時(shí)間復(fù)雜性，就不能再基于計(jì)算 2 2矩陣的 7次乘法這樣的方法了?；蛟S應(yīng)當(dāng) 研究 3 3或5 5矩陣的更好算法 。 在 Strassen之后又有許多算法改進(jìn)了矩陣乘法的計(jì)算時(shí)間復(fù)雜性。 目前最好的計(jì)算時(shí)間上界是 Ο ()。 目前知道的最好下界為 Ω (n2)。 關(guān)于矩陣乘積 大整數(shù)乘法 問(wèn)題描述： 設(shè) X、 Y是 n位十進(jìn)制大整數(shù)，用軟件 方法計(jì)算 X*Y。 直接解： n=1 劃分步： X、 Y分別劃分為兩個(gè) n/2位整數(shù)。 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(*計(jì)算包括 4次 n/2個(gè)十進(jìn)制整數(shù)乘積， 2次移位， 3次加。 大整數(shù)乘法的分治策略 分治策略時(shí)間復(fù)雜性分析 : 設(shè) T(n)為計(jì)算 2個(gè) n位大整數(shù)乘積所需的時(shí)間。則有： ??????)()2/(4)(1)1(nOnTnTT用換名和遞推法解得： T(n)=O(n2)， 同直接乘積的 時(shí)間復(fù)雜性。 大整數(shù)乘法的分治策略 治理步和綜合步改進(jìn)為： BDBDACCDBAACYX nn ????????? 2/10]))([(10*計(jì)算包括 3次 n/2個(gè)十進(jìn)制整數(shù)乘積， 2次移位， 6次加、減。 大整數(shù)乘法的分治策略改進(jìn) 改進(jìn)分治策略的時(shí)間復(fù)雜性分析： 得 T(n)的遞歸方程為： ??????)()2/(3)(1)1(nOnTnTT用換名和遞推法解得： T(n)=O(nlog3)。 該方法適用于計(jì)算其它進(jìn)制整數(shù)的乘積。 大整數(shù)乘法的分治策略改進(jìn)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1