汽车网站案例网页设计,软件开发网站模板,快速网站制作,一个人做网站赚钱全世界只有3.14 % 的人关注了数据与算法之美第一节、多项式乘法我们知道#xff0c;有两种表示多项式的方法#xff0c;即系数表示法和点值表示法。什么是系数表示法?所谓的系数表示法#xff0c;举个例子如下图所示#xff0c;A#xff08;x#xff09;6x^3 7x^2 - 10… 全世界只有3.14 % 的人关注了数据与算法之美第一节、多项式乘法我们知道有两种表示多项式的方法即系数表示法和点值表示法。什么是系数表示法?所谓的系数表示法举个例子如下图所示Ax6x^3 7x^2 - 10x 9Bx-2x^34x-5则CxAx*Bx就是普通的多项式相乘的算法系数与系数相乘这就是所谓的系数表示法。那么何谓点值表示法?一个次数为n次的多项式Ax的点值表示就是n个点值所形成的集合{(x0,y0), (x1,y1),..., (xn-1,yn-1)}。其中所有xk各不相同且当k01,……n-1时有ykAxk。一个多项式可以由很多不同的点值表示这是由于任意n个相异点x0x1...xn-1组成的集合都可以看做是这种点值法的表示方法。对于一个用系数形式表示的多项式来说在原则上计算其点值表示是简单易行的我们只需要选取n个相异点x0x1...xn-1然后对k01...n-1求出Axk然后根据霍纳法则求出这n个点的值所需要的时间为On^2。稍后你将看到如果巧妙的选取xk的话适当的利用点值表示可以使多项式的乘法可以在线性时间内完成。所以如果我们能恰到好处的利用系数表示法与点值表示法的相互转化那么我们可以加速多项式乘法下面将详细阐述这个过程达到On*logn的最佳时间复杂度。前面说了当用系数表示法即用一般的算法表示多项式时两个 n次多项式的乘法需要用 On^2的时间才能完成。但采用点值表示法时多项式乘法的运行时间仅为On。接下来咱们要做的是如何利用系数表示法与点值表示法的相互转化来实现多项式系数表示法的On*logn的快速乘法。第二节、多项式的快速乘法 在此之前我们得明白两个概念求值与插值。通俗的讲所谓求值系数-点值是指系数形式的多项式转换为点值形式的表示方式。而插值点值-系数正好是求值的逆过程即反过来它是已知点值表示法而要你转换其为多项式的系数表示法用n个点值对也可以唯一确定一个不超过n-1次多项式这个过程称之为插值。而这个系数表示法与点值表示法的相互转化即无论是从系数表示法转化到点值表示法所谓的求值还是从点值表示法转化到系数表示法所谓的插值求值和插值两种过程的时间复杂度都是On*logn。前面我们已经说了在多项式乘法中如果用系数表示法表示多项式那么多项式乘法的复杂度将为On^2而用点值表示法表示的多项式那么多项式的乘法的复杂度将是线性复杂度为On即 适当的利用点值表示可以使多项式的乘法可以在线性时间内完成。此时读者可以发挥你的想象假设我们以下面这样一种过程来计算多项式的乘法不过在此之前你得先把两个要相乘的多项式Ax和Bx扩充为次数或者说系数为2n次的多项式我们将会得到我们想要的结果系数表示法转化为点值表示法。先用系数表示法表示一个多项式然后对这个多项式进行求值操作即多项式从系数表示法变成了点值表示法时间复杂度为On*logn点值表示法计算多项式乘法。用点值表示法表示多项式后计算多项式的乘法线性复杂度为On点值表示法转化为系数表示法。最终再次将点值表示法表示的多项式转变为系数表示法表示的多项式这一过程为On*logn。那么综上上述三项操作系数表示法表示的多项式乘法总的时间复杂度已被我们降到了On*lognnn*lognON*logN。如下图所示从左至右看过去这个过程即是完成多项式乘法的计算过程。不过完成这个过程有两种方法一种就是前面第一节中所说的普通方法即直接对系数表示法表示的多项式进行乘法运算复杂度为On^2它体现在下图中得Ordinary multiplication过程。还有一种就是本节上文处所述的三个步骤1、将多项式由系数表示法转化为点值表示法(点值过程2、 利用点值表示法完成多项式乘法3、将点值表示法再转化为系数表示法插值过程。三个步骤下来总的时间复杂度为ON*logN。它体现在下图中的Evaluation Pointwise multiplication Interpolation 三个合过程。由上图中你也已经看到了。我们巧妙的利用了关于点值形式的多项式的线性时间乘法算法来加快了系数形式表示的多项式乘法的运算速度。在此过程中我们的工作最关键的就在于以On*logn的时间快速把一个多项式从系数形式转换为点值形式求值我们即称之为FFT然后再以On*logn的时间从点值形式转换为系数形式插值我们即称之为FFT逆。最终达到了我们以最终的系数形式表示的多项式的快速乘法为ON*logN的时间复杂度。好不令人心生快意。对上图有一点必须说明项w2n是2n次单位复根。且不容忽视的是在上述两种表示法即系数表示法和点值表示法相互转换的过程中 都使用了单位复根才得以在On*logn的时间内完成求值与插值运算至于何谓单位复根请参考相关资料。因为为了保证本文的通俗易懂性无意引出一大堆公式或定理。第三节、FFT注本节有相当部分文字来自算法导论中文版第二版以及维基百科。在具体介绍FFT之前我们得熟悉知道折半定理是怎么一回事儿如果n0且n为偶数那么n个n次单位复根的平方等于n/2个n/2个单位复根。我们已经知道通过使用一种称为快速傅里叶变换FFT的方法可以在On*logn的时间内计算出DFTna而若采用直接的方法复杂度为On^2。FFT就是利用了单位复根的特殊性质。推荐阅读《数学建模算法与应用》你将看到FFT方法运用的策略为分治策略所谓分治即分而治之。两个多项式Ax与Bx相乘的过程中FFT用Ax中偶数下标的系数与奇数下标的系数分别定义了两个新的次数界为n/2的多项式A[0]x和A[1]xA[0](x) a0 a2x a4x2 ··· an-2xn/2-1,A[1](x) a1 a3x a5x2 ··· an-1xn/2-1. 注意A[0]包含了A中所有偶数下标的系数下标的相应二进制数的最后一位为0而A[1]包含A中所有奇数下标的系数下标的相应二进制数的最后一位为1。有下式 这样求Ax在处的问题就转换为1求次数界为n/2的多项式A[0]与A[1]在点 的值2将上述结果进行组合。 下面我们用N次单位根WN来表示。为了简单起见我们下面设待变换序列长度n 2r。 根据上面单位根的对称性求级数时可以将求和区间分为两部分Fodd(k) 和 Feven(k)是两个分别关于序列奇数号和偶数号序列N/2点变换。由此式只能计算出yk的前N/2个点对于后N/2个点注意Fodd(k) 和 Feven(k) 都是周期为N/2的函数由单位根的对称性于是有以下变换公式。这样一个N点变换就分解成了两个N/2点变换照这样可继续分解下去。这就是库利-图基快速傅里叶变换算法的基本原理。此时我们已经不难分析出此时算法的时间复杂度将为O(NlogN)。ok没想到本文之中还是出现了这么多的公式没办法搞这个FFT就是个纯数学活儿。之前买的一本小波与傅里叶分析基础也是如此就是一本数学公式和定理的聚集书。不过能看懂更好实在无法弄懂也只权当做个稍稍了解。好了下面咱们来简单理解下FFT中的蝶形算法本文将告结束。如下图所示 有人这样解释蝶形算法对于N2的x次方点的离散信号把它按索引位置分成两个序列分别为024....2K记为A和135....2K-1记为B由傅立叶变换可以推出N点的傅立叶变换前半部分的结果为AB*旋转因子后半部分的结果为A-B*旋转因子。于是求N点的傅立叶变换就变成分别求两个N/2点序列的傅立叶变换对每一个N/2点的序列递归前面的步骤直到只有两点的序列就只变成简单的加减关系了。把这些点的加减关系用线连接看上去就是个蝶形。ok更多可参考算法导论第30章。举一个例子我们知道4X4的矩阵运算如果按常规算法的话仍要进行64次乘法运算和48次加法这将耗费较多的时间于是在H.264中有一种改进的算法蝶形算法可以减少运算的次数。这种矩阵运算算法构造非常巧妙利用构造的矩阵的整数性质和对称性可完全将乘法运算转化为加法运算。如下图所示版权归原作者所有转载仅供学习使用不用于任何商业用途如有侵权请留言联系删除感谢合作。精品课程推荐选购数学科普正版读物严选“数学思维好物”送给孩子的益智礼物 | 办公室神器算法工程师成长阅读 | 居家高科技理工科男女实用型礼物精选 数据与算法之美用数据解决不可能长按扫码关注
