我正在尝试获得快速傅里叶变换（IFFT）逆变换的计算复杂度。我已经知道 n 位置的一维向量是 O(nlogn)，但就我而言，首先我有两个 FFT 的乘积。然后，我要计算它对应的IFFT，并得到它的计算复杂度。
X(w) 和 Q(w) 都是一维向量，并且都有 n 个位置。
简单来说，如果X(w)和Q(w)是FFT，考虑到它们的乘积仍然是FFT（根据卷积性质），相应的IFFT的计算复杂度是多少？
仍然是 O(N log N)。 ifft 不关心如何获取数据，逐元素乘法是 O(N)。