什麼是fft算法

快速傅立葉變換

FFT（Fast Fourier Transform，快速傅立葉變換）是一種用於計算離散傅立葉變換（DFT）的高效算法。

FFT算法通過使用分治策略和其他最佳化技術，將DFT計算的複雜度從O(N^2)降低到O(NlogN)，極大地減少了計算時間。該算法在1965年由J.W.庫利和T.W.圖基提出，廣泛套用於音頻處理、信號壓縮、圖像處理、機器學習等多個領域。