快速算法的主要目标为节省计算时间，采取手段主要如下：
减少加法数量
减少乘法数量
减少循环 数量 其中以减少乘法数量最为重要，可以最为高效率节省计算量。
N-point DFT
对于任何点数的离散傅立叶转换(DFT) ，都有其适合的快速算法．
由于线性非时变系统 可以用卷积 Convolution来表示，故我们可以说其运算复杂度为，三个傅立叶转换的计算量（包括两个FTs 以及一个IFT)
3
θ
(
N
l
o
g
N
)
{\displaystyle 3\theta (NlogN)}
θ
(
N
l
o
g
N
)
{\displaystyle \theta (NlogN)}
θ
(
N
)
{\displaystyle \theta (N)}
Replacement of DFTs
对于DFT的计算有复数(complex number)的问题，我们也可以透过矩阵的方式来处理．
下面以四个例子来解说：
(1)
y
1
=
a
x
1
+
2
a
x
2
{\displaystyle y_{1}=ax_{1}+2ax_{2}}
y
1
=
(
a
2
a
)
(
x
1
x
2
)
{\displaystyle y_{1}={\begin{pmatrix}a&2a\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}
y
1
=
a
(
x
1
+
2
x
2
)
{\displaystyle y_{1}=a(x_{1}+2x_{2})}
(
y
1
y
2
)
=
(
a
a
a
a
)
(
x
1
x
2
)
{\displaystyle {\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}a&a\\a&a\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}
y
1
=
a
(
x
1
+
x
2
)
{\displaystyle y_{1}=a(x_{1}+x_{2})}
y
2
=
y
1
{\displaystyle y_{2}=y1}
(
y
1
y
2
)
=
(
a
b
b
a
)
(
x
1
x
2
)
{\displaystyle {\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}a&b\\b&a\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}
(
y
1
y
2
)
=
(
a
+
b
2
a
+
b
2
a
+
b
2
a
+
b
2
)
(
x
1
x
2
)
+
(
a
−
b
2
−
a
−
b
2
−
a
−
b
2
a
−
b
2
)
(
x
1
x
2
)
{\displaystyle {\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}{\frac {a+b}{2}}&{\frac {a+b}{2}}\\{\frac {a+b}{2}}&{\frac {a+b}{2}}\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}+{\begin{pmatrix}{\frac {a-b}{2}}&-{\frac {a-b}{2}}\\-{\frac {a-b}{2}}&{\frac {a-b}{2}}\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}
(
y
1
y
2
)
=
(
a
b
c
a
)
(
x
1
x
2
)
{\displaystyle {\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}a&b\\c&a\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}
(
y
1
y
2
)
=
(
a
a
a
a
)
(
x
1
x
2
)
+
(
0
b
−
a
c
−
a
0
)
(
x
1
x
2
)
{\displaystyle {\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}a&a\\a&a\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}+{\begin{pmatrix}0&b-a\\c-a&0\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}
^ Jian-Jiun Ding, Advanced Digital Signal Processing class note, the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2018&2020.
