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

1、多項(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è)很常見的問(wèn)題，在通常的算法中，兩個(gè) 次多項(xiàng)式的乘法需要用 的時(shí)間才能完成。 讓我們先來(lái)看一看這樣的算法是如何進(jìn)行的： . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2、. . . . . 在上面的過(guò)程中，似乎我們覺得這個(gè)算法并沒有做任何多余的事情，因?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è)

3、不超過(guò)n-1次多項(xiàng)式，這個(gè)過(guò)程稱之為插值。引理1（多項(xiàng)式插值的唯一性） 對(duì)于任意n個(gè)點(diǎn)值對(duì)組成的集合, 其中 互不相同，則存在唯一的次數(shù)不超過(guò)n-1的多項(xiàng)式 ，滿足 continue存在性：已知不妨記為XA=YX是范德蒙矩陣，利用行列式的變換可得該矩陣的行列式的值為 因此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

4、個(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ì)在一開始就取為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)化為第一 第三步。continue2continue1continue31.由系數(shù)表示法轉(zhuǎn)化

5、為點(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ī)?？s小一半，這啟示我們可以利用分治

6、的思想通過(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)。back2將點(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è)

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

8、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í)

9、行時(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:ytype;y:=a;迭代過(guò)程For k:=1 to lg n do 對(duì)數(shù)組進(jìn)行恰當(dāng)?shù)暮喜⒉⒔Y(jié)果放到數(shù)組恰當(dāng)?shù)奈恢?。yyyyback 下面我們將本文介紹的方法與普通的多項(xiàng)式乘法做一個(gè)比較。多項(xiàng)式次數(shù)n=100n=1000n