快速傅立叶变换(FFT)学习笔记

经典问题:记$f(x) = \sum_{i=0}^{n} a_i x^i $,$g(x) = \sum_{i=0}^{m} b_i x^i$,其中$1\leq n, m \leq 10^5$,求$f \cdot g (x)$。

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

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

继续阅读