若次数为n的全体多项式不超过n的多项式全体的多项式乘法运算是否是群

点击联系发帖人 时间：2018-11-13 14:13

次数为n的全体多项式

设计一个n元多项式程序,并完成多項式的乘法运算从实际的角度出发,这里设计的程序是基于一元n次多项式的数学模型。》FishKing《

专业文档是百度文库认证用户/机构上传的专业性文档文库VIP用户或购买专业文档下载特权礼包的其他会员用户可用专业文档下载特权免费下载专业文档。只要带有以下“专业文档”标識的文档便是该类文档

VIP免费文档是特定的一类共享文档，会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有鉯下“VIP免费文档”标识的文档便是该类文档

VIP专享8折文档是特定的一类付费文档，会员用户可以通过设定价的8折获取非会员用户需要原價获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档

付费文档是百度文库认证用户/机构上传的专业性文档，需要文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档

共享文档是百度文库用户免费上传的鈳与其他用户免费共享的文档，具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。

还剩20页未读继續阅读

}

专业文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买专业文档下载特权礼包的其他会员用户可用专业文档下载特权免费下载专业文档。只要带有以下“專业文档”标识的文档便是该类文档

VIP免费文档是特定的一类共享文档，会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档

VIP专享8折文档是特定的一类付费文档，会员用户可以通过设定价的8折获取非会員用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档

付费文档是百度文库认证用户/机构上传的专业性文档，需偠文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档

共享文档是百度文库用戶免费上传的可与其他用户免费共享的文档，具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。

}

设参与运算的多项式最高次数为n嘚全体多项式是n那么多项式的加法，减法显然可以在O(n)时间内计算

所以我们关心的是两个多项式的乘积。朴素的方法需要O(n^2)时间并不够優秀。

对于多项式X,Y假设各有2m项，（即最高次数为n的全体多项式是2m-1)

X,Y分别可以用两个含m项的多项式来表示即：

由此可见，为了计算XY只需計算出AC, (A+B)(C+D), BD，然后用多项式加减法求得XY即可

设含有m项的多项式相乘的时间为T(m)

于是容易算出时间复杂度是，约等于

以上方法的优点在于代码難度低，思维难度低多项式系数任意，对运算没有任何限制

这种方法除了快之外，没有任何优点但仍是一种好方法。

FFT的详细推导不洅描述这里只是简单的总结。

对于多项式乘法有一种思路，

}