快速傅立葉變換（英語：Fast Fourier Transform, FFT），是快速計算序列的離散傅立葉變換（DFT）或其逆變換的方法。傅立葉分析將訊號從原始域（通常是時間或空間）轉換到頻域的表示或者逆過來轉換。FFT會通過把DFT矩陣分解為稀疏（大多為零）因子之積來快速計算此類變換。因此，它能夠將計算DFT的複雜度從只用DFT定義計算需要的 $O(n^2)$，降低到 $O(n\log n)$，其中 $n$ 為資料大小。

快速傅立葉變換廣泛的應用於工程、科學和數學領域。這裡的基本思想在1965年才得到普及，但早在1805年就已推導出來。 1994年美國數學家吉爾伯特·斯特朗把FFT描述為「我們一生中最重要的數值演算法」，它還被IEEE科學與工程計算期刊列入20世紀十大演算法。

用FFT計算DFT會得到與直接用DFT定義計算相同的結果；最重要的區別是FFT更快。（由於捨入誤差的存在，許多FFT演算法還會比直接運用定義求值精確很多，後面會討論到這一點。）

令 $x_0, ...., x_{N-1}$ 為複數。DFT由下式定義

直接按這個定義求值需要 $O(N^2)$ 次運算：$X_k$ 共有 $N$ 個輸出，每個輸出需要 $N$ 項求和。直接使用DFT運算需使用$N$個複數乘法($4N$ 個實數乘法)與$N-1$個複數加法($2N-2$個實數加法)，因此，計算使用DFT所有$N$點的值需要$N^2$複數乘法與$N^2-N$ 個複數加法。FFT則是能夠在 $O(N \log N)$ 次操作計算出相同結果的任何方法。更準確的說，所有已知的FFT演算法都需要 $O(N \log N)$ 次運算（技術上$O$只標記上界），雖然還沒有已知的證據證明更低的複雜度是不可能的。（Johnson and Frigo, 2007）

要說明FFT節省時間的方式，就得考慮複數相乘和相加的次數。直接計算DFT的值涉及到 $N^2$ 次複數相乘和 $N(N−1)$ 次複數相加（可以通過削去瑣碎運算（如乘以1）來節省 $O(N)$ 次運算）。眾所周知的基2庫利-圖基演算法，$N$ 為2的冪，可以只用 $\frac N2\log _2(N)$ 次複數乘法（再次忽略乘以1的簡化）和 $Nlog_2(N)$ 次加法就可以得到相同結果。在實際中，現代電腦通常的實際效能通常不受算術運算的速度和對複雜主體的分析主導（參見Frigo & Johnson, 2005），但是從 $O(N^2)$ 到 $O(N \log N)$ 的母體改進仍然能夠體現出來。

以上問題雖然困擾著aoygnuy，不過這件事對他來說輕輕鬆鬆，但是有著更難的問題等著他解決。

有一天他獲得了一個大箱子，這個箱子有能夠裝載的重量上限$M$

箱子前方是滿坑滿谷的背包，每個背包都價值不菲，但是每個背包的規格皆有些差別。為了拿到更多錢好讓卡他拉麵的人有拉麵可以吃，他決定利用這個大撈一筆。

他獲得了一張表格，寫的就是那$N$個背包的重量$w_i$及價格$v_i$，aoygnuy當然想要賺更多錢，不過為了避免箱子裝太重的東西破掉，aoygnuy決定請你幫忙寫程式，協助他算出能夠載運的背包的最大總價值。