「樹」用於快速傅立葉變換多項式評估？

Question

我想通過使用FFT的分而治之算法來評估多項式A（x）。我基本上把多項式分解成它的奇數根和偶數根，然後對兩個較小的多項式進行遞歸（允許我每次遞歸計算兩次數值）。

爲了想象這一點，我試圖創建一個樹來顯示算法中的多項式路徑。我不確定如何開始 - 有人可以讓我離開嗎？我並不期望完整的樹只是一個簡單的例子，讓我走上正確的道路。

Answer 1

這裏是從Algorithms第2章一個簡單的例子：

A(x) = 3 + 4x + 6x^2 + 2x^3 + x^4 + 10x^5 
    = (3 + 6x^2 + x^4) + x(4 + 2x^2 + 10x^4) 
    = E(x^2) + x*O(x^2) 

其中

E(x) = 3 + 6x + x^2 
O(x) = 4 + 2x + 10x^2 

通知如何多項式的大小已通過因子2縮水？此外，我們可以在x回收評估，因爲-x會產生類似的值。

A(x) = E(x^2) + x*O(x^2) 
A(-x) = E(x^2) - x*O(x^2) 

我希望你能看到這個遞歸過程如何變成一棵樹。