找到一个据称是O（n）的卷积算法！

ssikkiss · 发表于 2010-6-11 23:52:40

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

搞大数的大家有福了！刚搜到的，还没来得及细看，先发出来在说！

ssikkiss · 发表于 2010-6-12 00:08:26

不理解里面的horner方法，搜了下，原来：秦九韶算法是中国南宋时期的数学家秦九韶提出的一种多项式简化算法。在西方被称作霍纳算法（Horner algorithm或 Horner scheme），是以英国数学家威廉·乔治·霍纳命名的. 　　把一个n次多项式f(x)=a[n]x^n+a[n-1]x^(n-1)+......+a[1]x+a[0]改写成如下形式：　　f(x)=a[n]x^n+a[n-1]x^(n-1))+......+a[1]x+a[0] 　　=(a[n]x^(n-1)+a[n-1]x^(n-2)+......+a[1])x+a[0] 　　=((a[n]x^(n-2)+a[n-1]x^(n-3)+......+a[2])x+a[1])x+a[0] 　　=...... 　　=(......((a[n]x+a[n-1])x+a[n-2])x+......+a[1])x+a[0]. 　　求多项式的值时，首先计算最内层括号内一次多项式的值，即　　v[1]=a[n]x+a[n-1] 　　然后由内向外逐层计算一次多项式的值，即　　v[2]=v[1]x+a[n-2] 　　v[3]=v[2]x+a[n-3] 　　...... 　　v[n]=v[n-1]x+a[0] 　　这样，求n次多项式f(x)的值就转化为求n个一次多项式的值。　　（注：中括号里的数表示下标）　　结论：对于一个n次多项式，至多做n次乘法和n次加法。

ssikkiss · 发表于 2010-6-12 05:49:27

一大早起来，我又来思考这个文章，差点让我晕死：其中未对加法和乘法进行任何定义，所以我按正常的加法和乘法来理解。其中第2步算出的U（x）和V（x）将是一个大数，而且这步的计算过程因为结果越来越大也不是O（n）的； U（x）和V（x）是大数，直接导致第三步A=U（x）* V（x）的计算是O（n^2）；

ssikkiss · 发表于 2010-6-12 06:05:44

大概弄懂文意了，作者的向量U和V，因为仅仅是向量，所以作者在第1步给它选了一个进制x，通过第2步把这组向量算成2个大数U（X），和V（X），第3步大数相乘得到A，第4步再求各结果向量。

无心人 · 发表于 2010-6-12 10:04:05

高德纳的书里的习题已经对整数卷积给出了个很好的算法可惜，偶看不懂

ssikkiss · 发表于 2010-6-12 12:16:48

第2，3楼仅是我的主观臆断，请大家不要受此影响而不看原文

gxqcn · 发表于 2010-6-13 08:46:04

粗略地阅读了一下，它的第四步有（2n-2）次除法，但每次除法实则是O(n)的复杂度，所以该算法效率将十分低下。该文发表于《计算数学》1991年2月，如果真有价值，想必现在已到处在引用了。

medie2005 · 发表于 2010-6-13 12:41:33

看到中文标题的论文, 就觉得悬了.

mathe · 发表于 2010-6-13 15:28:43

我是看了标题就根本不去看它了

账号		自动登录	找回密码
密码			欢迎注册

[分享] 找到一个据称是O（n）的卷积算法！

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。