你有沒有想過，手機怎麼從一段錄音裡聽出是哪幾個音、音樂播放器上那排跳動的頻譜長條又是怎麼冒出來的？ 背後都是把一段訊號拆成「一堆不同頻率的波疊在一起」。傅立葉變換就是做這件拆解的工具， 但老實算一遍要 n×n 次、資料一大就慢到卡住；FFT（快速傅立葉變換）用分治法把重複的計算折疊起來， 把工作量從 n² 砍到 n log n，才讓即時處理聲音、影像變得可能。 下面你會看到它一階段一階段把數列變成頻率結果的每一步。
迭代版 Cooley-Tukey FFT：先依索引的二進位反轉重新排列輸入（位元反轉排列），
再由下而上跑 log₂n 個階段，每階段把序列切成長度倍增的區段，用蝶形運算
u=a[i+j]、v=w·a[i+j+len/2] → a[i+j]=u+v、a[i+j+len/2]=u-v 更新，
避免遞迴、就地完成整個變換。
FFT 是分治法的經典應用：遞迴版把長度 n 的 DFT 拆成「偶數項」與「奇數項」兩個長度 n/2 的子問題， 各自遞迴求解後用蝶形運算合併，時間複雜度 T(n) = 2T(n/2) + O(n) = O(n log n)。 本頁呈現的是等價的迭代版：先用位元反轉排列把遞迴的分解順序「攤平」成陣列順序， 再由下而上做 log n 個階段的蝶形合併，省去遞迴呼叫的開銷。
a+bi 格式顯示。框線標記本步驟涉及的格子。