系数表示法与点值表示法

一个 $N$ 次多项式有 $N+1$ 个系数, 它们可以唯一确定这个多项式; 此外可以取 $N+1$ 个点, 计算多项式在这些点的值; 这样 $N+1$ 个不同的键值对也可以唯一确定一个 $N$ 次的多项式

在计算多项式乘法时, 系数表示法需要 $O(n^2)$ 的时间复杂度, 而点值表示法只需要 $O(n)$ 的复杂度. 这是因为两个多项式乘积在一点的值等于它们俩在这点值的乘积

如果能有很快的方法在系数表示法与点值表示法之间转换, 将能极大地加速多项式乘法

单位根与FFT

首先将系数表达式转化为点值不能朴素地计算, 这是因为计算一个点值需要 $N$ 次乘法, 这样复杂度仍然是 $O(n^2)$ , 没有意义. 不过若是取单位根

x_k=e^{2k\pi/N}

它的任意次方都可以以常数复杂度求出, 而不用进行乘法

x_k^m=e^{2mk\pi/N}

如果有多项式

f(x)=a_0+a_1x+\cdots+a_Nx^N=\sum_{n=0}^{N-1} a_kx^n

那么

f(x_k)=\sum_{n=0}^{N-1} a_ke^{i2\pi nk/N}

这个形式容易让人想起一位故人, 因而不妨取单位根是负指数,那么不妨再直接一点

f(x_k)=\sum_{n=0}^{N-1} a_ke^{-i2\pi nk/N}=DFT\{a\}[k]

因而

Note

点值表示是系数表示的离散傅里叶变换

而FFT的复杂度是 $O(n\log n)$ , 这就实现了加速

自然, 将点值表示还原回系数表示, 也只需要进行傅里叶逆变换

a_k=IDFT\{x\}[k]

进行傅里叶逆变换也可以由FFT以 $O(n\log n)$ 的复杂度完成