Вычислительная сложность n-мерного быстрого преобразования Фурье?

Я пытаюсь написать немного кода, который будет прогнозировать время, затраченное на выполнение дискретного преобразования Фурье на данном n-мерном массиве, но я изо всех сил пытаюсь разобраться в вычислительной сложности n-мерного FFTs.

Как я понимаю:

  • 1D БПФ вектора длины N должен принимать k*(N*log(N)), где k - некоторая постоянная времени

  • Для матрицы M*N двумерный БПФ должен принимать:

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

    поскольку для каждой строки и столбца требуется 1D БПФ,

Как это обобщается на случай ND? Из этого следует, что это должно быть k*prod(dimensions)*sum(log(dimensions))?

Ответы

Ответ 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-мерный БПФ является таким же, как и одномерный БПФ с размером произведения размеров, за исключением того, что факторы twiddle другой. Поэтому естественно следует, что вычислительная сложность одинакова.