算法合集之《多項式乘法》.ppt

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