DFT和FFT详解（算法导论学习笔记）

代码均为做严格测试，仅供参考

将原问题分解为几个规模较小但类似于原问题的子问题，递归的求解这些子问题。然后再合并这些子问题的解来建立原问题的解。递归求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

分治法在分层递归时都有三个步骤：

两个N次多项式相乘，最直接的复杂度为 O(n2) ，运用傅里叶变换，则可以吧多项式相乘的复杂度转化为 nlog(n)

输入输出均采用系数表达，假设n是2的幂，否则通过添加系数为0的高阶系数。算法准备过程如下：

单位复数根

n次单位复数根是满足 ωn=1 的复数 ω ，这些根正好有n个，分别是 e2πikn(k=0,1,2...n−1)

其中 e2πin 被称作主n次单位根。 ωj∗ωk=ω(k+j)modn

消去引理

对于任意整数n>=0和k>=0，以及d>=0

ωdkdn=ωkn

折半引理

如果n>0为偶数，那么n个n次单位复数根的平方的集合就是n/2个n/2次单位复数根的集合。

对任意非负整数k，我们有 (ωkn)2=ωkn/2

求和引理

对任意整数n>=1和不能被n整除的非负整数k，有

∑n−1j=0(ωkn)j=0

我们希望计算次数界为n的多项式A(x)= ∑n−1j=0ajxj

在n个n次单位复数根处的值，假设A以系数形式给出： a=(a0,a1,a2...an−1) 。接下来对k=0,1,2,..n-1，定义结果 yk :

yk=A(ωkn)=∑n−1j=0ajωkjn

向量 y=(y0,y1,...yn−1) 就是系数向量a=( a0,a1,...,an−1 )的离散傅里叶变换DFT

通过使用快速傅里叶变换的方法，利用复数单位根的特殊性质，我们就可以在 θ(nlgn) 的时间内计算出DFT(a)。

首先分别定义两个新的次数界为n/2的多项式

A[1](x)=a1+a3+...an−1xn/2−1

分别包含了所有偶数下标的系数和奇数下标的系数。

A(x)=A[0](X2)+xA[1](x2)

因而求A（x）在 ω0n,ω1n,…,ωn−1n 处的值得问题转化为：

求次数界为n/2的多项式 A[0](x)+xA[1](x) 在点 (ω0)2…(ωn−1)2 处的取值

用递归方法计算fft的伪代码如下

计算出逆DFT。将fft算法进行修改，将a与y互换，用 ω−1n替换ωn ，并将计算结果的每个数除以n。

T(n)=2T(n/2)+θ(n)=θ(nlgn)

从算法实现上来看，整体的时间复杂度无法进行优化。

但是可以把递归的算法改成迭代的形式实现。从而节省栈中的空间。同时迭代算法可以做到常数上的优化。