n维快速傅立叶变换的计算复杂度？

Question

我正在尝试编写一些代码来预测在给定的n维数组上执行离散傅立叶变换所需的时间,但我很难理解n维FFT的计算复杂性.

据我了解:

• 长度的矢量的一维FFT N应该采取k*(N*log(N))其中k是一些定时恒定

• 对于M*N矩阵,2D FFT应采用:

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

  因为它需要在每行和每列中采用1D FFT

这如何概括为ND案例？它应该遵循它应该是k*prod(dimensions)*sum(log(dimensions))吗？

Answer 1

如果我们进一步推导出2D,那就很明显了:

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等),复杂性为:

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

从数学上讲,除了旋转因子不同之外,N维FFT与具有尺寸乘积的1-D FFT 相同.因此,自然地说计算复杂性是相同的.