庫利-圖基演算法（Cooley-Tukey algorithm）
/ KOO-lee TOO-kee /
1965 年庫利（James Cooley）與圖基（John Tukey）發表其方法時，讓快速傅立葉轉換變得實用又出名（後來才發現核心想法其實可追溯到 1805 年的高斯）。庫利-圖基演算法是把大小為 N 的 DFT 化為許多微小 DFT 的具體分治配方，也是多數人說「FFT」時所指的方案。
以下用平實步驟說明這個遞迴。把 N 個樣本分成偶數索引與奇數索引兩組。分別計算每一半的大小為 N/2 的 DFT——稱結果為 E_k 與 O_k。接著完整的 DFT 把它們重組：X_k = E_k + W^k * O_k 以及 X_{k+N/2} = E_k - W^k * O_k，其中 W = e^(-2*pi*i/N) 是旋轉因子。每一次這樣的配對就是一個蝶形，它一次產生兩個輸出，這也是為何一次 W^k 乘法能同時服務頻譜的兩半。由於每一半本身又用相同的拆分求解，遞迴在大小為 1 的轉換（什麼也不做）觸底，展開後得到 log2(N) 個階段、每階段 N/2 個蝶形——正好是 O(N log N) 的成本。這個「依時間索引的奇偶拆分」版本稱為時間抽選；鏡像版本則做頻率抽選。
有兩個實作細節無處不在。第一，基本的 radix-2 形式要求 N 是 2 的冪；真實函式庫推廣到混合基底（把 N 分解成小質數並據此拆分），使任意長度都能運作。第二，奇偶拆分會把輸入重排成位元反轉（bit-reversed）順序，所以高效能程式碼要嘛先把每個索引的位元反轉以預先洗牌，要嘛把這個重排吸收進蝶形樣式。結果是原地、對快取友善，且是你日後呼叫的幾乎每一個 FFT 的根基。
一個 8 點 DFT 拆成兩個 4 點 DFT（偶數索引 0,2,4,6 與奇數 1,3,5,7）；每個 4 點再拆成兩個 2 點 DFT；每個 2 點就是單一蝶形。三個階段（log2(8) = 3）、每階段四個蝶形，算出全部八個輸出——12 個蝶形而非 64 次原始乘加。
奇偶拆分、遞迴、再用旋轉因子重組——一張圖看懂 FFT。
庫利-圖基精確計算 DFT；它不是近似。功勞應與高斯共享——他在 1805 年用相同的分解來內插小行星軌道，比傅立葉分析成為計算課題早了一個多世紀。