算法合集之多項式乘法(已修改)
2025-10-25 18:36 本頁面
【正文】 張家琳 復旦大學附屬中學 引言 多項式是最基本的數(shù)學工具之一，由于其形式簡單，且易于用計算機對其進行各種計算，在當今的社會中應用越來越廣。不僅在像 Maple這樣的數(shù)學軟件中有著舉足輕重的作用，在工程、信息等諸多領域中都有著廣闊的應用。 2 3 41l n ( 1 ) ( 1 )2 3 4nnx x x xxxn?? ? ? ? ? ? ? ? ?3 5 7 2 1s i n ( 1 )3 ! 5! 7 ! ( 2 1 ) !nnx x x xxxn?? ? ? ? ? ? ? ??2 4 6 2c o s 1 ( 1 )2 ! 4 ! 6 ! ( 2 ) !nnx x x xxn? ? ? ? ? ? ? ? 下面我們給出幾個多項式逼近的例子： 多項式的基本運算 加法運算 20 1 2()nnf x a a x a x a x? ? ? ? ?0 1 2 1* ( * ( * ( * ) ) )nna x a x a x a x a?? ? ? ? ? ? 求值運算 乘法運算 普通的多項式乘法運算 多項式乘法是一個很常見的問題，在通常的算法中，兩個 次多項式的乘法需要用 的時間才能完成。 n 2()On 讓我們先來看一看這樣的算法是如何進行的： 11 1 0...nnnna x a x a x a??? ? ? ?11 1 0...nnnnb x b x b x b??? ? ? ?*10 1 0 1 0 0 0...nnnna b x a b x a b x a b??? ? ? ?121 1 1 1 1 1 0...nnnna b x a b x a b x a b x? ?? ? ? ?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 10...n n nn n n na b x a b x a b x?? ? ?211 1 0 0 1 0 010.. .. .. .. . ( )nnn n nn n n k k n k kkka b x a b x a b x a b a b x a b?? ? ???? ? ? ? ? ? ??? 在上面的過程中，似乎我們覺得這個算法并沒有做任何多余的事情，因為我們必須考慮每一組 ,它們的乘積對最終的結果都會產生影響。而且我們不能通過調整計算順序從根本上降低算法時間復雜度，至多只能使其常數(shù)因子稍小一些。 ijab 如果我們不能跳出以上思維的局限，我們就不可能在根本上降低算法的時間復雜度。 讓我們首先換一個角度來考察多項式。 多項式的點值表示法 首先讓我們來看多項式的另一種表示方法：點值表示法 ,即用 （ 其中 ， 互不相同 ） 來表示一個不超過 次多項式 。 0 0 1 1 2 , 2 1 1( , ) , ( , ) , ( ) , . . . . . . , ( , )nnx y x y x y x y??( ) ,i i if x y x?1n? 給定一個多項式 ， 要給出 n組點值對最簡單的方法是任選 n個互不相同的 xi， 依次求出多項式在這 n個點的值 。 用 n個點值對也可以唯一確定一個不超過 n1次多項式 ，這個過程稱之為 插值 。 引理 1（多項式插值的唯一性） 對于任意 n個點值對組成的集合 , 其中 互不相同 ， 則存在唯一的次數(shù)不超過 n1的多
教學課件相關推薦
鄂ICP備17016276號-1