Вычислительная сложность обратного FFT

Question

Я пытаюсь вычислить вычислительную сложность ifft, я знаю, что это NlogN для измерения N * 1, сигнала. Но у меня есть продукт двух сигналов, тогда я хочу получить ifft, а затем вычислить вычислительную сложность. Так просто, если X (w) и Q (w) являются преобразованием Фурье двух сигналов времени, то что такое вычислительная сложность их произведения.
Примечание: X (w) и Q (w) имеют одинаковый размер (N * 1).
ifft (X (w) * Q (w)) = ???

Answer 1

Это все еще O (N log N). В ifft все равно, как вы получаете данные, а умножение по элементам - O (N).