经典问题:记 f(x)=i=0naixig(x)=i=0mbixi,其中1n,m105,求fg(x)

显然如果我们做朴素的多项式乘法,时间复杂度是 O(nm) 的。我们可以使用快速傅立叶变换(FFT)在 O(clogc) 的时间内解决此问题,其中 c 是不小于 n+m 的最小的 2 的幂。

本文是笔者学习FFT的笔记和一些思考,不推荐作为教程食用。

Read more »
0%