转：fft算法（快速傅里叶变换算法）

FFT (Fast Fourier Transform) 是一种快速傅里叶变换算法。它是用来将一个信号从时域转换到频域的算法。这个算法通过分治策略，将一个长度为 N 的复数序列分解成 N/2 个长度为 2 的复数序列，然后对这些小的序列分别进行 FFT 计算。

最简单的 FFT 算法是暴力算法，它的时间复杂度是 O(N^2)，对于较长的序列来说运算时间非常长。而 FFT 算法则是通过 Cooley-Tukey 算法，使用了分治思想，将复杂度降低到了 O(N log N)。

使用 FFT 算法进行频域分析可以用来做诸如音频信号处理、图像压缩、通信系统等领域。在信号处理和数学建模中，FFT 是一个非常重要的工具。

FFT 算法有很多种实现方式，其中常用的有:

基于递归的 Cooley-Tukey 算法
基于迭代的 radix-2 算法
基于迭代的 Bluestein 算法

　　这些算法都有各自的优缺点，根据实际应用场景来选择使用。

本文转载自：https://www.teamdoc.cn/archives/2946