快速傅里叶变换与多项式乘法有什么关系

第一节、多项式乘法

    我们知道，有两种表示多项式的方法，即系数表示法和点值表示法。什么是系数表示法?所谓的系数表示法，举个例子如下图所示，A（x）=6x^3 + 7x^2 - 10x + 9，B（x）=-2x^3+4x-5，则C（x）=A（x）*B（x）就是普通的多项式相乘的算法，系数与系数相乘，这就是所谓的系数表示法。

    那么，何谓点值表示法?。一个次数为n次的多项式A（x）的点值表示就是n个点值所形成的集合：{(x0,y0), (x1,y1),..., (xn-1,yn-1)}。其中所有xk各不相同，且当k=0，1,……，n-1时，有y（k）=A（xk）。

    一个多项式可以由很多不同的点值表示，这是由于任意n个相异点x0，x1，...，xn-1组成的集合，都可以看做是这种点值法的表示方法。对于一个用系 数形式表示的多项式来说，在原则上计算其点值表示是简单易行的，我们只需要选取n个相异点x0，x1，...，xn-1，然后对k=0，1，...，n- 1，求出A（xk），然后根据霍纳法则，求出这n个点的值所需要的时间为O（n^2）。

    稍后，你将看到，如果巧妙的选取xk的话，适当的利用点值表示可以使多项式的乘法可以在线性时间内完成。所以，如果我们能恰到好处的利用系数表示法与点值 表示法的相互转化，那么我们可以加速多项式乘法（下面，将详细阐述这个过程），达到O（n*logn）的最佳时间复杂度。

    前面说了，当用系数表示法，即用一般的算法表示多项式时，两个 n次多项式的乘法需要用 O（n^2）的时间才能完成。但采用点值表示法时，多项式乘法的运行时间仅为O（n）。接下来，咱们要做的是，如何利用系数表示法与点值表示法的相互转化 来实现多项式系数表示法的O（n*logn）的快速乘法。

第二节、多项式的快速乘法

    在此之前，我们得明白两个概念，求值与插值。通俗的讲，所谓求值（系数->点值），是指系数形式的多项式转换为点值形式的表示方式。而插值（点值 ->系数）正好是求值的逆过程，即反过来，它是已知点值表示法，而要你转换其为多项式的系数表示法（用n个点值对也可以唯一确定一个不超过n-1次 多项式，这个过程称之为插值）。而这个系数表示法与点值表示法的相互转化，即无论是从系数表示法转化到点值表示法所谓的求值，还是从点值表示法转化到系数 表示法所谓的插值，求值和插值两种过程的时间复杂度都是O（n*logn）。

    前面，我们已经说了，在多项式乘法中，如果用系数表示法表示多项式，那么多项式乘法的复杂度将为O（n^2），而用点值表示法表示的多项式，那么多项式的 乘法的复杂度将是线性复杂度为O（n），即：  适当的利用点值表示可以使多项式的乘法可以在线性时间内完成。此时读者可以发挥你的想象，假设我们以下面 这样一种过程来计算多项式的乘法（不过在此之前，你得先把两个要相乘的多项式A（x）和B（x）扩充为次数或者说系数为2n次的多项式），我们将会得到我 们想要的结果：

• 系数表示法转化为点值表示法。先用系数表示法表示一个多项式，然后对这个多项式进行求值操作，即多项式从系数表示法变成了点值表示法，时间复杂度为O（n*logn）；
• 点值表示法计算多项式乘法。用点值表示法表示多项式后，计算多项式的乘法，线性复杂度为O（n）；
• 点值表示法转化为系数表示法。最终再次将点值表示法表示的多项式转变为系数表示法表示的多项式，这一过程，为O（n*logn）。
   

    那么，综上上述三项操作，系数表示法表示的多项式乘法总的时间复杂度已被我们降到了O（n*logn+n+n*logn）=O（N*logN）。

    如下图所示，从左至右，看过去，这个过程即是完成多项式乘法的计算过程。不过，完成这个过程有两种方法，一种就是前面第一节中所说的普通方法，即直接对系 数表示法表示的多项式进行乘法运算，复杂度为O（n^2），它体现在下图中得Ordinary multiplication过程。还有一种就是本节上文处所述的三个步骤：1、将多项式由系数表示法转化为点值表示法(点值过程）；2、 利用点值表示法完成多项式乘法；3、将点值表示法再转化为系数表示法（插值过程）。三个步骤下来，总的时间复杂度为O（N*logN）。它体现在下图中的 Evaluation + Pointwise multiplication + Interpolation 三个合过程。

    由上图中，你也已经看到了。我们巧妙的利用了关于点值形式的多项式的线性时间乘法算法，来加快了系数形式表示的多项式乘法的运算