多項式到n次冪算法

哪個是做多項式冪的最好方法？它是遵循多項式定理（wikipedia），它採用O（？）或FFT（快速傅立葉變換），然後用O（（N * log（N））^ 2）進行反FFT。多項式到n次冪算法

你可以做一個例子嗎？你想要計算什麼？ – duedl0r

最好以什麼方式？問題的大小和順序是什麼？可能沒有最好的答案;例如，對於一個小問題，直接的蠻力乘法可能比使用基於FFT的算法更快，因爲算法的初始設置不值得加速。但對於巨大的問題，FFT方法肯定值得... – twalberg

爲什麼你認爲FFT +反FFT是O（（N log（N））^ 2）？兩者都是O（N log（N）），所以它們的和也是O（N log（N））。 – sebii

FFT如果您需要頻繁地執行或使用大的多項式。天真的乘法算法是O（N^2），而FFT是O（N log（N））。

下面是一些巧妙的應用程序更好的解釋：JeffE FFT

2013-12-24 06:15:07 sebii

在兩種情況下，如果要計算p（z）^ k，則N = k * deg（p）。如果要計算具有p的根的冪作爲其根的多項式，請使用Dandelin-Graeffe迭代或非二進制冪，即根和多項式係數的冪和之間的牛頓恆等式。 – LutzL

回答