math - 逆 FFT 的计算复杂度

Question

我正在尝试计算 ifft 的计算复杂度，我知道它是 N*1 维度的 NlogN 信号。但是我有两个信号的乘积，然后我想得到 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)。