[工學(xué)]第四章遞歸與分治-wenkub.com
2024-10-10 17:50 本頁面
【正文】 該方法適用于計算其它進(jìn)制整數(shù)的乘積。 大整數(shù)乘法的分治策略 分治策略時間復(fù)雜性分析 : 設(shè) T(n)為計算 2個 n位大整數(shù)乘積所需的時間。 目前知道的最好下界為 Ω (n2)。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時間復(fù)雜性，就不能再基于計算 2 2矩陣的 7次乘法這樣的方法了。 根據(jù) 分治策略 描述，得遞歸方程為： ?????????2)2(4)2/(8)(12)2(nnTnTT求解該方程： 矩陣乘積分治策略時間復(fù)雜性分析 )()(2222221281222212)()(2)1(8)(12)1(),2(T)k(g,2n323233223333212kknOnTigbcbkgkgkggkkkkkkiiikkkiikkk????????????????????????????????用遞推法求解得：得令時間復(fù)雜性未降低，同 多項式相乘，需設(shè)法降 低 n/2矩陣的乘積次數(shù)。 } 由于數(shù)組傳遞的特殊性，可省略 ps,qs,rs，其實現(xiàn)見P97 算法 。 //r2 = r3*r4 PolyMinus(r2,k+rs,r0,rs,2*k1)。 //r0 =p0*q0 PolyMulti(p,k,q,k,r1,n+rs,k)。元素初始為 0。 初始 :n=4,令 k=n/2=2 1 1 1 2 多項式乘積的分治算法實現(xiàn) p數(shù)組： q數(shù)組： 1 1 2 3 k p0 p1 k q0 q1 計算 r0： r0(x)=p0(x)q0(x)=(1+x)(1x) 1 0 1 多項式乘積的分治算法實現(xiàn) r0數(shù)組： p、 q從 0開始，長度為 k的元素組成的多項式的乘積 r0在 p(x)q(x)中最低次為 0，最高次 2k2。 例 ： 設(shè)多項式 p(x) = 1+ x x2 + 2x3 q(x) = 1 x + 2x2 – 3x3 用分治法計算這兩個多項式的乘積。 多項式乘積的分治算法 治理、組合步改進(jìn)： )()()()()()()()())()())(()((111001001010xqxpxqxpxqxpxqxpxqxqxpxp??????多項式乘積的分治算法改進(jìn) nnxxqxpxxqxpxqxpxqxpxqxp)()()]()()()([)()()()(112/100100????記： ))()() ) (()(()()()()()()()(10102111000xqxqxpxpxrxqxpxrxqxpxr?????多項式乘積的分治算法改進(jìn) nn xxrxxrxrxrxrxqxp )())()()(()()()( 12/1020 ?????改進(jìn)后的分治算法乘積次數(shù)為三次。 為降低 n次多項式乘積的時間復(fù)雜性，可將其轉(zhuǎn)換為低階多項式的乘積，且盡量減少乘積次數(shù)，增加多項式加減次數(shù)。 問題描述： 已知多項式 多項式乘積的分治算法 11101110...)(...)(????????????nnnnxbxbbxqxaxaaxp計算 p(x)*q(x)。 解： 直接解： n=1 劃分步、治理步： mid =(0+n1)/2。 min = y1y2 ? y1:y2。 } } else { mid = (low+high)/2。 if((highlow)=1) { if(A[low]A[high]) { max = A[high]。 治理步： 用分治法對兩個子序列進(jìn)行最大最小求解 組合步： 對得到的數(shù)據(jù)比較，求到全序列的最大 最小。 in。min,int n) { int x。設(shè) T(n)為分治算法的計算時間。 應(yīng)盡量使 k個子問題的規(guī)模大致相同。 i=k。遞歸地解這些子問題，然后將各子問題的解合 并得到原問題的解。 分治法的基本思想 分治法的一般設(shè)計步驟： divide_and_conquer(p(n)) { if(n=
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1