快速傅里叶变换(Fast Fourier Transform, FFT in short)

网上关于FFT的介绍很多,算导也有相关算法描述,但是原来读的时候很清楚,可是读完也不知道怎么实现.这次在机房膜拜了大神的代码后自己琢磨了一个初等数学描述的证明,并得到了一个比较简洁的实现方法.主要是For OIer,所以给出的证明是简洁而不失于严谨性的(融合了算导, 维基百科的证明和自己的理解).