本文介绍了n维FFT的计算复杂度的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
在每个维上有m个点的n维FFT的计算复杂度是多少?
What is the computational complexity of the n-dimensional FFT with m points along each dimension?
推荐答案
对于一维FFT，它是O(m log m).
For a 1D FFT it's O(m log m).
对于2D FFT，您必须在每个轴上执行m x 1D FFT，因此O(2 m^2 log m) = O(m^2 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).
现在来我这里转机还为时过早n >= 3，但我想可能是:
It's too early in the morning here to get my head round n >= 3 but I'm guessing it's probably:
O(m^n log m)
这篇关于n维FFT的计算复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！