快速傅立葉轉換（fast Fourier transform）
/ FOOR-yay /
一個次數為 n-1 的多項式可用兩種等價方式描述：用它的 n 個係數列表，或用它在 n 個相異點上的值（n 個點唯一決定一條 n-1 次曲線，正如 2 個點決定一條直線）。離散傅立葉轉換是把係數轉成在一組特殊取值點上的值；快速傅立葉轉換則是用分治法以 O(n log n) 而非顯然的 O(n^2) 完成這個轉換。
樸素方法在 n 個點各自評估多項式，每點花 O(n)、總共 O(n^2)。FFT 的巧思在於取值點的選擇：n 個複數單位根（在單位圓上等距分布的 n 個點），具有美妙的對稱性。把多項式 P(x) 拆成偶數索引係數與奇數索引係數，構成兩個半規模多項式 Peven 與 Podd，使 P(x) = Peven(x^2) + x * Podd(x^2)。因為單位根成對出現 r 與 -r 且平方相同，在全部 n 個根上評估 P，便化簡為只在 n/2 個平方點上評估 Peven 與 Podd，再用便宜的乘加（蝴蝶運算）把每一對組合起來。這就是 T(n) = 2 T(n/2) + O(n) = O(n log n)。用反向的根跑同一套機制，便能把值轉回係數。
FFT 是有史以來最具影響力的演算法之一——它改造了訊號處理、音訊與影像壓縮以及大數算術，常被稱為許多現代數位技術背後的主力。對演算法設計而言，它最重要的用途是以 O(n log n) 相乘多項式與巨大整數。誠實的微妙之處：乾淨版本假設 n 是 2 的冪（否則補零），而因為它用複數浮點單位根計算，會帶有微小的捨入誤差——對精確的整數運算，常改用模體上的數論轉換（NTT）。
要在 4 次單位根 {1, i, -1, -i} 上評估 P，注意 1 與 -1 平方為 1，i 與 -i 平方為 -1。所以 Peven 與 Podd 只需在 {1, -1} 上評估——點數減半——再用蝴蝶運算把每一對重新組合。
成正負對的單位根讓一次在平方點上的評估同時服務兩者，產生 O(n log n) 的切分。
教科書版 FFT 假設 n 是 2 的冪並使用複數單位根，因此帶有浮點捨入誤差；精確的整數運算通常改用數論轉換。