快速傅里葉變換（FFT）是一種計算序列的離散傅里葉變換（DFT）或其逆（IDFT）的算法。傅里葉分析將一個信號從其原始域（通常是時間或空間）轉換為頻域的表示，反之亦然。DFT是通過將一個數值序列分解為不同頻率的成分而得到的。這種操作在許多領域都很有用，但直接從定義中計算它往往太慢而不實用。FFT通過將DFT矩陣分解為稀疏（大部分為零）因子的乘積來快速計算這種轉換。因此，它設法將計算DFT的復雜性從是數據大小。速度上的差異可能是巨大的，特別是對于N可能是數千或數百萬的長數據集。在存在舍入誤差的情況下，許多FFT算法比直接或間接地評估DFT定義要準確得多。有許多不同的FFT算法，基于廣泛的已發表的理論，從簡單的復數運算到群論和數論。快速傅里葉變換被廣泛用于工程、音樂、科學和數學領域的應用。其基本思想在1965年得到普及，但一些算法早在1805年就已得出。1994年，吉爾伯特-斯特朗將FFT描述為我們一生中最重要的數字算法，它被IEEE雜志《科學與工程計算》列入20世紀十大算法。最著名的FFT算法取決于N的因式分解，但是對于所有的N，甚至素數N，都有復雜度為O(NlogN)的FFT。是統一的N次方原始根，因此可以應用于任何有限域的類似變換，如數論變換。由于逆DFT與DFT相同，但指數中的符號相反，且有1/N的因子，任何FFT算法都可以很容易地適用于它。

DFT的快速算法的發展可以追溯到卡爾-弗里德里希-高斯在1805年未發表的工作，當時他需要它來從樣本觀測中插補小行星帕拉斯和朱諾的軌道。他的方法與JamesCooley和JohnTukey在1965年發表的方法非常相似，他們被認為是現代通用FFT算法的發明者。雖然高斯的工作甚至早于約瑟夫-傅里葉在1822年的成果，但他沒有分析計算時間，最終使用其他方法來實現他的目標。從1805年到1965年，其他作者發表了一些FFT的版本。FrankYates在1932年發表了他的版本，稱為交互算法，它提供了Hadamard和Walsh變換的有效計算。Yates的算法仍然被用于統計設計和實驗分析領域。1942年，G.C.Danielson和CorneliusLanczos發表了他們的版本，用于計算X射線晶體學的DFT，在這個領域，傅里葉變換的計算是一個可怕的瓶頸。雖然過去的許多方法都集中在減少恒定系數的在利用對稱性進行計算的過程中，丹尼爾森和蘭佐斯意識到，可以利用周期性并應用加倍的技巧，使[N]增加一倍，而勞動量僅略高于一倍，不過和高斯一樣，他們并沒有分析出這導致了JamesCooley和JohnTukey獨立地重新發現了這些早期的算法，并在1965年發表了一個更通用的FFT，當N是復合的而不一定是2的冪時，也適用，同時還分析了縮放。

Tukey是在肯尼迪總統的科學咨詢委員會的一次會議上提出這個想法的，當時的討論主題是通過設置傳感器從外部包圍蘇聯來檢測蘇聯的核試驗。為了分析這些傳感器的輸出，將需要一種FFT算法。在與Tukey的討論中，RichardGarwin認識到該算法的普遍適用性，不僅適用于國家安全問題，也適用于廣泛的問題，包括他直接感興趣的一個問題，即確定氦-3的三維晶體中自旋方向的周期性。加文將圖基的想法交給庫利（兩人都在IBM的沃森實驗室工作）進行實施。Cooley和Tukey在相對較短的6個月內發表了論文。由于Tukey不在IBM工作，這一想法的專利性受到懷疑，該算法進入了公共領域，而這一領域經歷了2000年的計算xxx。