FFT（快速傅里叶变换）

FFT（快速傅里叶变换）

前言

又要补之前的知识，艹。

快速傅里叶变换 (fast Fourier transform), 即利用计算机计算离散傅里叶变换（DFT)的高效、快速计算方法的统称，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。

也就是说 ：FFT用来加速两个多项式的乘法。

建议学习一下有关复数的知识，这里 ~~我水了一篇博客。~~

多项式的系数表示法和点值表示法

系数表示法

一个$n - 1$ 次的 $n$ 项多项式 $f(x)$ 可以表示为 $f(x) = \sum_{i= 0}^{n- 1} a_ix^i$

即：

\[f(x) = a_0 + a_1x^1 + a_2x^2+a_3x^3+\cdots+a_{n - 1}x^{n - 1} \]

这就是我们平常最常用的 系数表示法

点值表示法

现在有一个多项式 $f(x)$ 我们可以把它在坐标系上表示出来

把多项式放到平面直角坐标系里面，看成一个函数
把 $n$ 个不同的 $x$ 代入，会得出 $x$ 个不同的 $y$，在坐标系内就是 $n$ 个不同的点
那么这 $n$ 个点 唯一确定 该多项式，也就是 有且仅有 一个多项式满足 $∀k, f(x_k) = y_k $ （这个其实跟插值差不多，大家可以看看这个拉格朗日插值法）

所以 $f(x)$ 就可以表示成 $f(x) = {(x_0 , f(x_0)),(x_1 , f(x_1))(x_2 , f(x_2) \cdots (x_n - 1 , f(x_n - 1)))}$

这就是 点值表示法

高精度乘法下两种多项式表示法的区别

对于两个用系数表示的多项式，我们把它们相乘时。

很明显这个时间复杂度是 $O(n)$ 的

但是点值表示法就不太一样了，只需要 $O(n)$ 的时间。

假设两个点值多项式分别为

\[f(x) = {(x_0 , f(x_0)),(x_1 , f(x_1))(x_2 , f(x_2) \cdots (x_n - 1 , f(x_n - 1)))} \newline g(x) = {(x_0 , g(x_0)),(x_1 , g(x_1))(x_2 , g(x_2) \cdots (x_n - 1 , g(x_n - 1)))} \]

设他们的乘积是 $h(x)$ 则

\[h(x) = {(x_0 , f(x_0)\cdot g(x_0)),(x_1 , f(x_1)\cdot g(x_1)),(x_2 , f(x_2)\cdot g(x_2)), \cdots (x_n - 1 , f(x_{n - 1})\cdot g(x_{n - 1}))} \]

所以就只用枚举 $O(n)$ 就够了

好像我们只用把系数表示法转换成点值表示法就可以 $O(n)$ 解决多项式乘法了

但是我们朴素的系数转点值要 $O(n^2)$ ，所以我们要引入FFT