信息學(xué)集訓(xùn)隊作業(yè)zjl

1、多項式乘法 張家琳復(fù)旦大學(xué)附屬中學(xué)引言 多項式是最基本的數(shù)學(xué)工具之一，由于其形式簡單，且易于用計算機對其進(jìn)行各種計算，在當(dāng)今的社會中應(yīng)用越來越廣。不僅在像Maple這樣的數(shù)學(xué)軟件中有著舉足輕重的作用，在工程、信息等諸多領(lǐng)域中都有著廣闊的應(yīng)用。 下面我們給出幾個多項式逼近的例子：多項式的基本運算 加法運算 求值運算 乘法運算普通的多項式乘法運算 多項式乘法是一個很常見的問題，在通常的算法中，兩個 次多項式的乘法需要用 的時間才能完成。 讓我們先來看一看這樣的算法是如何進(jìn)行的： . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2、. . . . . 在上面的過程中，似乎我們覺得這個算法并沒有做任何多余的事情，因為我們必須考慮每一組 ,它們的乘積對最終的結(jié)果都會產(chǎn)生影響。而且我們不能通過調(diào)整計算順序從根本上降低算法時間復(fù)雜度，至多只能使其常數(shù)因子稍小一些。 如果我們不能跳出以上思維的局限，我們就不可能在根本上降低算法的時間復(fù)雜度。 讓我們首先換一個角度來考察多項式。多項式的點值表示法 首先讓我們來看多項式的另一種表示方法：點值表示法,即用 （其中， 互不相同）來表示一個不超過 次多項式。 給定一個多項式，要給出n組點值對最簡單的方法是任選 n個互不相同的xi，依次求出多項式在這n個點的值。 用n個點值對也可以唯一確定一個

3、不超過n-1次多項式，這個過程稱之為插值。引理1（多項式插值的唯一性） 對于任意n個點值對組成的集合, 其中 互不相同，則存在唯一的次數(shù)不超過n-1的多項式 ，滿足 continue存在性：已知不妨記為XA=YX是范德蒙矩陣，利用行列式的變換可得該矩陣的行列式的值為 因此X有逆矩陣 。唯一性： 若兩個函數(shù)次數(shù)不超過n-1次的多項式 均符合題意，則多項式 有n個根， 且 為不超過n-1次的多項式，所以 , 即 。 back點值多項式的乘法 因此： 適當(dāng)?shù)睦命c值表示可以使多項式的乘法可以在線性時間內(nèi)完成！ 因為f(x)g(x)的次數(shù)為n-1，r(x)的次數(shù)為2n-2,因此確定r(x)需要2n-1

4、個點值對，而現(xiàn)在我們只有n個點值對。 我們可以通過對f(x)與g(x)的點值對個數(shù)的 擴充來解決這個問題，即將f(x),g(x）的點值對在一開始就取為2n-1。利用點值表示法改善多項式系數(shù)表示法的乘法 下面讓我們來看一看我們是否能夠利用點值表示法在計 算多項式乘法時的線性時間來提高系數(shù)表示法的多項式乘 法的速度。 為了做到這一點，我們需要做： 將多項式由系數(shù)表示法轉(zhuǎn)化為點值表示法(點值過程） 利用點值表示法完成多項式乘法 將點值表示法再轉(zhuǎn)化為系數(shù)表示法（插值過程） 其中第二步只需要線性時間。問題的關(guān)鍵轉(zhuǎn)化為第一 第三步。continue2continue1continue31.由系數(shù)表示法轉(zhuǎn)化

5、為點值表示法。（點值過程） 注意！x0,x1,xn-1是由我們自己選擇的，我們可以充分利用這一點通過適當(dāng)?shù)倪x擇使轉(zhuǎn)化過程降為O(n log n)。 這里我們選擇1的n次單位根作為x0,x1,xn-1，即 其中引理2：對任何整數(shù)n=0,k=0,j0,成立：證明：折半定理注意到， 中包含了f中所有偶下標(biāo)的系數(shù)，而 中包含了f中所有奇下標(biāo)的系數(shù)。并記求 與 在點 的值。 問題：求設(shè)n為偶數(shù)（否則可以通過添加高次零項使n化為偶數(shù)）。另一方面，由折半定理： 并不是n個不同的數(shù)，而是僅由1的n/2次單位根組成，每個根恰好出現(xiàn)2次。 由此可以看到子問題與原問題形式相同，但規(guī)?？s小一半，這啟示我們可以利用分治

6、的思想通過遞歸來解決這個問題。 遞歸算法的具體實現(xiàn)過程遞歸邊界條件Function transform(a:atype):y:ytype；if n=1 then return a0遞歸預(yù)處理 if odd(n) then begin inc(n);an-1:=0;end; 遞歸過程For k:=0 to n-1 do 利用計算可以證明，以上計算方法的時間復(fù)雜度為O(n log n)。back2將點值表示法再轉(zhuǎn)化為系數(shù)表示法。（插值過程） 點值過程所解決的問題可以等效為一個矩陣方程： 插值過程是點值過程的逆運算。這個問題比前一個問題看起來更復(fù)雜，但事實上，通過適當(dāng)?shù)霓D(zhuǎn)化可以把這個問題轉(zhuǎn)化為前一個

7、問題。記為YA點值過程插值過程如果存在引理3利用引理3，我們就可以很容易的解決插值的問題。 YA可等效為矩陣方程： 因此，我們可以充分利用點值過程的方法求出多項式的系數(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; 遞歸過程For k:=0 to n-1 do 利用計算backa:atypey:ytypey0yn-1:=0;遞歸結(jié)束后再將a中每一個數(shù)除以n。多項式乘法的算法流程問題：f(x),g(x)是兩個

8、n-1次的多項式，已知f(x)g(x)的系數(shù)表示，求出r(x)=f(x)*g(x)的系數(shù)表示。算法流程：1. 預(yù)處理：通過加入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ù)表示，并注意要將結(jié)果除以次數(shù)作為最后結(jié)果。以上第1、第3步的執(zhí)行時間都是O(n)，第2、第4步的執(zhí)

9、行時間都是O(n log n)。 算法改進(jìn) 在函數(shù)transform中，我們是用遞歸的方式來求解，我們對n=8的情況來具體演示一下遞歸調(diào)用的過程。 但是遞歸的方法對空間的要求很高，從函數(shù)transform中可以看到每次遞歸調(diào)用時都需要新的系數(shù)數(shù)組傳入遞歸過程內(nèi)部。而通過剛才的演示，我們發(fā)現(xiàn)我們也可以用從底向上迭代的方法來進(jìn)行。迭代算法的具體實現(xiàn)過程初始化預(yù)處理通過增加高次零項使將多項式的次數(shù)增加到2的冪次。Function transform_better (a:atype):y:ytype;y:=a;迭代過程For k:=1 to lg n do 對數(shù)組進(jìn)行恰當(dāng)?shù)暮喜⒉⒔Y(jié)果放到數(shù)組恰當(dāng)?shù)奈恢?。yyyyback 下面我們將本文介紹的方法與普通的多項式乘法做一個比較。多項式次數(shù)n=100n=1000n