我想知道我们计算 DFT 的速度是否存在理论上的限制。我们都知道 FFT 在时间内执行。但是，这是某种下限吗？
可能还有更快的算法尚未被发现，但我们目前还不知道它们是否更快，或者这是一个无法跨越的神圣边界？
编辑：显然这是 CS 中一个已知的未解决问题（感谢@John）。
那么，问题的细节是什么？从哪里开始尝试改进？
是O ( N日志ñ)O(NlogN)FFT 速度是我们能达到的最快速度？
信息处理
fft
傅里叶变换
自由度
2022-02-05 11:35:21
2个回答
虽然一般问题在理论计算机科学中仍然是一个悬而未决的问题，但有一些（随机）算法称为稀疏快速傅立叶变换，当您只关心几个 DFT 系数时，它可以将 DFT 逼近到某个逼近因子。
您可以在这些论文和相关论文中找到一些详细信息（可在此处下载）：
哈萨涅、海瑟姆等人。“近乎最优的稀疏傅里叶变换。” 第44届计算理论研讨会论文集。ACM，2012 年。
哈萨涅、海瑟姆等人。“稀疏傅里叶变换的简单实用算法。” 第二十届 ACM-SIAM 离散算法年度研讨会论文集。暹罗，2012。
计算范式中的大多数“分而治之”算法都使用 O(NlogN) 作为下限。它在空间和时间复杂度之间提供了某种平衡。排序是分治法的应用之一。FFT 也使用相同的“分而治之”方法计算。
O(N) 算法虽然速度很快，但需要更多空间（内存）进行计算。进行改进的唯一方法是使用不同的算法（如 karatsuba 乘法、吠陀乘法等）来提高乘法的速度。
其它你可能感兴趣的问题