FFT

傅立葉轉換

傅立葉轉換在物理和數學中經常出現，這也代表它在日常生活中同樣有許多應用。

簡單來說，傅立葉轉換會接收一個輸入訊號（通常位於時域或空域），並將它轉換到頻域。更具體地說，當輸入訊號是由不同頻率混雜而成（也就是疊加）時，這個轉換會把各個頻率分離出來，並顯示它們的相對強度。

這讓傅立葉轉換成為訊號處理（例如濾波、壓縮等）以及許多資料科學應用的主要工具。因此，它的使用範圍可能比一般人最初想像的更廣，也讓它成為一個絕佳的例子，說明虛數為何不可或缺，畢竟傅立葉轉換的輸出一般來說是複數。

雖然傅立葉轉換有積分形式，但我們身處數位世界，所以感興趣的是離散版本。這個轉換的推導超出了本練習的範圍，不過正向的離散轉換（轉換到頻域）形式如下：

Xₖ = Σ xₙ * ℯ^(-2iπk * n/N)

這裡的加總對n進行，N是取樣點的數量，k是頻率，i是虛數單位，而xₙ則是個別的取樣點。

快速傅立葉轉換

雖然傅立葉轉換極為實用，但以樸素方式實作的話有點慢（O(n²)）。快速傅立葉轉換（FFT）是一種能大幅加速的演算法。這通常是透過分治法達成，運用公式中的一些對稱性，讓複雜度漸進為O(Nlog(N))。這樣的加速大幅提升了這個轉換的實用性與適用範圍。