大家好
我是一個理學院學生
因為有需要
最近在學傅立葉變換演算法的實踐
我知道傅立葉變換可以看成對於每一個頻率，兩個向量在希爾伯特的空間的內積
如此要做成DFT很容易
可是FFT碰到一些遞迴性質的函數
如呼叫自己的Recursive FFT
我不了解的是他的演算法
主要問題可分為兩個：
1.證明該Recursive FFT運算結果等價於DFT
2.為什麼他可在O(nlogn)時間內完成
參考網址：http://stackoverflow.com/questions/28009590/understanding-the-fft-recursive-algorithm
圖片同Introduction to algorithm