作者watermeter (水表)
看板C_and_CPP
标题[问题] Recursive FFT为什麽可以在O(nlogn)时间
时间Thu Mar 10 12:45:17 2016
大家好
我是一个理学院学生
因为有需要
最近在学傅立叶变换演算法的实践
我知道傅立叶变换可以看成对於每一个频率，两个向量在希尔伯特的空间的内积
如此要做成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://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1457585119.A.921.html
1F：推 johnpage: 离散数学 03/10 14:49
2F：→ coal511464: 有些np问题 可以透过hash table来达到假nln时间 03/10 20:28
3F：→ coal511464: 你可以看看 0/1 背包问题 03/10 20:28
4F：→ coal511464: 但不确定你这实际怎麽做 03/10 20:29
5F：推 PhysiAndMath: 线代启示录+快速傅立叶 喂狗 03/11 23:48