简单回顾

快速傅里叶变换，其实是离散傅里叶变换的一种改进算法

我们先来回忆一下离散傅里叶变换（DFT）：

其中ω[m]–––––=e2πimN$\underset{\_}{\omega [m]}=e^{2\pi i\frac{m}{N}}$

对应的矩阵形式为：

不难发现，如果要对N$N$个采样点进行DFT，则时间复杂度为o(N2)$o\left(N^2\right)$

接下来，我们将讲解时间复杂度为o(NlogN)$o\left(N\log N\right)$的FFT算法

为了书写方便，我们记

这样，ω[m]–––––$\underset{\_}{\omega [m]}$就可以改写为

同时，不难发现，

---

FFT推导

FFT的核心思想就是：将DFT的N×N$N\times N$矩阵该写为对几个N2×N2$\frac{N}{2}\times \frac{N}{2}$的矩阵的操作，并用这种方式进行递归，最后得到FFT

首先，我们将(1)$(1)$式拆分为奇数、偶数两部分，即

利用(2)$(2)$式，可将上式改写为

注意我们要使用递归来计算的话，必须把式子写成矩阵形式，那么(3)$(3)$式就可以写为：

我们仔细看看从(3)$(3)$式的求和形式到(4)$(4)$的矩阵矩阵形式，(3)$(3)$式完全是没有问题的，但是(4)$(4)$式却有问题：
(4)$(4)$式中的F–––N2${\underset{\_}{\mathcal{F}}}_{\frac{N}{2}}$是N2×N2$\frac{N}{2}\times \frac{N}{2}$的矩阵，那么与之相乘的矩阵必然有N2$\frac{N}{2}$行，也就是说m≤N2−1$m\le \frac{N}{2}-1$。换句话说，(4)$(4)$式计算出的其实是F–––N${\underset{\_}{\mathcal{F}}}_N$的前半部分。

那么对于m∈[N2,N−1]$m\in [\frac{N}{2},N-1]$的情况，应该如何写出相应的矩阵形式呢？我们将(3)$(3)$式左边的系数写成m+N2$m+\frac{N}{2}$，这样一来，m$m$的取值依然是[0,N2−1]$[0,\frac{N}{2}-1]$。于是就有：

注意到，

带入(5)$(5)$式，有：

写成矩阵的形式，即

结合(4)$(4)$，(6)$(6)$两式，我们可以得到FFT的矩阵递归式：

F–––Nf[m]–––––=FN2feven[m]––––––––––––+ω––[N,−m]FN2fodd[m]–––––––––––$${\underset{\_}{\mathcal{F}}}_N\underset{\_}{f[m]}=\underset{\_}{{\mathcal{F}}_{\frac{N}{2}}{f}_{even}[m]}+\underset{\_}{\omega }[N,-m]\underset{\_}{{\mathcal{F}}_{\frac{N}{2}}{f}_{odd}[m]}$$

F–––Nf[m+N2]––––––––––=FN2feven[m]––––––––––––−ω––[N,−m]FN2fodd[m]–––––––––––$${\underset{\_}{\mathcal{F}}}_N\underset{\_}{f[m+\frac{N}{2}]}=\underset{\_}{{\mathcal{F}}_{\frac{N}{2}}{f}_{even}[m]}-\underset{\_}{\omega }[N,-m]\underset{\_}{{\mathcal{F}}_{\frac{N}{2}}{f}_{odd}[m]}$$

其中m∈[0,N2−1]$m\in [0,\frac{N}{2}-1]$，第一个等式为前N2$\frac{N}{2}$项，第二个等式为后N2$\frac{N}{2}$项

这个式子很明确地告诉我们：

FFT实际上就是将DFT的矩阵，通过一定的方式进行拆分，从而降低时间复杂度的一种算法

---

FFT的时间复杂度

有了递归式，我们就可以来算时间复杂度。

方便起见，我们将矩阵写成[n×m]$\left[n\times m\right]$，其中n$n$，m$m$分别表示行列数。并设N=2k$N=2^k$

1. 那么前N2$\frac{N}{2}$项就可以写成

   [N2×N2]+CN[N2×N2]$$\left[\frac{N}{2}\times \frac{N}{2}\right]+C_N\left[\frac{N}{2}\times \frac{N}{2}\right]$$

   其中CN$C_N$为一常数，该式花费的时间为o([N2×N2])+1+o([N2×N2])$o\left(\left[\frac{N}{2}\times \frac{N}{2}\right]\right)+1+o\left(\left[\frac{N}{2}\times \frac{N}{2}\right]\right)$，其中1$1$就是常数相乘的操作

   对于后N2$\frac{N}{2}$项，由于对应的矩阵、常数都是相同的，因此只需要额外进行1$1$次操作即可

2. 我们把n×n$n\times n$的矩阵记为[n]$[n]$，并把m$m$个不同的常数相乘记为Cm$C^m$，则如下图

   

   注意图中1+2⋯+2k−1$1+2\cdots +2^{k-1}$是前文提到的后N2$\frac{N}{2}$项的计算量，需要进行累加计算。到最后一项时，它的累积值为2n−1$2^n-1$

不难发现，递归至最后一项时，总计算次数应为（图中最后一行以及虚线框内）：

简单解释一下上式

• 前面的各项排列组合表示的是各个常数Cx$C^x$所需的计算时间，如系数Ck$C^k$只在最后一个一阶矩阵前出现，计算量为k⋅(kk)=k$k\cdot (\genfrac{}{}{0ex}{}{k}{k})=k$次，又如系数C1$C^1$必然会出现(1k)$(\genfrac{}{}{0ex}{}{1}{k})$次，因此计算量为1⋅(1k)=k$1\cdot (\genfrac{}{}{0ex}{}{1}{k})=k$；
• 第一个2n$2^n$表示的是所有1$1$阶矩阵的计算时间总和；
• 2n−1$2^n-1$表示的是后N2$\frac{N}{2}$项的计算量；
• 第二个2n$2^n$表示的是计算所有+$+$（加号）花费的时间

(7)$(7)$式不容易计算，但是我们可以直观地估计一下，对于前面的阶乘项，最多用时为k$k$次，最少为1$1$次，那么不严格地估计一下，我们取平均k+12$\frac{k+1}{2}$次，这样共需要计算N$N$次（有N$N$个[1]$[1]$），因此时间复杂度应为：

因此，FFT的时间复杂度就是