这是一个创建于 2420 天前的主题，其中的信息可能已经有所发展或是发生改变。
K 个多项式，这 K 个多项式最高次数的和是 S。如何在 O(SlogSlogK)内求出这 K 个多项式的乘积。
O(KSlogS)很容易，只需要对每个多项式做 FFT, O(SlogS)，然后依次逐点相乘，最后 IFFT。总的复杂度就是 O(KSlogS)。但是如何把 K 变成 logK 就想不到了，尝试两两相乘，但是复杂度并不能降低。
O(KSlogS)很容易，只需要对每个多项式做 FFT, O(SlogS)，然后依次逐点相乘，最后 IFFT。总的复杂度就是 O(KSlogS)。但是如何把 K 变成 logK 就想不到了，尝试两两相乘，但是复杂度并不能降低。
第 1 条附言 · 2018-04-13 21:20:02 +08:00
 |
1
wodesuck 2018-04-13 21:59:15 +08:00  2
两两相乘复杂度是 O(SlogSlogK)的。
两个 degree 为 a 和 b 的多项式相乘，是 O((a+b)log(a+b))。考虑做第一次两两相乘，P1 乘 P2，P3 乘 P4，P5 乘 P6...，复杂度就是 O( (d1+d2)log(d1+d2) + (d3+d4)log(d3+d4) + ...) < O((d1+d2+d3+...)logS) = O(SlogS)。乘完后 degree 和不变，下一次两两相乘的复杂度还是 O(SlogS)，一共要做 logK 趟。 |
 |
2
zjuturtle 2018-04-13 22:03:31 +08:00
可以参考一下我的博客
https://zjuturtle.com/2017/12/26/fft/ |
Select Language