算法合集之多項(xiàng)式乘法-資料下載頁
2024-10-18 18:36本頁面
【正文】 2 / 2( ) ( ) * ( )k k k kn n n na a a? ? ? ?? ? ? ???遞歸結(jié)束后再將 a中每一個(gè)數(shù)除以 n。 多項(xiàng)式乘法的算法流程 問題： f(x),g(x)是兩個(gè) n1次的多項(xiàng)式 ， 已知 f(x)g(x)的系數(shù)表示 ， 求出 r(x)=f(x)*g(x)的系數(shù)表示 。 算法流程： 1. 預(yù)處理：通過加入 n1個(gè)值為 0的高價(jià)次數(shù)，使 f(x)g(x)的次數(shù)增加到 2n2。這是為了使點(diǎn)值對(duì)的個(gè)數(shù)足夠能夠唯一確定 r(x)。 2. 點(diǎn)值：利用分治的方法，通過函數(shù) transform求出 f(x)與g(x)在 1的 2n1次單位根處的值。 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é)果 。 以上第 第 3步的執(zhí)行時(shí)間都是 O(n)，第 第 4步的執(zhí)行時(shí)間都是 O(n log n)。 算法改進(jìn) 在函數(shù) transform中，我們是用遞歸的方式來求解，我們對(duì) n=8的情況來具體演示一下遞歸調(diào)用的過程。 0 1 2 3 4 5 6 7( , , , , , , , )a a a a a a a a1 3 5 7( , , , )a a a a3()a1()a37( , )aa15( , )aa5()a 7()a0 2 4 6( , , , )a a a a2()a26( , )aa04( , )aa0()a 6()a4()a3()a1()a37( , )aa15( , )aa5()a 7()a2()a26( , )aa04( , )aa0()a 6()a4()a 但是遞歸的方法對(duì)空間的要求很高 ， 從函數(shù) transform中可以看到每次遞歸調(diào)用時(shí)都需要新的系數(shù)數(shù)組傳入遞歸過程內(nèi)部 。 而通過剛才的演示 ， 我們發(fā)現(xiàn)我們也可以用從底向上迭代的方法來進(jìn)行 。 0 1 2 3 4 5 6 7( , , , , , , , )a a a a a a a a0 2 4 6( , , , )a a a a 1 3 5 7( , , , )a a a a迭代算法的具體實(shí)現(xiàn)過程 初始化 預(yù)處理 通過增加高次零項(xiàng)使將多項(xiàng)式的次數(shù)增加到2的冪次。 Function transform_better (a:atype):y:ytype。 y:=a。 迭代過程 For k:=1 to lg n do 對(duì)數(shù)組進(jìn)行恰當(dāng)?shù)暮喜⒉⒔Y(jié)果放到數(shù)組恰當(dāng)?shù)奈恢谩? 0 1 2 3 4 5 6 7( , , , , , , , )a a a a a a a a1 3 5 7( , , , )a a a a3()a1()a37( , )aa15( , )aa5()a 7()a0 2 4 6( , , , )a a a a2()a26( , )aa04( , )aa0()a 6()a4()a y y y y back 0122,??01?01? 01?01? 01?01?01?01?0122,?? 0122,??0122,??0 1 2 34 4 4 4, , ,? ? ? ?0 1 2 34 4 4 4, , ,? ? ? ?0 1 2 3 4 5 6 78 8 8 8 8 8 8 8, , , , , , ,? ? ? ? ? ? ? ? 下面我們將本文介紹的方法與普通的多項(xiàng)式乘法做一個(gè)比較。 多項(xiàng)式次數(shù) n=100 n=1000 n=10000 n=20210 n=30000 普通方法 時(shí)間 (s) 30 點(diǎn)值方法 時(shí)間 (s) 精度 (real) 10~11位 10~11位 9~10位 8~9位 8~9位 測試環(huán)境： PIII 500 128M RAM FreePascal
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1