FFT

傅里叶变换

傅里叶变换在物理学和数学中经常出现，这也意味着它在日常生活中有许多用途。

简而言之，傅里叶变换接收一个输入信号（通常位于时域或空域），并把它转换到频域。 更具体地说，如果输入信号由多种不同频率混杂而成（也就是这些频率的叠加），傅里叶变换就会把这些频率逐一分离出来，并显示它们各自的相对强度。

这让傅里叶变换成为信号处理（例如滤波、压缩等）和许多数据科学应用中的主要工具。 因此，它的使用可能比人们最初想象的要广泛得多；考虑到傅里叶变换的输出通常是一个复数，它也就成了虚数不可或缺的一个典型例子。

傅里叶变换虽然有积分形式的表述，但我们身处数字世界，所以关心的是离散版本。 该变换的推导超出了本练习的范围，不过正向的离散变换（转换到频域）形式如下： Xₖ = Σ xₙ * ℯ^(-2iπk * n/N) 这里求和是对n进行的，N是样本的数量，k是频率，i是虚数单位，xₙ是单个样本。

快速傅里叶变换

傅里叶变换虽然极其有用，但朴素地实现起来有点慢（O(n²)）。 快速傅里叶变换（FFT）是一种能大幅提升速度的算法。 这通常通过分治策略实现，它利用了公式中的某些对称性，最终达到渐近O(Nlog(N))的复杂度。 这种提速极大地提升了傅里叶变换的实用性，也扩大了它适用的应用范围。