math - n 维快速傅里叶变换的计算复杂度？

Question

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

据我了解：

• 长度向量的 1D FFTN应该取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 相同，只是维度乘积的大小不同，只是旋转因子不同。所以很自然地得出计算复杂度是一样的。