离散傅里叶变换 (DFT)

离散傅里叶变换（Discrete Fourier Transform, DFT）是将离散时间域信号转换至频率域的核心数学工具，其本质是将采样数据转化为振荡的三角多项式系数描述，从而在频域揭示信号的幅度与相位特征。根据定义直接计算长度为N的序列的DFT，需要进行 $O(N^2)$ 次复数乘法与加法运算，在处理海量数据时构成严重的算力瓶颈。FFT通过分治法将这一计算复杂度降至 $O(N\log N)$。