在 n 维情况下，FFT 的计算复杂度。

Question

n维FFT在每个维度上有m个点的计算复杂度是多少？

- Dan

---

可能是计算n维快速傅里叶变换的复杂度？的重复问题。 - user719662

Answer 1

对于1D 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)

- Paul R

---

没错，但实际上这个复杂度是O(2^n m^n log m)，我只是想指出系数也会随着n的增长呈指数级增长。 - GeorgeWilson