如果我们进一步推导您的2D推论，就会很清楚:

If we take your derivation of 2D a bit further, it becomes clear:

N*(k*M*log(M)) + M*(k*N*log(N)) = k*M*N*(log(M)+log(N))

成为:

                                = k*M*N*(log(M*N))

对于N个维度(A，B，C等)，复杂度为:

For N dimensions (A,B,C, etc...), the complexity is:

O( A*B*C*... * log(A*B*C*...) )

从数学上讲，N维FFT与一维FFT的尺寸乘积大小相同，只是

Mathematically speaking, an N-Dimensional FFT is the same as a 1-D FFT with the size of the product of the dimensions, except that the twiddle factors are different. So it naturally follows that the computational complexity is the same.