algorithm - 从总和的乘积中找到乘积的总和（多项式）

Question

多项式通常写为幂的总和（或生成器的各种乘积），谷歌给了我很多结果如何从它变成纯和的乘积形式（你可以看到多项式消失的地方） ：

x^2 - 1 = (x + 1) (x - 1)

不过，我正在寻找另一个方向，这要容易得多，但如果天真地完成，计算量仍然很大。

我有一个多项式消失的 n 值数组。我可以以某种方式获得 n log n 中的系数吗？

标签： algorithmpolynomialspolynomial-math

Answer 1

我对此表示怀疑。N log N 是理论上已知的多项式乘法的最佳渐近速度。然而，这个问题似乎需要通过乘以分层多项式展开

step 1) x^2 + Ax + B = (x + a)(x + b), x^2 + Cx + D = (x + c)(x + d), ..., 
step 2) x^4 + Ax^3 + Bx^2 + Cx + D = (x^2 + Ax + B)(x^2 + Cx + D), ...
...
step log N/2)  (polynomial of order N/2) * (polynomial of order N/2)

当多项式的大小变得足够大时，可以开始使用基于 FFT 的方法，或者在此之前使用 Karatsuba。我希望，这种方法介于 O(N^2) 的朴素方法之间，它将基础多项式 (x+a) 与 (x+b)、(x+c) 相乘...和 N log N，可能为 N (log N)^2。