FFT 通过分治法将 DFT 复杂度从 O(N²)降至 O(N log N)，核心是奇偶分解与蝴蝶操作；c++实现需用复数类、位翻转重排数据，并迭代合并子结果，正逆变换仅差符号及归一化，完整流程包括预处理、合并与还原验证。
傅里叶变换（Fourier transform）能将信号从时域转换到频域，而快速傅里叶变换（FFT）是其高效实现方式。在 C ++ 中手写一个简单的 FFT算法 ，有助于理解其数学原理和 递归 结构。
1. FFT 的基本原理
离散傅里叶变换（DFT）公式为：
X[k] = Σ (n=0 到 N−1) x[n] ⋅ e^(−2πi⋅k⋅n/N)
立即学习“C++ 免费学习笔记（深入）”；
直接计算复杂度为 O(N²)。FFT 利用分治思想，将序列分为奇偶两部分，递归计算，把复杂度降到 O(N log N)。
核心是“** 蝴蝶操作 **”（Butterfly Operation），结合单位根的周期性和对称性进行合并计算。
2. 复数支持与位翻转重排
C++标准库 提供 std::complex，可直接用于复数运算。
FFT 递归前需对输入数组做“位反转置换”（Bit-reversal Permutation），使数据按特定顺序 排列，便于迭代合并。
例如长度为 8 时，索引二进制表示如下：
- 0: 000 → 000 → 0
- 1: 001 → 100 → 4
- 2: 010 → 010 → 2
- 3: 011 → 110 → 6
- … 依此类推
3. 迭代版 FFT 实现代码
以下是一个简洁的 C ++ 迭代 FFT 实现：
#include <iostream> #include <vector> #include <complex> #include <cmath> <p>using namespace std; using Complex = complex<double> const double PI = acos(-1);</p><p>// 位反转函数 int reverseBits(int x, int logN) {int rev = 0; for (int i = 0; i < logN; ++i) {if (x & (1 << i)) rev |= 1 << (logN - 1 - i); } return rev; }</p><p>// 快速傅里叶变换（原地 FFT）void fft(vector<Complex>& a, bool invert) {int n = a.size(); int logN = 0; while ((1 << logN) < n) ++logN;</p><pre class='brush:php;toolbar:false;'>// 位反转重排 for (int i = 0; i < n; ++i) {int ri = reverseBits(i, logN); if (i < ri) swap(a[i], a[ri]); } // 迭代合并 for (int len = 2; len <= n; len <<= 1) {double angle = 2 * PI / len * (invert ? 1 : -1); Complex wlen(cos(angle), sin(angle)); for (int i = 0; i < n; i += len) {Complex w(1); for (int j = 0; j < len / 2; ++j) {Complex u = a[i + j]; Complex v = a[i + j + len/2] * w; a[i + j] = u + v; a[i + j + len/2] = u - v; w *= wlen; } } } // 逆变换后归一化 if (invert) {for (int i = 0; i < n; ++i) a[i] /= n; }}
4. 使用示例与验证
测试一个简单信号的 FFT：
int main() { vector<Complex> signal = {0,1,2,3,4,5,6,7}; // 长度必须为 2 的幂 fft(signal, false); // 正向 FFT <pre class='brush:php;toolbar:false;'>cout << " 频域结果：n"; for (int i = 0; i < signal.size(); ++i) {cout << "X[" << i << "] = " << signal[i] << 'n'; } fft(signal, true); // 逆 FFT 验证 cout << "n 逆变换还原：n"; for (auto& x : signal) cout << x.real() << ''; cout <<'n'; return 0;}
输出应接近原始信号，说明变换可逆。
基本上就这些。掌握 FFT 关键在于理解分治结构、单位根性质和蝴蝶操作。这个版本虽简单，但已具备实际用途，比如音频分析或多项式乘法。不复杂但容易忽略细节，如位反转和符号方向。
