我看到很多文献中，他们说，通过使用FFT可以达到更快的卷积。 我知道，一个人需要从结果获得FFT和再IFFT，但我真的为什么使用FFT可以使卷积快不明白？
Answer 1:
FFT加快对于足够大的过滤器的卷积，因为卷积需要N次乘法（和N-1）次加法用于每个输出样本，相反（2）N ^ 2操作为N个采样的块。
考虑，即一个具有通过将零用于FFT处理的块大小翻倍，每个块需要（2）*（2N）*日志（2N）操作，以执行FFT，2N操作繁殖和再次4N *日志（2N）操作以执行反FFT，存在盈亏平衡点，其中8Nlog2N <= 2N ^ 2。
最根本的原因是：
1）的离散的时域信号可以被表示为频率的总和。
2）在时间域卷积（O（N ^ 2））等于在频域中的频率的乘法（O（N））3）的转变是可逆的
4）存在的信号从时域转换到频域以小于N ^ 2点的操作（这是在“快速傅里叶变换”）的第一架F的方法。
直向前FT是O（N ^ 2），其中每个频域元素F（I）=西格玛F（I）* EXP（I * PI / N）。
然而，FFT是基于实验值（I * PI / N）具有一定的对称性，从而允许计算在奇数/偶数矢量被分裂的观察。 偶数矢量可以在O（N）为代价来计算而奇数矢量需要一半大小的完整FT。 因为这可以被重复，直到N = 2，整体的复杂性将是（成比例）NLOG（N）。
文章来源: Why does FFT accelerate the calculation involved in convolution?
