数据分析方法|梅长林
第二节、多项式的快速乘法
在此之前，我们得明白两个概念，求值与插值。通俗的讲，所谓求值（系数->点值），是指系数形式的多项式转换为点值形式的表示方式。而插值（点值->系数）正好是求值的逆过程，即反过来，它是已知点值表示法，而要你转换其为多项式的系数表示法（用n个点值对也可以唯一确定一个不超过n-1次多项式，这个过程称之为插值）。这个系数表示法与点值表示法的相互转化，无论是从系数表示法转化到点值表示法所谓的求值，还是从点值表示法转化到系数表示法所谓的插值，求值和插值两种过程的时间复杂度都是O（n*logn）。
前面我们已经说了，在多项式乘法中，如果用系数表示法表示多项式，那么多项式乘法的复杂度将为O（n^2）；而用点值表示法表示的多项式，多项式的乘法复杂度将是线性复杂度为O（n），即：适当利用点值表示可以使多项式的乘法在线性时间内完成。
此时读者可以发挥你的想象，假设我们以下面这样一种过程来计算多项式的乘法（不过在此之前，你得先把两个要相乘的多项式A（x）和B（x）扩充为次数或者说系数为2n次的多项式），我们将会得到我们想要的结果：
-
系数表示法转化为点值表示法。先用系数表示法表示一个多项式，然后对这个多项式进行求值操作，即多项式从系数表示法变成了点值表示法，时间复杂度为O（n*logn）。如果你对多项式插值的更多细节感兴趣，可以参考数值分析多项式插值和插值多项式利用牛顿插值法。
-
点值表示法计算多项式乘法。用点值表示法表示多项式后，计算多项式的乘法，线性复杂度为O（n）。想深入了解点值表示法的应用？可以看看多项式插值及克里金插值和Lagrange插值多项式。
-
点值表示法转化为系数表示法。最终再次将点值表示法表示的多项式转变为系数表示法表示的多项式，这一过程为O（n*logn）。关于这种转换过程的详细介绍，可以参考牛顿插值多项式和Newton多项式插值。
综上所述，系数表示法表示的多项式乘法总的时间复杂度已被我们降到了O（nlogn+n+nlogn）=O（n*logn）。这就如同你用神奇的转换咒语，将复杂的数学运算简化成轻松的“魔法”！
从左至右看过去，这个过程就是完成多项式乘法的计算过程。不过，完成这个过程有两种方法：一种就是前面第一节中所说的普通方法，即直接对系数表示法表示的多项式进行乘法运算，复杂度为O（n^2），它体现在下图中的Ordinary multiplication过程。另一种就是本节上文处所述的三个步骤：1、将多项式由系数表示法转化为点值表示法……
是不是感觉数学突然变得有趣了起来？这就是数学的魔力所在，简化复杂，化繁为简，让我们在探索的过程中不断惊叹！
