“树”用于快速傅立叶变换多项式评估？

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) 

我希望你能看到这个递归过程如何变成一棵树。