FFT/FWT 相关理论自我复习

下文下标一般从 \(0\) 开始。

卷积：记的数组 \(a,b\) 在运算 \(\circ\) 下的卷积 \(a\circ b=c\)，其中 \(c_k=\sum\limits_{i\circ j=k} a_ib_j\)。

直接暴力计算卷积复杂度为 \(O(n^2)\)，其中 \(n\) 为数组长度。

DFT-IDFT

一般快速计算特殊卷积的方法为构造 DFT 变换：

欲构造可逆的 DFT 变换 把长度为 \(n\) 的数组映射到长度为 \(n\) 的数组，满足 \(\texttt{DFT}(a)\times \texttt{DFT}(b)=\texttt{DFT}(c)\)。

设 DFT 的逆变换 \(\texttt{IDFT}=\texttt{DFT}^{-1}\)，此时 \(c=\texttt{IDFT}(\texttt{DFT}(a)\times \texttt{DFT}(b))\)，于是我们只需快速做 \(\texttt{DFT},\texttt{IDFT}\) 变换即可。

由于「DFT 变换 把长度为 \(n\) 的数组映射到长度为 \(n\) 的数组」，于是设 \(\vec{u}\)

FFT

快速计算 \(a\times b=c\)，其中 \(c_k=\sum\limits_{i+j=k} a_ib_j\)。