石家庄58同城招聘信息_手机app软件制作工具_品牌网络seo方案外包_百度认证证书

目标

两个向量（每个向量各自对应一个多项式）的简单相乘（时间复杂度$O(n^2)$）可以通过两个向量各自对应的离散傅里叶变换的相乘（时间复杂度$O(n\cdot \text{lg }n)$）来代替，以此降低计算的时间复杂度。

核心思路

点值表达式的乘法仅需$O(n)$复杂度，因此系数表达式的多项式乘法希望通过点值表达式来作为媒介来完成乘法操作，之后再将计算结果转化为系数表达式。

背景知识(可跳过)

次数界(关键概念)

多项式计算

多项式加法

多项式乘法

这里解释一下为什么$C$的次数界为$n_a+n_b-1$?

$A$的次数界为$n_a$，$A$的最高次数$n_a-1$；同理$B$的次数界为$n_b$，$B$的最高次数$n_b-1$，故$C$的最高次数$n_a+n_b-2$，因此$C$的次数界为$n_a+n_b-1$。

两种表达式的计算

系数表达式

点值表达式

插值多项式的唯一性

证明略，这个定理说明了一件事情：要**唯一确定一个次数界为$n$的多项式$A(x)$需要$n$个点**。

单位复数根

其中${\omega }_n={\omega }_n^1$，即图中的${\omega }_8^1$。

消去引理

其实在这个定理在几何上有很好的直观的理解。

折半定理

求和定理

从几何上就是每个方向的“相对”方向能够被抵消，因此总和为0。

DFT与FFT

DFT

FFT

卷积定理算法

为什么时间复杂度就是低

本质就是在第10-13行，单位复数所具备的性质使得，在得到一个多项式中偶数项的DFT（即算法中的$y^{[0]}$）和奇数项的DFT（即算法中的$y^{[1]}$）之后，仅需$O(n)$的复杂度就可以得到一个多项式中的DFT，因此得到一个多项式的DFT仅需$O(n\cdot \text{lg }n)$复杂度。这就完成了核心思想流程中的求值操作。

而点值的乘法仅需$O(n)$；

插值步骤，即将点值表达式转换为现实中常用的操作也仅需$O(n\cdot \text{lg }n)$。那为什么可以成功转化呢，因为点值表达法给够了$2n$个点，根据插值多项式的唯一性定理，次数界为$2n-1$的多项式$C(x)$被唯一确定。

参考资料：黑书《算法导论》。