qq名字网离散傅里叶变换
所谓离散傅里叶变换就是以为基函数来对（以为周期的）周期函数进行插值．具体地，如果已经知道一个函数在的个等分点（）上的值，我们就需要确定一组数（）使得函数
很多时候，为了体现对称性，一般把的离散傅里叶变换写成
接下来我们说的离散傅里叶变换都是指系数是的那些式子．
离散傅里叶变换在理论上是十分简单的，但是分析其计算量就会发现在实际操作上并不容易．因为每计算一个就要计算次乘法再把个复数相加，于是求出全部的就需要次乘法．即使计算机出现以后，当较大时计算所花费的代价也很大．20世纪60年代提出了快速算法，使得计算离散傅里叶变换的复杂度由降低到了．
下面介绍快速傅里叶变换．方便起见，记，，那么离散傅里叶变换就可以写成
在Mathematica中，我们可以这样实现：
在上面的例子中，递归定义的函数FFT表示快速傅里叶变换，它接收的参数是上文中的，而我们实际要计算的是的离散傅里叶变换，所以在计算这个数的离散傅里叶变换时，提供给FFT的参数应该是Range[16]/Sqrt[16]．
