[工學(xué)]第四章遞歸與分治(編輯修改稿)
2024-11-09 17:50 本頁面
【文章內(nèi)容簡介】 (nlog3)，優(yōu)于直接乘積的 O(n2)，其原因在于降低了低階多項(xiàng)式乘積次數(shù)。 該思想也被用于后續(xù)的矩陣乘積和大整數(shù)乘法分治算法中，它們都是通過降低低階乘積次數(shù)達(dá)到改進(jìn)時(shí)間復(fù)雜性的目的。 例 ： 設(shè)多項(xiàng)式 p(x) = 1+ x x2 + 2x3 q(x) = 1 x + 2x2 – 3x3 用分治法計(jì)算這兩個(gè)多項(xiàng)式的乘積。 多項(xiàng)式乘積的分治算法實(shí)例 解： n=4,n/2=2,劃分多項(xiàng)式得： p(x) = (1+ x) +(1 + 2x)x2 q(x) = (1 x) +(2 – 3x)x2 4121020 )())()()(()()()( xxrxxrxrxrxrxqxp ?????多項(xiàng)式乘積的分治算法實(shí)例 222120129)321)(211()(672)32)(21()(1)1)(1()(xxxxxxxrxxxxxrxxxxr??????????????????????6543654222422222267721672)521(1)672()6721129(1)()(xxxxxxxxxxxxxxxxxxxxxxqxp??????????????????????????多項(xiàng)式乘積的分治算法實(shí)例 多項(xiàng)式乘積的分治算法實(shí)現(xiàn) 多項(xiàng)式 p(x)、 q(x)、 p(x)q(x)均用數(shù)組存放。 輸入： 多項(xiàng)式系數(shù)個(gè)數(shù) n 含 n個(gè)元素的數(shù)組 p— p(x)的系數(shù) 含 n個(gè)元素的數(shù)組 q— q(x)的系數(shù) 輸出： 含 2n1個(gè)元素的數(shù)組 r0— p(x)q(x)的系數(shù) 多項(xiàng)式分治算法實(shí)現(xiàn)的關(guān)鍵在于計(jì)算過程中 r0、 rr2元素存放位置及計(jì)算時(shí) p,q的起始位置和涉及的元素個(gè)數(shù)。 多項(xiàng)式乘積的分治算法實(shí)現(xiàn) 下面以例 。 初始 :n=4,令 k=n/2=2 1 1 1 2 多項(xiàng)式乘積的分治算法實(shí)現(xiàn) p數(shù)組： q數(shù)組： 1 1 2 3 k p0 p1 k q0 q1 計(jì)算 r0： r0(x)=p0(x)q0(x)=(1+x)(1x) 1 0 1 多項(xiàng)式乘積的分治算法實(shí)現(xiàn) r0數(shù)組： p、 q從 0開始，長度為 k的元素組成的多項(xiàng)式的乘積 r0在 p(x)q(x)中最低次為 0，最高次 2k2。 計(jì)算 r1： r1(x)=p1(x)q1(x)=(1+2x)(23x) 2 7 6 多項(xiàng)式乘積的分治算法實(shí)現(xiàn) r1數(shù)組： p、 q從 k開始，長度為 k的元素組成的多項(xiàng)式的乘積 r1在 p(x)q(x)最低次為 n，最高次 2n2。 計(jì)算 r2： r2(x)=(p0(x)+p1(x))(q0(x)+q1(x)) 0 3 多項(xiàng)式乘積的分治算法實(shí)現(xiàn) r3數(shù)組： r3(x) = p0(x)+p1(x) r4(x) = q0(x)+q1(x) 3 4 r4數(shù)組： r2(x) = r3(x)r4(x) r r4從 0開始，長度為 k的元素組成的多項(xiàng)式的乘積 r2在 p(x)q(x)最低次為 k，最高次 3k2。 多項(xiàng)式乘積的分治算法實(shí)現(xiàn) 0 9 12 r2數(shù)組： r2(x)= r2(x) – r0(x) r2 從 k開始， r0從 0開始，長度為 2k1的對應(yīng)元素相減 多項(xiàng)式乘積的分治算法實(shí)現(xiàn) 0 9 12 r2數(shù)組： 1 0 1 r0數(shù)組： 1 9 11 r2結(jié)果： r2(x)= r2(x) – r1(x) r2 從 k開始， r0從 n開始，長度為 2k1的對應(yīng)元素相減 多項(xiàng)式乘積的分治算法實(shí)現(xiàn) 1 9 11 r2數(shù)組： 2 7 6 r1數(shù)組： 1 2 5 r2結(jié)果： r0(x) = r0(x) + r2(x)(計(jì)算 r0(x) + r2(x)xk） r0 從 k開始， r2從 k開始，長度為 2k1的對應(yīng)元素相加 多項(xiàng)式乘積的分治算法實(shí)現(xiàn) 1 0 1 r0數(shù)組： 1 2 5 r2數(shù)組： 1 0 0 2 5 r0結(jié)果： r0(x) = r0(x) + r1(x)(計(jì)算 p(x)q(x)） r0 從 n開始， r1從 n開始，長度為 2k1的對應(yīng)元素相加 多項(xiàng)式乘積的分治算法實(shí)現(xiàn) 1 0 0 2 5 r0數(shù)組： 2 7 6 r1數(shù)組： 1 0 0 2 7 7 6 r0結(jié)果： 計(jì)算結(jié)果 多項(xiàng)式乘積的分治算
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1