逆FFT的计算复杂度

Question

逆FFT的计算复杂度

3

我尝试计算ifft的计算复杂度，对于一个N*1维信号，我知道它是NlogN。但是我有两个信号的乘积，然后我想得到ifft，然后计算计算复杂度。简单来说，如果X(w)和Q(w)是两个时间信号的傅里叶变换，那么它们的乘积的计算复杂度是多少。
注意：X(w)和Q(w)具有相同的（N*1）大小。
ifft(X(w)*Q(w))= ???

（说明：ifft是逆傅里叶变换的缩写，计算复杂度是指执行算法所需的计算资源的数量，通常用时间复杂度表示，即算法执行所需的时间与问题规模之间的关系）

- SAH

4

应该在程序员社区上提问。 - Daniel Mann

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Evan · Accepted Answer

它仍然是O(N log N)。ifft并不在乎你如何获取数据，逐元素相乘是O(N)。