qt实现快速傅立叶变换代码

以下是一个使用 Qt 实现快速傅立叶变换的示例代码：

#include <QCoreApplication>
#include <QVector>
#include <complex>

typedef std::complex<double> Complex;

void fft(QVector<Complex>& x)
{
    const int N = x.size();
    if (N <= 1) return;

    QVector<Complex> even(N/2), odd(N/2);
    for (int i = 0; i < N/2; ++i) {
        even[i] = x[2*i];
        odd[i] = x[2*i+1];
    }

    fft(even);
    fft(odd);

    for (int k = 0; k < N/2; ++k) {
        Complex t = std::polar(1.0, -2 * M_PI * k / N) * odd[k];
        x[k] = even[k] + t;
        x[k+N/2] = even[k] - t;
    }
}

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    QVector<Complex> x = {1, 2, 3, 4};
    fft(x);

    for (const auto& c : x) {
        qDebug() << c;
    }

    return a.exec();
}

这个代码使用递归实现了快速傅立叶变换，输入一个长度为 $N$ 的复数向量，输出它的傅立叶变换。在每一层递归中，将输入向量分成偶数项和奇数项两个子向量，分别递归计算它们的傅立叶变换，然后将它们合并成一个更长的傅立叶变换。最终得到的傅立叶变换的长度是 $N$，它的每一项都是输入向量的傅立叶变换的某个系数。