第三节、FFT
注：本节有相当部分文字来自算法导论中文版第二版以及维基百科。
在具体介绍FFT之前，我们得熟悉知道折半定理是怎么一回事儿：如果n>0且n为偶数，那么，n个n次单位复根的平方等于n/2个n/2个单位复根。我们已经知道，通过使用一种称为快速傅里叶变换（FFT）的方法，可以在O（n*logn）的时间内计算出DFTn（a），而若采用直接的方法复杂度为O（n^2）。FFT就是利用了单位复根的特殊性质。
你将看到，FFT方法运用的策略为分治策略，所谓分治，即分而治之。两个多项式A（x）与B（x）相乘的过程中，FFT用A（x）中偶数下标的系数与奇数下标的系数，分别定义了两个新的次数界为n/2的多项式A[0]（x）和A[1]（x）：
A[0](x) =a0 +a2x +a4x2 +··· +an-2xn/2-1,
A[1](x) =a1 +a3x +a5x2 +··· +an-1xn/2-1.
注意，A[0]包含了A中所有偶数下标的系数（下标的相应二进制数的最后一位为0），而A[1]包含A中所有奇数下标的系数（下标的相应二进制数的最后一位为1）。有下式：
这样，求A（x）在
处的问题就转换为：
1）求次数界为n/2的多项式A[0]与A[1]在点
的值
2）将上述结果进行组合。
下面，我们用N次单位根WN来表示
。
为了简单起见，我们下面设待变换序列长度n = 2r。 根据上面单位根的对称性，求级数
时，可以将求和区间分为两部分：
Fodd(k) 和 Feven(k)是两个分别关于序列
奇数号和偶数号序列N/2点变换。由此式只能计算出yk的前N/2个点，对于后N/2个点，注意Fodd(k) 和 Feven(k) 都是周期为N/2的函数，由单位根的对称性，于是有以下变换公式：
-
-
。
-
-
这样，一个N点变换就分解成了两个N/2点变换，照这样可继续分解下去。这就是库利-图基快速傅里叶变换算法的基本原理。此时，我们已经不难分析出此时算法的时间复杂度将为O(NlogN)。
ok，没想到，本文之中还是出现了这么多的公式（没办法，搞这个FFT就是个纯数学活儿。之前买的一本小波与傅里叶分析基础也是如此，就是一本数学公式和定理的聚集书。不过，能看懂更好，实在无法弄懂也只权当做个稍稍了解）。
好了，下面，咱们来简单理解下FFT中的蝶形算法，本文将告结束。如下图所示：
有人这样解释蝶形算法：对于N（2的x次方）点的离散信号，把它按索引位置分成两个序列，分别为0，2，4，....，2K（记为A）和1，3，5，....，2K-1（记为B），由傅立叶变换可以推出N点的傅立叶变换前半部分的结果为A+B*旋转因子，后半部分的结果为A-B*旋转因子。于是求N点的傅立叶变换就变成分别求两个N/2点序列的傅立叶变换，对每一个N/2点的序列，递归前面的步骤，直到只有两点的序列，就只变成简单的加减关系了。把这些点的加减关系用线连接，看上去就是个蝶形。ok，更多可参考算法导论第30章。
举一个例子，我们知道，4X4的矩阵运算如果按常规算法的话仍要进行64次乘法运算和48次加法，这将耗费较多的时间，于是在H.264中，有一种改进的算法（蝶形算法）可以减少运算的次数。这种矩阵运算算法构造非常巧妙，利用构造的矩阵的整数性质和对称性，可完全将乘法运算转化为加法运算。如下图所示：
