FFT的全稱是快速傅立葉變換，在計算卷積的時候特別快，時間複雜度為O(n*log(n))。另外還有NTT（快速數論變換）也可以計算卷積，而且沒有浮點數精度損失。

Fast Fourier Transform (FFT)，快速傅立葉變換。

在FFT之前，我們一定知道離散傅立葉變換Discrete Fourier Transform (DFT)，DFT是一種傅立葉變換，在時域和頻域上都呈離散的形式。

DFT由於在時域和頻域上都是離散的形式，那麼很適合用計算機去處理。但是DFT的演算法法複雜度達到了Ο(n^2)，我們取n=1024，那麼計算DFT需要1048576即一百多萬次複數乘法運算。在實際的處理過程中，會遇到更大的N，運算量將異常的大，很難滿足實際的訊號處理需求。

快速傅立葉變換(FFT)是序列離散傅立葉變換DFT的快速演算法,它簡化了DFT的運算過程。FFT的演算法複雜度為O(nlog n)}，在實踐中，計算時間可減少幾個數量級。

快速傅立葉變換被廣泛地應用於工程、科學和數學領域，基本思想是1965年提出的。1994年，Gilbert Strang ，將FFT描述為"我們一生中最重要的數值演算法"；FFT並被IEEE"科學與工程計算"雜誌列入20世紀前10大演算法。

我們大部分教材上介紹的都是庫利-圖基FFT演算法，它的主要思想是把輸入序列在時域奇偶順序分組，然後再利用對稱性、週期性質簡化運算。也稱為時域抽取的FFT演算法。

與此對應的另一種辦法是在頻域按奇偶順序分組，稱為桑德-圖基演算法。

從FFT演算法誕生至今，各種改進或派生的演算法層出不窮。例如：Prime-factor FFT algorithm, Bruun"s FFT algorithm, Rader"s FFT algorithm, Bluestein"s FFT algorithm, and Hexagonal Fast Fourier Transform。

感興趣的讀者，可以下載相關論文或者搜尋學習。

快速傅立葉變換 (fast Fourier transform), 即利用計算機計算離散傅立葉變換（DFT)的高效、快速計算方法的統稱，簡稱FFT。快速傅立葉變換是1965年由J.W.庫利和T.W.圖基提出的。採用這種演算法能使計算機計算離散傅立葉變換所需要的乘法次數大為減少，特別是被變換的抽樣點數N越多，FFT演算法計算量的節省就越顯著。