^{N點(diǎn)DFT共需要N2次復(fù)數(shù)乘法和N(N-1)次復(fù)數(shù)加法，共4N2次實(shí)數(shù)乘法和(2N2+2N*(N-1))次實(shí)數(shù)加法。當(dāng)N很大時(shí)，這是一個(gè)非常大的計(jì)算量。}

利用FFT算法之后，任何一個(gè)N為2的整數(shù)冪（即N= 2^M）的DFT，都可以通過M次分解，最后成為2點(diǎn)的DFT來計(jì)算。M次分解構(gòu)成了從x(n)到X(k)的M級(jí)迭代計(jì)算，每級(jí)由N/2個(gè)蝶形運(yùn)算組成。完成一個(gè)蝶形計(jì)算需一次乘法和兩次復(fù)數(shù)加法。因此，完成N點(diǎn)的時(shí)間抽選FFT計(jì)算的總運(yùn)算量為：

復(fù)數(shù)乘法次數(shù)：M*N/2=log₂N*N/2

復(fù)數(shù)加法次數(shù)：M*2*N/2=log₂N*N

大多數(shù)情況下復(fù)數(shù)乘法所花的時(shí)間最多，所以以復(fù)數(shù)乘法的計(jì)算次數(shù)來比較DFT與FFT的效率為：DFT/FFT=2N/log₂N。

愛華網(wǎng)本文地址 » http://www.klfzs.com/a/25101013/178771.html