n 维 FFT 的计算复杂度
每个维度有 m 个点的 n 维 FFT 的计算复杂度是多少？
What is the computational complexity of the n-dimensional FFT with m points along each dimension?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
对于一维 FFT，其时间复杂度为
O(m log m)。对于 2D FFT，您必须在每个轴上执行 mx 1D FFT，因此
O(2 m^2 log m)=O(m^2 log m)。现在还太早，我无法思考
n >= 3但我猜可能是：For a 1D FFT it's
O(m log m).For a 2D FFT you have to do m x 1D FFTs in each axis so that's
O(2 m^2 log m)=O(m^2 log m).It's too early in the morning here to get my head round
n >= 3but I'm guessing it's probably: