algorithm - 多项式乘法的复杂性

Question

我正在尝试将两个多项式 A 和 B 相乘，每个多项式都为 'd'，其中基本上有两个运算，即乘法和加法。为了得到一个输出多项式'C'，总共需要多少次操作？我搜索了很多，我假设总乘法运算将是“d^2”，总加法将是“2d-1”。因此总操作数将是 (2d-1)*(d^2)。这是真的？还是假的？如何？请建议....

Answer 1

多项式d具有d+1系数。所以一个简单的实现需要(d+1)^2乘法。对于非常大d的操作数量可以减少到O( d log(d))使用 FFT。