DFT · 离散傅里叶变换

DFT：逐个频率「探针」

真实世界里我们拿到的不是连续函数，而是一串采样点 $x[0], x[1], \dots , x[N-1]$ 。离散傅里叶变换 (DFT) 把这 N 个时域样本，变成 N 个频域复数 $X[0..N-1]$ :

X[k] = Σₙ x[n] · e^(−i·2π·k·n/N) = Σ x[n]·(cos − i·sin)

每个 $X[k]$ 是一个探针：它把信号和「频率为 k 的旋转向量」逐点相乘再求和——用旋转向量的语言说，就是把信号缠绕在转速 k 的圆上，看 N 个贡献向量首尾相接后的合矢量有多长。对得上（信号真含这个频率）→ 向量同向叠加成一根长矢量；对不上 → 向量绕圈互相抵消，合矢量≈0。

选一个信号，按「下一个 k ▸」逐个频率探测。左图是当前 k 的缠绕：N 个贡献向量首尾相接，粗矢量就是 $X[k]$ 。右图是逐步建起的幅度谱 |X[k]|——谱上的尖峰，就是信号里真实存在的频率。

三条要记住的性质。 其一，k=0 是直流 (DC):X[0] = Σx[n] = 所有样本之和 = 平均值×N。其二，共轭对称：实信号的谱满足 $X[N-k] = conj(X[k])$ ——所以幅度谱左右镜像，真正独立的只有前一半（这也是「单频 k=2」会在 k=2 和 k=14 都出峰的原因）。其三，能在实/虚部之间分相位:cos 分量进实部、sin 分量进虚部，|X[k]| 给强度、atan2(im,re) 给相位。

它很慢。 外层 N 个 k、内层 N 个 n，一共 $N^2$ 次复数乘加。N=1024 就是百万次；音频一秒几万样本、图像上百万像素， $O(N^2)$ 在这些规模下不可用。FFT 用分治把它压到 $O(N \log N)$ ——这是 20 世纪最重要的算法之一。