[問題] Recursive FFT為什麼可以在O(nlogn)時間
大家好
我是一個理學院學生
因為有需要
最近在學傅立葉變換演算法的實踐
我知道傅立葉變換可以看成對於每一個頻率，兩個向量在希爾伯特的空間的內積
如此要做成DFT很容易
可是FFT碰到一些遞迴性質的函數
如呼叫自己的Recursive FFT
我不了解的是他的演算法
主要問題可分為兩個：
1.證明該Recursive FFT運算結果等價於DFT
2.為什麼他可在O(nlogn)時間內完成
參考網址：http://stackoverflow.com/questions/28009590/understanding-the-fft-recursive-algorithm
圖片同Introduction to algorithm
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.121.251
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1457585119.A.921.html
推
03/10 14:49, , 1F
03/10 14:49, 1F
→
03/10 20:28, , 2F
03/10 20:28, 2F
→
03/10 20:28, , 3F
03/10 20:28, 3F
→
03/10 20:29, , 4F
03/10 20:29, 4F
推
03/11 23:48, , 5F
03/11 23:48, 5F