快速傅立葉轉換（FFT）

快速傅立葉轉換並不是另一種轉換——它算的就是同一個離散傅立葉轉換，只是透過巧妙重複利用算過的運算、而非重算，因而快得驚人。直接計算 N 點 DFT 約需 N² 次乘法；FFT 把訊號一再對半拆解，將其降到約 N·log₂N。對一百萬點的分析而言，這就是一兆次運算與約兩千萬次運算之差——大約少了五萬倍的工作量。

這個單一演算法是有史以來最具影響力的之一。沒有它，即時頻譜分析儀、MP3 與 JPEG 壓縮、MRI 影像重建、Wi-Fi 與 4G/5G 數據機（它們透過 OFDM 同時在數千個頻率格上傳送資料）以及音樂 App 上的音訊視覺化，全都不切實際。1965 年由 Cooley 與 Tukey 重新發現，它默默驅動著現代訊號科技中驚人比例的一切。