推 johnpage: 離散數學 03/10 14:49
→ coal511464: 有些np問題 可以透過hash table來達到假nln時間 03/10 20:28
→ coal511464: 你可以看看 0/1 背包問題 03/10 20:28
→ coal511464: 但不確定你這實際怎麼做 03/10 20:29
推 PhysiAndMath: 線代啟示錄+快速傅立葉 餵狗 03/11 23:48
大家好
我是一個理學院學生
因為有需要
最近在學傅立葉變換演算法的實踐
我知道傅立葉變換可以看成對於每一個頻率，兩個向量在希爾伯特的空間的內積
如此要做成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