并在 N 个样本的有限间隔内对其进行采样。

• 周期性 T 是总样本 （N） 和采样间隔 Δt 的乘积。
• 离散时间点 （tn） 是索引 n 和采样间隔 Δt 的乘积。
• ⍵，整体表示第 k 个频率分量处的频率 bin。
• ⍵k 表示 ⍵ 频率箱中第 n 个索引处的特定频率。

很酷，但 k 到底是从哪里来的???

井变量 k 表示第 k 个频率分量。在每个离散时间样本 n 处，我们将有 k 个构成信号的非周期频率分量。

不幸的是，如果我们有一个高值 N，计算机必须进行大量的计算，这可能会带来问题......我们稍后会谈到这一点。

        因此，使用

        我们可以将方程式改写为：

        我们得到了 DFT。

        但是等一下，我们还没有完成！

        DFT 的方程可以简化，并通过所谓的统一根来表示。

        从本质上讲，统一根是一个复数，当提高到第 n 个整数时，当 n 是正整数时，指数的结果是 1。

        因此，我们可以用单位的第 N 根来表示我们的方程，

        进一步简化为，

        现在，如果你还记得我之前提到的，

        “不幸的是，如果我们有一个高值的 N，计算机必须进行大量的计算，这可能会带来问题......我们稍后会讨论这个问题。

        在计算信号的频谱/频域时，DFT可能被证明是无效的。

        计算时间、负载和复杂性太多了！

        原因如下。

        让我们再看一下我们的DFT方程。

        对于每个 k 值，我们必须处理 N-1 次计算。

        如果我们再看一下早期的视觉效果，以获得更多的视角，

        很明显，如果我们有一个更高的索引 N，我们将不得不处理每 N 个不断增加的 k 个计算量。

        变量 N 还决定了我们的计算机将决定使用多少个索引。我们不仅要担心 k 个计算，还要担心 n。

        因此，最终，当您同时考虑 k 和 n 时，您需要执行 N² 计算。

        如果你听说过Big O Notation，你就会知道这很糟糕。

        让我给你看看。

        随着时间的流逝，随着我们值 N 的增加，我们的整体计算复杂度将呈指数级增长。

        如果我们的数据集中有 3000 个采样数据，那么总共需要 9,000,000 次计算机操作才能遍历整个数据集。请记住，计算复杂性呈指数级增长。

        与较低的 Big-O 复杂性相比，这是巨大的。

        但这就是我们有快速傅里叶变换:)的原因。

七、快速傅里叶变换

        因此，为了缓解 DFT 的计算复杂性随着 N 的增加呈指数级增长的问题，需要进行一些轻微的修改。

        数学家约翰·图基（John Tukey）与约翰·肯尼迪（John F. Kennedy）总统进行了讨论，讨论了使用该国周围的传感器检测苏联核试验的可能性。

        他意识到，为了利用这些传感器，他们需要一种计算复杂度较低的算法。

        他们与James Cooley一起发表了一篇论文，概述了FFT的可用性，以便将计算复杂度从N²降低到nlog₂ n，这是一个极大的改进。

        正如你所看到的，计算以更线性的方式增加，而不是指数增长。

        这使得事情更加高效和可行，尤其是当我们有大量数据点需要计算时。

        让我告诉你为什么。

        让我们再看一下DFT。

        假设我们要计算第二个傅里叶系数 X（1）。