V2EX = way to explore V2EX 是一个关于分享和探索的地方
Sign Up Now For Existing Member Sign In
请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 2936 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