它是根據離散傅氏變換的奇、偶、虛、實等特性,對離散傅立葉變換的演算法進行改進獲得的.設x(n)為N項的複數序列,由DFT變換,任一X（m）的計算都需要N次複數乘法和N-1次複數加法,而一次複數乘法等於四次實數乘法和兩次實數加法,一次複數加法等於兩次實數加法,即使把一次複數乘法和一次複數加法定義成一次“運算”（四次實數乘法和四次實數加法）,那麼求出N項複數序列的X（m）,即N點DFT變換大約就需要N^2次運算.當N=1024點甚至更多的時候,需要N2=1048576次運算,在FFT中,利用WN的週期性和對稱性,把一個N項序列（設N=2k,k為正整數）,分為兩個N/2項的子序列,每個N/2點DFT變換需要（N/2）2次運算,再用N次運算把兩個N/2點的DFT變換組合成一個N點的DFT變換.這樣變換以後,總的運算次數就變成N+2（N/2）2=N+N2/2.繼續上面的例子,N=1024時,總的運算次數就變成了525312次,節省了大約50%的運算量.而如果我們將這種“一分為二”的思想不斷進行下去,直到分成兩兩一組的DFT運算單元,那麼N點的DFT變換就只需要Nlog2N次的運算,N在1024點時,運算量僅有10240次,是先前的直接演算法的1%,點數越多,運算量的節約就越大,這就是FFT的優越性.
它是根據離散傅氏變換的奇、偶、虛、實等特性,對離散傅立葉變換的演算法進行改進獲得的.設x(n)為N項的複數序列,由DFT變換,任一X（m）的計算都需要N次複數乘法和N-1次複數加法,而一次複數乘法等於四次實數乘法和兩次實數加法,一次複數加法等於兩次實數加法,即使把一次複數乘法和一次複數加法定義成一次“運算”（四次實數乘法和四次實數加法）,那麼求出N項複數序列的X（m）,即N點DFT變換大約就需要N^2次運算.當N=1024點甚至更多的時候,需要N2=1048576次運算,在FFT中,利用WN的週期性和對稱性,把一個N項序列（設N=2k,k為正整數）,分為兩個N/2項的子序列,每個N/2點DFT變換需要（N/2）2次運算,再用N次運算把兩個N/2點的DFT變換組合成一個N點的DFT變換.這樣變換以後,總的運算次數就變成N+2（N/2）2=N+N2/2.繼續上面的例子,N=1024時,總的運算次數就變成了525312次,節省了大約50%的運算量.而如果我們將這種“一分為二”的思想不斷進行下去,直到分成兩兩一組的DFT運算單元,那麼N點的DFT變換就只需要Nlog2N次的運算,N在1024點時,運算量僅有10240次,是先前的直接演算法的1%,點數越多,運算量的節約就越大,這就是FFT的優越性.