每个维度有 m 个点的 n 维 FFT 的计算复杂度是多少？
最佳答案
对于一维 FFT，它是O(m log m)。
对于 2D FFT，您必须在每个轴上执行 m x 1D FFT，因此 O(2 m^2 log m) = O(m^2 log m).
现在还太早，我无法思考 n >= 3 但我猜可能是:
O(m^n log m)
关于math - n 维 FFT 的计算复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6514861/