V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member Sign In
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 2941 days ago, the information mentioned may be changed or developed.
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 就想不到了，尝试两两相乘，但是复杂度并不能降低。
Supplement 1 · Apr 13, 2018
 |
1
wodesuck Apr 13, 2018  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 Apr 13, 2018
可以参考一下我的博客
https://zjuturtle.com/2017/12/26/fft/ |
Select Language