Какова вычислительная сложность n-мерного БПФ с m точками вдоль каждого измерения?
Для 1D БПФ это O(m log m).
O(m log m)
Для двумерного БПФ необходимо выполнить m x 1D БПФ по каждой оси, так что это O(2 m^2 log m) = O(m^2 log m).
O(2 m^2 log m)
O(m^2 log m)
Слишком рано утром, чтобы обдумать мою мысль n >= 3 но я предполагаю, что это, вероятно:
n >= 3
O(m^n log m)