快速傅里叶变换复杂度

快速傅里叶变换（FFT, Fast Fourier Transform）的复杂度之所以是$O(n\log n)$，是因为FFT算法通过分治法高效地计算离散傅里叶变换（DFT, Discrete Fourier Transform），而DFT的直接计算复杂度为$O(n^2)$。下面详细解释为什么FFT能够将复杂度降低到$O(n\log n)$：

离散傅里叶变换（DFT）

DFT的定义如下，对于一个长度为$n$的序列$x(t)$：
$$X(k)=\sum _{t=0}^{n-1}x(t)\cdot e^{-i\frac{2\pi }{n}kt},k=0,1,\dots ,n-1$$

直接计算每个$X(k)$都需要$O(n)$次乘法和加法，因此计算所有$X(k)$的总复杂度为$O(n^2)$。

快速傅里叶变换（FFT）

FFT利用分治法，将DFT计算过程递归地分解成较小的DFT，从而大幅降低计算复杂度。以下是其基本原理：

1. 分治思想

• 将长度为$n$的DFT分解为两个长度为$n/2$的DFT：
  • 一个计算输入序列的偶数索引项
  • 一个计算输入序列的奇数索引项

2. 递归分解

• 继续递归地分解这些长度为$n/2$的DFT，直到分解到最基本的长度为1的DFT。
• 通过这种分解，每次递归将问题规模减半。

3. 合并步骤

• 合并这些小的DFT结果以得到最终的DFT。

复杂度分析

1. 分解阶段：

   • 每次分解将DFT分成两个规模为$n/2$的子问题，递归深度为$\log n$。

2. 合并阶段：

   • 每个递归层次上，需要$O(n)$次计算来合并子问题的结果。

总的复杂度为：
$$T(n)=2T\left(\frac{n}{2}\right)+O(n)$$

根据主定理（Master Theorem）：

• 对于递归关系$T(n)=aT(n/b)+f(n)$，当$a=2$、$b=2$时，比较$f(n)$和$n^{{\log }_{b}a}$发现$f(n)$和$n$都是$O(n)$，所以：
  $$T(n)=O(n\log n)$$

结论

快速傅里叶变换（FFT）的复杂度为$O(n\log n)$，这是因为FFT通过递归分治法将原本复杂度为$O(n^2)$的DFT计算高效地分解和合并，从而显著降低了计算时间。这使得FFT成为处理频域变换的高效算法，特别适合大规模数据和长时间序列的计算。