我假设一维DFT / IDFT …

所有DFT都使用以下公式：

• X(k) 被转换的样本值（复杂域）
• x(n) 是输入数据样本值（真实或复杂域）
• N 是数据集中样本/值的数量

通常将整个事情乘以归一化常数c。如您所见，对于单个值，您需要进行N计算，因此对于所有样本而言，O(N^2)这很慢。

在这里我的真正的< - >复杂的领域DFT/IDFT在C++中，你还可以找到如何计算二维与一维变换，以及如何变换计算提示N-pointDCT，IDCT由N-pointDFT，IDFT那里。

快速算法

有一些快速算法可以将等式分别分解为 总和的* 奇数 和 偶数
部分（给出总和），这也是每个单个值，但是这两个一半是相同的方程式，但需要不断调整。因此，可以直接从第一个算出一半。这导致每个值。如果您递归地应用它，那么您将获得单个值。所以整个事情变得很棒，但同时也增加了以下限制：
*2x N/2``O(N)``+/-``O(N/2)``O(log(N))``O(N.log(N))

所有DFFT需要输入数据集的大小等于2的幂！

因此可以递归拆分。零填充到2的最大幂的最接近值用于无效的数据集大小（在音频技术中，有时甚至是相移）。
复数

• c = a + i*b
• c 是复数
• a 是它的真实部分（重新）
• b 是它的虚部（Im）
• i*i=-1 是假想单位

所以计算是这样的

加成：

c0+c1=(a0+i.b0)+(a1+i.b1)=(a0+a1)+i.(b0+b1)

乘法：

c0*c1=(a0+i.b0)*(a1+i.b1)
     =a0.a1+i.a0.b1+i.b0.a1+i.i.b0.b1
     =(a0.a1-b0.b1)+i.(a0.b1+b0.a1)

极性形式

a = r.cos(θ)
b = r.sin(θ)
r = sqrt(a.a + b.b)
θ = atan2(b,a)
a+i.b = r|θ

sqrt

sqrt(r|θ) = (+/-)sqrt(r)|(θ/2)
sqrt(r.(cos(θ)+i.sin(θ))) = (+/-)sqrt(r).(cos(θ/2)+i.sin(θ/2))

真实- >复杂转换：

complex = real+i.0