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/ |