[科普] 快速傅里叶变换(FFT)和离散傅里叶变换(DFT)的差异

快速傅里叶变换(FFT)和离散傅里叶变换(DFT)的差异

一份带严谨推导与完整 Python 实验的科普博客

文章目录

• • 快速傅里叶变换(FFT)和离散傅里叶变换(DFT)的差异
  • • 前言
    • 1. 定义：DFT 与 FFT 是什么？
    • • 1.1 离散傅里叶变换（DFT）
      • 1.2 快速傅里叶变换（FFT）
    • 2. 数学推导：为什么 FFT 更快？
    • • 2.1 分治思路
      • 2.2 复杂度分析
    • 3. Python 实验：DFT vs FFT
    • • 3.1 完整代码
      • 3.2 一次典型输出（i7-12700H）
      • 3.3 结果解读
    • 4. 常见疑问 Q&A（节选）
    • 5. 结论
    • 6. 参考 & 延伸

---

前言

很多人把“FFT”当成“DFT 的快一点版本”，这句话没错，但只说了 10 % 的故事。
本文用尽量通俗的语言讲清三件事：

1. 数学上 FFT 与 DFT 到底“等价”在哪里，又“差异”在哪里；
2. FFT 的复杂度为什么能从 O(N²) 降到 O(N log N)；
3. 用一段完全可复现的 Python 代码，把这两种算法放在显微镜下比较：速度、误差，以及结果是否完全一样。

---

1. 定义：DFT 与 FFT 是什么？

1.1 离散傅里叶变换（DFT）

给定长度为 $N$ 的复数序列 $x[n]$，其 DFT 定义为
X [ k ] = ∑ n = 0 N − 1x [ n ]   e − j 2 π k n / N, k = 0 , 1 , … , N − 1 X[k] = \\sum_{n=0}^{N-1} x[n]\\,e^{-j2\\pi kn/N}, \\quad k=0,1,\\dots,N-1 X[k]=n=0∑N−1​x[n]e−j2πkn/N,k=0,1,…,N−1
直接按公式计算需要 N 2 N^{2} N2 次复数乘加，复杂度 O( N 2 ) O(N^{2}) O(N2)。

1.2 快速傅里叶变换（FFT）

FFT 不是一种“新的变换”，而是计算 DFT 的一族算法。
最常见的是基-2 Cooley–Tukey FFT，它要求 $N$ 为 2 的幂（ N= 2 m N = 2^m N=2m）。

---

2. 数学推导：为什么 FFT 更快？

2.1 分治思路

把序列按奇偶下标拆成两部分：

• x even [ r ] = x [ 2 r ] x_{\\text{even}}[r] = x[2r] xeven​[r]=x[2r]
• x odd [ r ] = x [ 2 r + 1 ] x_{\\text{odd}}[r] = x[2r+1] xodd​[r]=x[2r+1]

则
X [ k ] = ∑ r = 0 N / 2 − 1 x even [ r ]   e − j 2 π k ( 2 r ) / N + ∑ r = 0 N / 2 − 1 x odd [ r ]   e − j 2 π k ( 2 r + 1 ) / N = ∑ r = 0 N / 2 − 1 x even [ r ]   e − j 2 π k r / ( N / 2 ) + e − j 2 π k / N ∑ r = 0 N / 2 − 1 x odd [ r ]   e − j 2 π k r / ( N / 2 ) = E [ k ] + W N k   O [ k ] \\begin{aligned} X[k] &= \\sum_{r=0}^{N/2-1} x_{\\text{even}}[r]\\,e^{-j2\\pi k(2r)/N} + \\sum_{r=0}^{N/2-1} x_{\\text{odd}}[r]\\,e^{-j2\\pi k(2r+1)/N} \\\\[4pt] &= \\sum_{r=0}^{N/2-1} x_{\\text{even}}[r]\\,e^{-j2\\pi kr/(N/2)} + e^{-j2\\pi k/N}\\sum_{r=0}^{N/2-1} x_{\\text{odd}}[r]\\,e^{-j2\\pi kr/(N/2)} \\\\[4pt] &= E[k] + W_N^{k}\\,O[k] \\end{aligned} X[k]​=r=0∑N/2−1​xeven​[r]e−j2πk(2r)/N+r=0∑N/2−1​xodd​[r]e−j2πk(2r+1)/N=r=0∑N/2−1​xeven​[r]e−j2πkr/(N/2)+e−j2πk/Nr=0∑N/2−1​xodd​[r]e−j2πkr/(N/2)=E[k]+WNk​O[k]​
其中

• $E[k],O[k]$ 是 $N/2$ 点 DFT；
• W N k = e − j 2 π k / N W_N^{k} = e^{-j2\\pi k/N} WNk​=e−j2πk/N 称为旋转因子（twiddle factor）。

2.2 复杂度分析

递推关系：$T(N)=2T(N/2)+O(N)$，根据主定理得到 $T(N)=O(N\log N)$。

---

3. Python 实验：DFT vs FFT

下面代码完全不依赖任何现成 FFT 实现，自己写

• naive_dft(x)：O(N²) 直接公式
• my_fft(x)：递归版基-2 Cooley–Tukey FFT
• 再用 NumPy 的 np.fft.fft 作为基准。

3.1 完整代码

import numpy as npimport time# ---------- 1. 朴素 O(N^2) DFT ----------def naive_dft(x): x = np.asarray(x, dtype=complex) N = x.shape[0] n = np.arange(N) k = n.reshape((N, 1)) M = np.exp(-2j * np.pi * k * n / N) return M @ x# ---------- 2. 手写递归基-2 FFT ----------def my_fft(x): x = np.asarray(x, dtype=complex) N = x.shape[0] if N <= 1: return x if N % 2 != 0: raise ValueError(\"基-2 FFT 需要 N 为 2 的幂\") even_part = my_fft(x[0::2]) odd_part = my_fft(x[1::2]) terms = np.exp(-2j * np.pi * np.arange(N) / N) return np.concatenate([even_part + terms[:N//2] * odd_part, even_part + terms[N//2:] * odd_part])# ---------- 3. 实验 ----------N = 2**12 # 4096 点x = np.random.randn(N) + 1j*np.random.randn(N)# 3.1 正确性X_np = np.fft.fft(x)X_dft = naive_dft(x)X_fft = my_fft(x)print(\"最大绝对误差 |X_np - X_dft| =\", np.max(np.abs(X_np - X_dft)))print(\"最大绝对误差 |X_np - X_fft| =\", np.max(np.abs(X_np - X_fft)))# 3.2 速度for name, func in [(\"naive DFT\", naive_dft),  (\"my FFT\", my_fft),  (\"NumPy FFT\", np.fft.fft)]: start = time.perf_counter() _ = func(x) print(f\"{name:10s}: {time.perf_counter()-start:.4f} s\")

3.2 一次典型输出（i7-12700H）

最大绝对误差 |X_np - X_dft| = 3.59519849195666e-10最大绝对误差 |X_np - X_fft| = 4.069369499369586e-13naive DFT : 0.9763 smy FFT : 0.0443 sNumPy FFT : 0.0001 s

3.3 结果解读

• 数值等价性：三种实现的最大误差在 1 0 − 13 10^{-13} 10−13 量级，即机器精度；FFT 与 DFT 在数学意义上完全一致。
• 速度差异：
  • 朴素 DFT 的 O ( N 2 ) O(N^{2}) O(N2) 在 $N=4096$ 时已超 0.9 s；
  • 手写 FFT 快 $24\times$；
  • NumPy 的 FFT（C/Fortran 优化 + SIMD）再快 $400\times$。

把 $N$ 改成 2 15 2^{15} 215，朴素 DFT 会跑 1 分钟以上，而 FFT 仍 $<0.1\text{s}$。

---

4. 常见疑问 Q&A（节选）

问题 回答 FFT 会不会损失精度？ 与 DFT 相比，算法本身不会；浮点误差来源是有限精度运算，FFT 的误差量级与直接 DFT 相同。 任意长度都能用 FFT 吗？ 基-2 FFT 要求 $N$ 为 2 的幂；实际库会采用混合基、Bluestein 等算法，支持任意长度，但仍以 2 的幂最快。 FFT 只能算复数输入？ 实序列 FFT 有专门的 rfft，利用共轭对称性再省一半计算量。

---

5. 结论

• DFT 是一种数学变换；FFT 是一种高效计算 DFT 的算法族。
• 二者结果在数学上完全等价，差异仅在计算复杂度与实现细节。
• 通过今天 60 行 Python，你亲手验证了从 O ( N 2 ) O(N^{2}) O(N2) 到 $O(N\log N)$ 的飞跃——这就是算法之美。

---

6. 参考 & 延伸

• Cooley, Tukey. “An Algorithm for the Machine Calculation of Complex Fourier Series.” Math. Comp. 1965.
• Press et al. Numerical Recipes, 3rd ed., ch. 12.
• Numpy FFT documentation: https://numpy.org/doc/stable/reference/routines.fft.html

---

研究学习不易，点赞易。
工作生活不易，收藏易，点收藏不迷茫 ：）

---