算法合集之多項(xiàng)式乘法(已修改)
2025-10-25 18:36 本頁(yè)面
【正文】 張家琳 復(fù)旦大學(xué)附屬中學(xué) 引言 多項(xiàng)式是最基本的數(shù)學(xué)工具之一，由于其形式簡(jiǎn)單，且易于用計(jì)算機(jī)對(duì)其進(jìn)行各種計(jì)算，在當(dāng)今的社會(huì)中應(yīng)用越來越廣。不僅在像 Maple這樣的數(shù)學(xué)軟件中有著舉足輕重的作用，在工程、信息等諸多領(lǐng)域中都有著廣闊的應(yīng)用。 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? ? ? ? ? ? ? ? 下面我們給出幾個(gè)多項(xiàng)式逼近的例子： 多項(xiàng)式的基本運(yùn)算 加法運(yùn)算 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?? ? ? ? ? ? 求值運(yùn)算 乘法運(yùn)算 普通的多項(xiàng)式乘法運(yùn)算 多項(xiàng)式乘法是一個(gè)很常見的問題，在通常的算法中，兩個(gè) 次多項(xiàng)式的乘法需要用 的時(shí)間才能完成。 n 2()On 讓我們先來看一看這樣的算法是如何進(jìn)行的： 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?? ? ???? ? ? ? ? ? ??? 在上面的過程中，似乎我們覺得這個(gè)算法并沒有做任何多余的事情，因?yàn)槲覀儽仨毧紤]每一組 ,它們的乘積對(duì)最終的結(jié)果都會(huì)產(chǎn)生影響。而且我們不能通過調(diào)整計(jì)算順序從根本上降低算法時(shí)間復(fù)雜度，至多只能使其常數(shù)因子稍小一些。 ijab 如果我們不能跳出以上思維的局限，我們就不可能在根本上降低算法的時(shí)間復(fù)雜度。 讓我們首先換一個(gè)角度來考察多項(xiàng)式。 多項(xiàng)式的點(diǎn)值表示法 首先讓我們來看多項(xiàng)式的另一種表示方法：點(diǎn)值表示法 ,即用 （ 其中 ， 互不相同 ） 來表示一個(gè)不超過 次多項(xiàng)式 。 0 0 1 1 2 , 2 1 1( , ) , ( , ) , ( ) , . . . . . . , ( , )nnx y x y x y x y??( ) ,i i if x y x?1n? 給定一個(gè)多項(xiàng)式 ， 要給出 n組點(diǎn)值對(duì)最簡(jiǎn)單的方法是任選 n個(gè)互不相同的 xi， 依次求出多項(xiàng)式在這 n個(gè)點(diǎn)的值 。 用 n個(gè)點(diǎn)值對(duì)也可以唯一確定一個(gè)不超過 n1次多項(xiàng)式 ，這個(gè)過程稱之為 插值 。 引理 1（多項(xiàng)式插值的唯一性） 對(duì)于任意 n個(gè)點(diǎn)值對(duì)組成的集合 , 其中 互不相同 ， 則存在唯一的次數(shù)不超過 n1的多
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1