Question

离散傅里叶变换（DFT）需进行N^2次乘法，N(N-1)次加法这是怎么算来的？哪位举个简单的如N=3的例子 谢谢

就是问DFT的计算次数为什么是N^2+N(N-1)次

Answer 1

偶尔碰到你的问题，已经很长时间了，不知道你还是不是需要，要不留给需要的人也好。

其实这个道理很简单，不用举例子的（敲公式太麻烦了）

看定义式：

X(K)一共是 N个点，每完成一个点的DFT,假设K=1时，把后面的求和式子展开，一共是N个式子，那就是N-1次加法喽，每个式子都是复数相乘，必然是N次复数乘法了。意思就是计算一次DFT,就需要N次复数乘法和N-1次复数加法，那么X(K)一共是N个点，计算N次，就需要N*N+N*（N-1）次运算喽，其中N*N次乘法，N*(N-1)次加法。

因为计算量相当大，所以才出现了FFT...

Answer 2

没看懂题目