快速傅里叶变换（FFT）通过分治法将DFT复杂度从O(N²)降至O(N log N)。C++实现需用std::complex和vector，递归拆分奇偶序列并合并结果，适用于2的幂长度信号。示例中构造含1Hz和3Hz的正弦信号，经FFT后输出频域幅度谱。实际应用建议改用迭代版、支持非2幂长度及调用FFTW等优化库以提升性能与稳定性。该实现适合教学理解，为进阶应用打下基础。
快速傅里叶变换（FFT）是信号处理中将时域信号转换为频域的关键算法。C++实现FFT通常基于“分治法”优化离散傅里叶变换（DFT），将复杂度从 O(N²) 降低到 O(N log N)。下面介绍一个简洁、可运行的递归版FFT实现，适用于复数序列。
1. 复数支持与头文件准备
C++标准库提供 std::complex 支持复数运算，配合 <vector> 存储数据：
#include <iostream> #include <vector> #include <complex> #include <cmath> <p>using namespace std; using Complex = complex<double>;</p>
2. 递归实现FFT核心函数
该版本要求输入长度为2的幂。核心思想是将序列分为奇偶两部分，分别计算后合并：
vector<Complex> fft(vector<Complex> a) {
int n = a.size();
if (n == 1) return {a[0]};
<pre class='brush:php;toolbar:false;'>// 拆分为偶数和奇数索引子序列
vector<Complex> even(n / 2), odd(n / 2);
for (int i = 0; i < n / 2; i++) {
even[i] = a[2*i];
odd[i] = a[2*i + 1];
}
// 递归计算子问题
vector<Complex> y_even = fft(even);
vector<Complex> y_odd = fft(odd);
// 合并结果
vector<Complex> y(n);
double angle = 2 * M_PI / n;
Complex w(1), wn(cos(angle), sin(angle)); // 单位根
for (int k = 0; k < n / 2; k++) {
y[k] = y_even[k] + w * y_odd[k];
y[k + n/2] = y_even[k] - w * y_odd[k];
w *= wn; // 累乘单位根
}
return y;}
立即学习“C++免费学习笔记（深入）”；
3. 使用示例：对正弦信号进行频谱分析
生成一个含两个频率成分的合成信号，并用FFT提取频域信息：
int main() {
const int N = 8;
vector<Complex> signal(N);
<pre class='brush:php;toolbar:false;'>// 构造信号：sin(2πf1 t) + 0.5*sin(2πf2 t)
for (int i = 0; i < N; i++) {
double t = i / static_cast<double>(N);
signal[i] = sin(2*M_PI*1*t) + 0.5*sin(2*M_PI*3*t);
}
// 执行FFT
vector<Complex> result = fft(signal);
// 输出幅度谱
cout << "Frequency Magnitudes:\n";
for (int i = 0; i < N; i++) {
double mag = abs(result[i]);
cout << "Bin " << i << ": " << mag << '\n';
}
return 0;}
立即学习“C++免费学习笔记（深入）”；
4. 优化建议与注意事项
实际应用中可进一步提升性能与实用性：
- 迭代版本更高效：避免递归开销，使用位逆序排列预处理数组
- 支持非2的幂长度：结合Bluestein或Rader算法扩展通用性
- 精度控制：浮点误差在深层递归中可能累积，注意数值稳定性
- 调用现成库：生产环境推荐使用FFTW等高度优化库
基本上就这些。这个实现帮助理解FFT原理，适合教学和小型项目。掌握其结构后，可逐步过渡到高性能版本或集成专业库。
