我假设一维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
