n维FFT的计算复杂度 [英] Computational complexity of the FFT in n dimensions

问题描述

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

What is the computational complexity of the n-dimensional FFT with m points along each dimension?

推荐答案

对于一维FFT，它是O(m log m).

For a 1D FFT it's O(m log m).

对于2D FFT，您必须在每个轴上执行m x 1D FFT，因此O(2 m^2 log m) = O(m^2 log m).

For a 2D FFT you have to do m x 1D FFTs in each axis so that's O(2 m^2 log m) = O(m^2 log m).

现在来我这里转机还为时过早n >= 3，但我想可能是:

It's too early in the morning here to get my head round n >= 3 but I'm guessing it's probably:

O(m^n log m)

这篇关于n维FFT的计算复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！