算法合集之《多項(xiàng)式乘法》.ppt

多項(xiàng)式乘法,張家琳 復(fù)旦大學(xué)附屬中學(xué),引言,多項(xiàng)式是最基本的數(shù)學(xué)工具之一，由于其形式簡(jiǎn)單，且易于用計(jì)算機(jī)對(duì)其進(jìn)行各種計(jì)算，在當(dāng)今的社會(huì)中應(yīng)用越來(lái)越廣。不僅在像Maple這樣的數(shù)學(xué)軟件中有著舉足輕重的作用，在工程、信息等諸多領(lǐng)域中都有著廣闊的應(yīng)用。,下面我們給出幾個(gè)多項(xiàng)式逼近的例子：,多項(xiàng)式的基本運(yùn)算,加法運(yùn)算,求值運(yùn)算,乘法運(yùn)算,普通的多項(xiàng)式乘法運(yùn)算,多項(xiàng)式乘法是一個(gè)很常見(jiàn)的問(wèn)題，在通常的算法中，兩個(gè) 次多項(xiàng)式的乘法需要用 的時(shí)間才能完成。,讓我們先來(lái)看一看這樣的算法是如何進(jìn)行的：,. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .,在上面的過(guò)程中，似乎我們覺(jué)得這個(gè)算法并沒(méi)有做任何多余的事情，因?yàn)槲覀儽仨毧紤]每一組 ,它們的乘積對(duì)最終的結(jié)果都會(huì)產(chǎn)生影響。而且我們不能通過(guò)調(diào)整計(jì)算順序從根本上降低算法時(shí)間復(fù)雜度，至多只能使其常數(shù)因子稍小一些。,如果我們不能跳出以上思維的局限，我們就不可能在根本上降低算法的時(shí)間復(fù)雜度。,讓我們首先換一個(gè)角度來(lái)考察多項(xiàng)式。,多項(xiàng)式的點(diǎn)值表示法,首先讓我們來(lái)看多項(xiàng)式的另一種表示方法：點(diǎn)值表示法,即用 （其中， 互不相同）來(lái)表示一個(gè)不超過(guò) 次多項(xiàng)式。,給定一個(gè)多項(xiàng)式，要給出n組點(diǎn)值對(duì)最簡(jiǎn)單的方法是任選 n個(gè)互不相同的xi，依次求出多項(xiàng)式在這n個(gè)點(diǎn)的值。,用n個(gè)點(diǎn)值對(duì)也可以唯一確定一個(gè)不超過(guò)n-1次多項(xiàng)式，這個(gè)過(guò)程稱之為插值。,引理1（多項(xiàng)式插值的唯一性）,對(duì)于任意n個(gè)點(diǎn)值對(duì)組成的集合, 其中 互不相同，則存在唯一的次數(shù)不超過(guò)n-1的多項(xiàng)式 ，滿足,continue,存在性：,已知,不妨記為XA=Y,X是范德蒙矩陣，利用行列式的變換可得該矩陣的行列式的值為,因此X有逆矩陣 。,唯一性：,若兩個(gè)函數(shù)次數(shù)不超過(guò)n-1次的多項(xiàng)式 均符合題意，則多項(xiàng)式 有n個(gè)根， 且 為不超過(guò)n-1次的多項(xiàng)式，所以 , 即 。,back,點(diǎn)值多項(xiàng)式的乘法,因此： 適當(dāng)?shù)睦命c(diǎn)值表示可以使多項(xiàng)式的乘法可以在線性時(shí)間內(nèi)完成！,因?yàn)閒(x)g(x)的次數(shù)為n-1，r(x)的次數(shù)為2n-2,因此確定r(x)需要2n-1個(gè)點(diǎn)值對(duì)，而現(xiàn)在我們只有n個(gè)點(diǎn)值對(duì)。,我們可以通過(guò)對(duì)f(x)與g(x)的點(diǎn)值對(duì)個(gè)數(shù)的 擴(kuò)充來(lái)解決這個(gè)問(wèn)題，即將f(x),g(x）的點(diǎn)值對(duì)在一開(kāi)始就取為2n-1。,利用點(diǎn)值表示法改善多項(xiàng)式系數(shù)表示法的乘法,下面讓我們來(lái)看一看我們是否能夠利用點(diǎn)值表示法在計(jì) 算多項(xiàng)式乘法時(shí)的線性時(shí)間來(lái)提高系數(shù)表示法的多項(xiàng)式乘 法的速度。 為了做到這一點(diǎn)，我們需要做： 將多項(xiàng)式由系數(shù)表示法轉(zhuǎn)化為點(diǎn)值表示法(點(diǎn)值過(guò)程） 利用點(diǎn)值表示法完成多項(xiàng)式乘法 將點(diǎn)值表示法再轉(zhuǎn)化為系數(shù)表示法（插值過(guò)程） 其中第二步只需要線性時(shí)間。問(wèn)題的關(guān)鍵轉(zhuǎn)化為第一 第三步。,continue2,continue1,continue3,1.由系數(shù)表示法轉(zhuǎn)化為點(diǎn)值表示法。（點(diǎn)值過(guò)程）,注意！x0,x1,xn-1是由我們自己選擇的，我們可以充分利用這一點(diǎn)通過(guò)適當(dāng)?shù)倪x擇使轉(zhuǎn)化過(guò)程降為O(n log n)。,這里我們選擇1的n次單位根作為x0,x1,xn-1，即,其中,引理2：對(duì)任何整數(shù)n=0,k=0,j0,成立：,證明：,折半定理,注意到， 中包含了f中所有偶下標(biāo)的系數(shù)，而 中包含了f中所有奇下標(biāo)的系數(shù)。,并記,求 與 在點(diǎn) 的值。,問(wèn)題：求,設(shè)n為偶數(shù)（否則可以通過(guò)添加高次零項(xiàng)使n化為偶數(shù)）。,另一方面，由折半定理：,并不是n個(gè)不同的數(shù)，而是僅由1的n/2次單位根組成，每個(gè)根恰好出現(xiàn)2次。,由此可以看到子問(wèn)題與原問(wèn)題形式相同，但規(guī)模縮小一半，這啟示我們可以利用分治的思想通過(guò)遞歸來(lái)解決這個(gè)問(wèn)題。,遞歸算法的具體實(shí)現(xiàn)過(guò)程,遞歸邊界條件,Function transform(a:atype):y:ytype；,if n=1 then return a0,遞歸預(yù)處理,if odd(n) then begin inc(n);an-1:=0;end;,遞歸過(guò)程,For k:=0 to n-1 do 利用,計(jì)算,可以證明，以上計(jì)算方法的時(shí)間復(fù)雜度為O(n log n)。,back,2將點(diǎn)值表示法再轉(zhuǎn)化為系數(shù)表示法。（插值過(guò)程）,點(diǎn)值過(guò)程所解決的問(wèn)題可以等效為一個(gè)矩陣方程：,插值過(guò)程是點(diǎn)值過(guò)程的逆運(yùn)算。這個(gè)問(wèn)題比前一個(gè)問(wèn)題看起來(lái)更復(fù)雜，但事實(shí)上，通過(guò)適當(dāng)?shù)霓D(zhuǎn)化可以把這個(gè)問(wèn)題轉(zhuǎn)化為前一個(gè)問(wèn)題。,記為,Y,A,點(diǎn)值過(guò)程,插值過(guò)程,如果,存在,引理3,利用引理3，我們就可以很容易的解決插值的問(wèn)題。,Y,A,可等效為矩陣方程：,因此，我們可以充分利用點(diǎn)值過(guò)程的方法求出多項(xiàng)式的系數(shù)表達(dá)。,遞歸邊界條件,Function transform( a:atype ):y:ytype ；,if n=1 then return a0,遞歸預(yù)處理,if odd(n) then begin inc(n); an-1:=0; end;,遞歸過(guò)程,For k:=0 to n-1 do 利用,計(jì)算,back,a:atype,y:ytype,y0,yn-1:=0;,遞歸結(jié)束后再將a中每一個(gè)數(shù)除以n。,多項(xiàng)式乘法的算法流程,問(wèn)題：f(x),g(x)是兩個(gè)n-1次的多項(xiàng)式，已知f(x)g(x)的系數(shù)表示，求出r(x)=f(x)*g(x)的系數(shù)表示。,算法流程：,1. 預(yù)處理：通過(guò)加入n-1個(gè)值為0的高價(jià)次數(shù)，使f(x)g(x)的次數(shù)增加到2n-2。這是為了使點(diǎn)值對(duì)的個(gè)數(shù)足夠能夠唯一確定r(x)。,2. 點(diǎn)值：利用分治的方法，通過(guò)函數(shù)transform求出f(x)與g(x)在1的2n-1次單位根處的值。,3. 點(diǎn)乘：將f(x),g(x)在各點(diǎn)的值逐點(diǎn)相乘，計(jì)算出r(x)在各點(diǎn)的值。,4. 插值：互換a與y的作用，再利用函數(shù)transform求r(x)的系數(shù)表示，并注意要將結(jié)果除以次數(shù)作為最后結(jié)果。,以上第1、第3步的執(zhí)行時(shí)間都是O(n)，第2、第4步的執(zhí)行時(shí)間都是O(n log n)。,算法改進(jìn),在函數(shù)transform中，我們是用遞歸的方式來(lái)求解，我們對(duì)n=8的情況來(lái)具體演示一下遞歸調(diào)用的過(guò)程。,但是遞歸的方法對(duì)空間的要求很高，從函數(shù)transform中可以看到每次遞歸調(diào)用時(shí)都需要新的系數(shù)數(shù)組傳入遞歸過(guò)程內(nèi)部。而通過(guò)剛才的演示，我們發(fā)現(xiàn)我們也可以用從底向上迭代的方法來(lái)進(jìn)行。,迭代算法的具體實(shí)現(xiàn)過(guò)程,初始化,預(yù)處理,通過(guò)增加高次零項(xiàng)使將多項(xiàng)式的次數(shù)增加到2的冪次。,Function transform_better (a:atype):y:yt