快速傅里叶变换

傅立叶变换

傅里叶变换的直观概念

任何波形可由多个正弦波叠加近似。

• 输入为长度为 $n$ 的离散信号序列（$n$ 一般为 $2^k$）
• 输出为一系列频率上的振幅和相位

离散傅里叶变换

性质：

• ${\omega }_n^{2k}={\omega }_{n/2}^k$
• ${\omega }_n^{n/2}=-1$

快速傅里叶变换 FFT

利用离散傅里叶变换的性质，可以设计一个快速傅里叶变换的分治算法，将原问题一分为二。

算法分析

• 时间复杂度：$T(n)=O(n\log n)$