大家好
我是一个理学院学生
因为有需要
最近在学傅立叶变换算法的实践
我知道傅立叶变换可以看成对于每一个频率，两个向量在希尔伯特的空间的内积
如此要做成DFT很容易
可是FFT碰到一些递回性质的函数
如呼叫自己的Recursive FFT
我不了解的是他的算法
主要问题可分为两个：
1.证明该Recursive FFT运算结果等价于DFT
2.为什么他可在O(nlogn)时间内完成
参考网址：http://stackoverflow.com/questions/28009590/understanding-the-fft-recursive-algorithm
图片同Introduction to algorithm