欢迎来到三一办公! | 帮助中心 三一办公31ppt.com(应用文档模板下载平台)
三一办公
全部分类
  • 办公文档>
  • PPT模板>
  • 建筑/施工/环境>
  • 毕业设计>
  • 工程图纸>
  • 教育教学>
  • 素材源码>
  • 生活休闲>
  • 临时分类>
  • ImageVerifierCode 换一换
    首页 三一办公 > 资源分类 > PPT文档下载  

    算法合集之《多项式乘法》.ppt

    • 资源ID:6596878       资源大小:542.50KB        全文页数:29页
    • 资源格式: PPT        下载积分:15金币
    快捷下载 游客一键下载
    会员登录下载
    三方登录下载: 微信开放平台登录 QQ登录  
    下载资源需要15金币
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    算法合集之《多项式乘法》.ppt

    多项式乘法,张家琳复旦大学附属中学,引言,多项式是最基本的数学工具之一,由于其形式简单,且易于用计算机对其进行各种计算,在当今的社会中应用越来越广。不仅在像Maple这样的数学软件中有着举足轻重的作用,在工程、信息等诸多领域中都有着广阔的应用。,下面我们给出几个多项式逼近的例子:,多项式的基本运算,加法运算,求值运算,乘法运算,普通的多项式乘法运算,多项式乘法是一个很常见的问题,在通常的算法中,两个 次多项式的乘法需要用 的时间才能完成。,让我们先来看一看这样的算法是如何进行的:,.,在上面的过程中,似乎我们觉得这个算法并没有做任何多余的事情,因为我们必须考虑每一组,它们的乘积对最终的结果都会产生影响。而且我们不能通过调整计算顺序从根本上降低算法时间复杂度,至多只能使其常数因子稍小一些。,如果我们不能跳出以上思维的局限,我们就不可能在根本上降低算法的时间复杂度。,让我们首先换一个角度来考察多项式。,多项式的点值表示法,首先让我们来看多项式的另一种表示方法:点值表示法,即用(其中,互不相同)来表示一个不超过 次多项式。,给定一个多项式,要给出n组点值对最简单的方法是任选 n个互不相同的xi,依次求出多项式在这n个点的值。,用n个点值对也可以唯一确定一个不超过n-1次多项式,这个过程称之为插值。,引理1(多项式插值的唯一性),对于任意n个点值对组成的集合,其中 互不相同,则存在唯一的次数不超过n-1的多项式,满足,continue,存在性:,已知,不妨记为XA=Y,X是范德蒙矩阵,利用行列式的变换可得该矩阵的行列式的值为,因此X有逆矩阵。,唯一性:,若两个函数次数不超过n-1次的多项式 均符合题意,则多项式 有n个根,且 为不超过n-1次的多项式,所以,即。,back,点值多项式的乘法,因此:适当的利用点值表示可以使多项式的乘法可以在线性时间内完成!,因为f(x)g(x)的次数为n-1,r(x)的次数为2n-2,因此确定r(x)需要2n-1个点值对,而现在我们只有n个点值对。,我们可以通过对f(x)与g(x)的点值对个数的 扩充来解决这个问题,即将f(x),g(x)的点值对在一开始就取为2n-1。,利用点值表示法改善多项式系数表示法的乘法,下面让我们来看一看我们是否能够利用点值表示法在计 算多项式乘法时的线性时间来提高系数表示法的多项式乘 法的速度。为了做到这一点,我们需要做:将多项式由系数表示法转化为点值表示法(点值过程)利用点值表示法完成多项式乘法 将点值表示法再转化为系数表示法(插值过程)其中第二步只需要线性时间。问题的关键转化为第一 第三步。,continue2,continue1,continue3,1.由系数表示法转化为点值表示法。(点值过程),注意!x0,x1,xn-1是由我们自己选择的,我们可以充分利用这一点通过适当的选择使转化过程降为O(n log n)。,这里我们选择1的n次单位根作为x0,x1,xn-1,即,其中,引理2:对任何整数n=0,k=0,j0,成立:,证明:,折半定理,注意到,中包含了f中所有偶下标的系数,而 中包含了f中所有奇下标的系数。,并记,求 与 在点 的值。,问题:求,设n为偶数(否则可以通过添加高次零项使n化为偶数)。,另一方面,由折半定理:,并不是n个不同的数,而是仅由1的n/2次单位根组成,每个根恰好出现2次。,由此可以看到子问题与原问题形式相同,但规模缩小一半,这启示我们可以利用分治的思想通过递归来解决这个问题。,递归算法的具体实现过程,递归边界条件,Function transform(a:atype):y:ytype;,if n=1 then return a0,递归预处理,if odd(n)then begin inc(n);an-1:=0;end;,递归过程,For k:=0 to n-1 do 利用,计算,可以证明,以上计算方法的时间复杂度为O(n log n)。,back,2将点值表示法再转化为系数表示法。(插值过程),点值过程所解决的问题可以等效为一个矩阵方程:,插值过程是点值过程的逆运算。这个问题比前一个问题看起来更复杂,但事实上,通过适当的转化可以把这个问题转化为前一个问题。,记为,Y,A,点值过程,插值过程,如果,存在,引理3,利用引理3,我们就可以很容易的解决插值的问题。,Y,A,可等效为矩阵方程:,因此,我们可以充分利用点值过程的方法求出多项式的系数表达。,递归边界条件,Function transform(a:atype):y:ytype;,if n=1 then return a0,递归预处理,if odd(n)then begin inc(n);an-1:=0;end;,递归过程,For k:=0 to n-1 do 利用,计算,back,a:atype,y:ytype,y0,yn-1:=0;,递归结束后再将a中每一个数除以n。,多项式乘法的算法流程,问题:f(x),g(x)是两个n-1次的多项式,已知f(x)g(x)的系数表示,求出r(x)=f(x)*g(x)的系数表示。,算法流程:,1.预处理:通过加入n-1个值为0的高价次数,使f(x)g(x)的次数增加到2n-2。这是为了使点值对的个数足够能够唯一确定r(x)。,2.点值:利用分治的方法,通过函数transform求出f(x)与g(x)在1的2n-1次单位根处的值。,3.点乘:将f(x),g(x)在各点的值逐点相乘,计算出r(x)在各点的值。,4.插值:互换a与y的作用,再利用函数transform求r(x)的系数表示,并注意要将结果除以次数作为最后结果。,以上第1、第3步的执行时间都是O(n),第2、第4步的执行时间都是O(n log n)。,算法改进,在函数transform中,我们是用递归的方式来求解,我们对n=8的情况来具体演示一下递归调用的过程。,但是递归的方法对空间的要求很高,从函数transform中可以看到每次递归调用时都需要新的系数数组传入递归过程内部。而通过刚才的演示,我们发现我们也可以用从底向上迭代的方法来进行。,迭代算法的具体实现过程,初始化,预处理,通过增加高次零项使将多项式的次数增加到2的幂次。,Function transform_better(a:atype):y:ytype;,y:=a;,迭代过程,For k:=1 to lg n do 对数组进行恰当的合并并将结果放到数组恰当的位置。,y,y,y,y,back,下面我们将本文介绍的方法与普通的多项式乘法做一个比较。,测试环境:PIII 500 128M RAM,

    注意事项

    本文(算法合集之《多项式乘法》.ppt)为本站会员(牧羊曲112)主动上传,三一办公仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一办公(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    备案号:宁ICP备20000045号-2

    经营许可证:宁B2-20210002

    宁公网安备 64010402000987号

    三一办公
    收起
    展开