多项式乘法与傅里叶变换
多项式乘法与傅里叶变换
我们知道，有二种表明代数式的方式，即指数表示法和点值表示法。
此章，我们来详细介绍代数式的加法及其迅速傅里叶变换优化算法。
此次我们从多项式乘法逐渐，随后详细介绍FFT优化算法的基本原理与完成。与此同时，文中虽牵涉到许多公式和定律（自然，我能尽可能舍弃一些与文中我们要详细介绍的管理中心內容不相干的定律或证实，只求确保能让阅读者便于接纳或了解），但尽可能确保浅显易懂，以让阅读者可以看个搞清楚。
有盆友提议，优化算法专一种，就ok，没必要每个都学习培训。
但本人确实抑制不住自身的兴趣爱好，便是想写，当无法增加逼迫自身不写时，这一经典算法科学研究系列产品便一直那么写下来了。
多项式乘法
我们知道，有二种表明代数式的方式，即指数表示法和点值表示法。什么是系数表示法?说白了的指数表示法。
举个事例如下图所显示，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）。
尊重原创文章，转载请注明出处与链接：http://www.mxiao.cn/1541/new/144026/违者必究！
以上就是洛阳达内教育IT培训中心 小编为您整理多项式乘法与傅里叶变换的全部内容。
