FFT

快速傅里叶变换FFT(Fast Fourier Transform)

傅里叶变换

快速傅里叶变换是一种可以在$O(nlogn)$时间内完成的离散傅里叶变换（DFT）算法。

在算法竞赛中的应用主要是用来加速多项式的乘法。