多项式乘法与傅里叶变换
来源：洛阳达内教育IT培训中心 时间：2021/9/18 14:15:18
但本人确实抑制不住自身的兴趣爱好，便是想写，当无法增加逼迫自身不写时，这一经典算法科学研究系列产品便一直那么写下来了。
多项式乘法
我们知道，有二种表明代数式的方式，即指数表示法和点值表示法。什么是系数表示法?说白了的指数表示法。
举个事例如下图所显示，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）的较好算法复杂度。
前边讲了，当用指数表示法，即用一般的优化算法表明代数式时，2个n次代数式的加法必须用O（n^2）的時间才可以进行。
但选用点值表示法时，多项式乘法的运作時间仅为O（n）。
在线咨询
电话咨询