本节将简单介绍从平方复杂度到nlogn复杂度的多项式乘法计算

---

假设我们有多项式$A(n)$和多项式$B(n)$,要求$A(n)\ast B(n)$

显然最暴力的就是两重循环的枚举,时间复杂度$O(n^2)$

分治与优化

分治优化下的时间复杂度能达到$O(n^{log3})$

首先对A(n)和B(n)中缺的项补0(让系数为0),方便后续计算

分治的本质是将原问题不断划分为若干个子问题,如何构造这样的关系呢?

将$A(n)=a_0+a_1{x}^1+a_2{x}^2+...+a_n{x}^n$分为两半

即令:

$A_0=a_0+a_1{x}^1+a_2{x}^2+...+a_{\lceil \frac{n}{2}\rceil }{x}^{\lceil \frac{n}{2}\rceil }$

$A_1=a_{\lceil \frac{n}{2}+1\rceil }+a_{\lceil \frac{n}{2}\rceil +2}{x}^1+...+a_n{x}^{\lceil \frac{n}{2}\rceil }$

显然有: $A(n)=A_0+A_1{x}^{\lceil \frac{n}{2}\rceil }$

对$B(n)$同理,则$A(n)\ast B(n)$可以表示为:

$A_0{B}_0+A_1{B}_0{x}^{\lceil \frac{n}{2}\rceil }+A_0{B}_1{x}^{\lceil \frac{n}{2}\rceil }+A_1{B}_1{x}^{2\lceil \frac{n}{2}\rceil }\text{ (1)}$

显然我们只需要求出$A_0{B}_0,A_1{B}_0,A_0{B}_1,A_1{B}_1$即可代入求出多项式的结果,而其中A和B的规模为原来的一半,并且同样是求多项式乘法

所以我们现在可以递归去求$F(A_0,B_0),F(A_1,B_0),F(A_0,B_1),F(A_1,B_1)$,base step为n为1时返回系数乘积

但是此时复杂度依然是$O(n^2)$

如何优化呢?

观察(1)式可知我们实际上不需要知道$A_1{B}_0,A_0{B}_1$的值,我们只需要知道$A_1{B}_0+A_0{B}_1$即可

构造$(A_0+A_1)(B_0+B_1)=A_0{B}_1+A_1{B}_0+A_0{B}_0+A_1{B}_1$

则$A_1{B}_0+A_0{B}_1=(A_0+A_1)(B_0+B_1)-(A_0{B}_0+A_1{B}_1)$

所以我们只需要递归求$F(A_0+A_1,B_0+B_1),F(A_0,B_0),F(A_1,B_1)$

此时复杂度为$O(n^{log3})$

快速傅里叶变换

快速傅里叶变换(FFT)的时间复杂度为$O(n\log n)$

对于一个n阶多项式,我们只需要n+1个点便可以确定(证明: 范德蒙特行列式)

所以要计算两个n阶多项式乘法$f(x),g(x)$,我们只需要在f(x)和g(x)上找2n+1个点,然后相乘即可表示出多项式乘法的结果

如果我们知道多项式f(x)的点值,也知道g(x)的点值,那么我们就可以通过O(1)计算出f(x)和g(x)的乘积多项式的点值

所以如果我们能以较低的时间复杂度内将系数表示法转化为点值表示法，再将点值表示法转回系数表示法，就能以较低的时间复杂度计算多项式的乘法

系数转点值

与分治优化类似,我们同样需要构造递归关系,但是FFT的构造关系与分治不同,我们需要构造一些偶函数的性质方便后续利用

对于多项式$f(x)=a_0+a_1{x}^2+a_2{x}^3+...+a_n{x}^n$

我们可以拆分奇偶

$$f(x)=(a_0+a_2{x}^2+...+a_{n-1}{x}^{n-1})+(a_1+a_3{x}^2+...+a_{n-1}{x}^{n-1})x$$

现在奇偶的系数都间隔为2,即$[0,2,4,...,n-1]$,无法点值表示,我们可以传入$x^2$使得系数间隔为1,即$[0,1,2,...,\frac{n-1}{2}]$,此时可以点值表示

所以:

$$f(x)=F_0(x^2)+F_1(x^2)x$$

现在我们发现$F_0$和$F_1$不也是一样的多项式吗,所以我们可以递归下去,直到系数为0

如何利用单位根的性质呢?

首先我们可以回忆一下单位根的性质

为了方便书写,我们用${\omega }_n^k$表示n次单位根:

$$e^{i\frac{2\pi }{N}kn}={\omega }_N^{nk}$$

此时有:

$${\omega }_n^k={\omega }_{cn}^{ck}$$$${\omega }_n^k=-{\omega }_n^{k+\frac{n}{2}}$$$${\omega }_n^0={\omega }_n^n=1$$

因此:

$$f(x)=F_0(x^2)+F_1(x^2)x$$$$f({\omega }_n^k)=F_0({\omega }_n^{2k})+F_1({\omega }_n^{2k}){\omega }_n^k$$$$f({\omega }_n^k)=F_0({\omega }_{\frac{n}{2}}^k)+F_1({\omega }_{\frac{n}{2}}^k){\omega }_n^k$$

你可能会疑问但是这样递归下去依然没有减少计算量啊?

别忘了我们这里$F_1,F_0$都满足$g(x)=g(-x)$

同时这里还有个最重要的性质没用到:

$${\omega }_n^k=-{\omega }_n^{k+\frac{n}{2}}$$

所以

$$f({\omega }_n^{k+\frac{n}{2}})=F_0({\omega }_{\frac{n}{2}}^k)-F_1({\omega }_{\frac{n}{2}}^k){\omega }_n^k$$

所以现在我们只需要计算一半的点即可得到$F_0({\omega }_{\frac{n}{2}}^k),F_1({\omega }_{\frac{n}{2}}^k)$,然后相加即为前一半,相减即为后一半,这样计算量减半

所以如果我们知道对于点$[{\omega }_{\frac{n}{2}}^1,{\omega }_{\frac{n}{2}}^2,{\omega }_{\frac{n}{2}}^3,...,{\omega }_{\frac{n}{2}}^n]$对应的$F_0,F_1$点值,我们就可以快速计算出$f({\omega }_n^k)$的点值表达式

如何计算?还记得我们上面说的吗,递归即可

由此每次递归我们都会将子问题的计算规模减半,显然此时的复杂度即为$O(nlogn)$

点值转系数

在得到点值表达式后,我们可以通过FFT的逆变换得到系数表达式

我们先从DFT的逆变换IDFT开始推导

还记得DFT公式吗?

$$X[k]=\sum _{n=0}^{N-1}x[n]\cdot e^{i\frac{2\pi }{N}kn}$$

我们可以把DFT公式视为矩阵乘法:

$$\left[\begin{array}{ccccc}1& 1& 1& \cdots & 1\\ 1& {\omega }_N^1& {\omega }_N^2& \cdots & {\omega }_N^{N-1}\\ 1& {\omega }_N^2& {\omega }_N^4& \cdots & {\omega }_N^{2(N-1)}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& {\omega }_N^{N-1}& {\omega }_N^{2(N-1)}& \cdots & {\omega }_N^{{(N-1)}^2}\end{array}\right]\left[\begin{array}{c}{a}_0\\ a_1\\ a_2\\ ⋮\\ a_{N-1}\end{array}\right]=\left[\begin{array}{c}{p}_0\\ p_1\\ p_2\\ ⋮\\ p_{N-1}\end{array}\right]$$

其中$\left[\begin{array}{c}{a}_0\\ a_1\\ a_2\\ ⋮\\ a_{N-1}\end{array}\right]$ 为系数表达式,$\left[\begin{array}{c}{p}_0\\ p_1\\ p_2\\ ⋮\\ p_{N-1}\end{array}\right]$ 为点值表达式

所以如果我们要求系数表达式,只需要求原来的逆矩阵即可

注意到:

$${\left[\begin{array}{ccccc}1& 1& 1& \cdots & 1\\ 1& {\omega }_N^1& {\omega }_N^2& \cdots & {\omega }_N^{N-1}\\ 1& {\omega }_N^2& {\omega }_N^4& \cdots & {\omega }_N^{2(N-1)}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& {\omega }_N^{N-1}& {\omega }_N^{2(N-1)}& \cdots & {\omega }_N^{{(N-1)}^2}\end{array}\right]}^T=\frac{1}{N}\left[\begin{array}{ccccc}1& 1& 1& \cdots & 1\\ 1& ({\omega }_N^1{)}^{-1}& ({\omega }_N^2{)}^{-1}& \cdots & ({\omega }_N^{N-1}{)}^{-1}\\ 1& ({\omega }_N^2{)}^{-1}& ({\omega }_N^4{)}^{-1}& \cdots & ({\omega }_N^{2(N-1)}{)}^{-1}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& ({\omega }_N^{N-1}{)}^{-1}& ({\omega }_N^{2(N-1)}{)}^{-1}& \cdots & ({\omega }_N^{{(N-1)}^2}{)}^{-1}\end{array}\right]$$

综上则有:

$$X[k]=\sum _{n=0}^{N-1}x[n]\cdot e^{-i\frac{2\pi }{N}kn}$$

所以将一个多项式在分治的过程中乘上的单位根变为其共轭复数，分治完的每一项除以n即可得到原多项式的每一项系数