快速傅立葉轉換（fast Fourier transform）
離散傅立葉轉換用途極廣，但直接計算卻慢得令人痛苦：N 個輸出各自加總 N 項，就是 N^2 次乘加，所以一秒、44,100 個樣本的音訊片段需要約二十億次運算，而一張百萬像素的影像更是無望。快速傅立葉轉換是一種演算法，只用 O(N log N) 次運算就算出「完全相同」的 DFT。它被廣泛譽為二十世紀最重要的數值演算法，也是即時頻譜分析、數位音訊、MP3、JPEG、磁振造影重建與無線電得以存在的原因。
訣竅在於分治。一個大小為 N 的 DFT 可拆成兩個大小為 N/2 的 DFT：一個對偶數索引的樣本、一個對奇數索引的樣本。一小段代數顯示，把這兩個半轉換用簡單的旋轉因子（twiddle factor）權重組合（即蝶形步驟），就能還原完整的轉換。每一半再拆、再拆，遞迴下去，直到抵達大小為 1 的平凡轉換。拆分約有 log2(N) 層，每層做 O(N) 次廉價的組合工作，總計即 O(N log N)。回報驚人：當 N 約一百萬時，N^2 是 10^12，而 N log N 約 2 * 10^7——加速五萬倍，把數小時化為不到一秒。
實用的 FFT 有許多變體——經典的 radix-2 要求 N 是 2 的冪，而混合基底（mixed-radix）與 Bluestein 演算法能處理任意 N（FFTW 等現代函式庫會自動挑選最佳計畫）。此轉換是「算出來」而非近似：FFT 給出與 O(N^2) DFT 相同的答案，僅差一般的浮點捨入，事實上因運算少得多，捨入通常還「更小」。誠實的提醒是：FFT 並未改變 DFT 的「意義」——洩漏、混疊與奈奎斯特極限全都仍然適用；FFT 只是讓計算變得負擔得起。
當 N = 1024 時，樸素 DFT 做約 1024^2 = 1,048,576 次複數乘法；FFT 做約 1024 * log2(1024) = 1024 * 10 = 10,240——少了約一百倍。當 N = 1,000,000 時，差距擴大到約五萬倍，這正是「無法使用」與「瞬間完成」之間的差別。
與 DFT 答案相同，但成本是 O(N log N) 而非 O(N^2)——這個加速造就了訊號處理。
當 N 是高度可分解（最好是 2 的冪）時 FFT 最快；除非函式庫使用 Bluestein 演算法，否則很大的質數 N 會退回到較慢的路徑。常見的做法是先把資料補零到下一個 2 的冪再轉換。