math - 评估多项式？

Question

为什么使用快速傅里叶变换计算具有 n 个点的多项式需要 O(n log n) 时间？我具体谈论的是实现一个分而治之的算法，将多项式 A(x) 分成偶数次幂和奇数次幂，然后使用递归。

Answer 1

令 T(n) 为 FFT 算法在 n 点处计算 n 次多项式所使用的时间。

算法分裂

A(x)=xB(x^2)+C(x^2)，

即分成两个多项式：奇数和偶数系数。例如：3x^3 + 2x^2 + 9x + 7 被拆分为 x(3x^2 + 9) + (2x^2 + 7)。

最初您想在 a、b、c、d 点计算 3x^3 + 2x^2 + 9x + 7。

现在您要在 a ²、 b ²、 c ²、 d ²点计算 3x+9 和 2x+7 。稍后，您将结合它在 a、b、c、d 处获得 3x^3 + 2x^2 + 2x + 7 的值。

关键思想：由于您使用单位根，因此 a ²、 b ²、 c ²、 d ²中的一半值是相同的。假设a ² =c ²和b ² =d ²。

^{因此，您需要在 a 2}、 b ²点计算 3x+2 和 2x+7 。

这意味着您将大小为 N 的实例减少为大小为 N/2 和 O(N) 后处理的两个实例。

FFT 递归地重复这个过程。这是与归并排序相同的递归方程，即 O(N log N) 复杂度。