秦九韶算法快速计算多项式的值
风水大师 2023-08-29 07:52www.huluw.com风水师
抛出问题
给定下列一元3次多项式
f(x)=4x^{3}+3x^{2}+2x^{1}+1x^{0} (1)
计算 f(4) 需要进行总共几次乘法运算,几次加法运算?
由3次推广到一元n次多项式
f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+...+a_{1}x^{1}+a_{0}x^{0} (2)
计算 f(4) 需要进行总共几次乘法运算,几次加法运算?
朴素算法
以朴素算法求解(1)的话,计算 f(4) 总共需要
(1+2)+(1+1)+1=6 次乘法
1+1+1=3 次加法
以朴素算法求解(2)的话,计算 f(4) 总共需要
[1+(n-1)]+[1+(n-2)]+[1+(n-3)]+...+1
=n+(n-1)+(n-2)+...+1
=\frac{n(n+1)}{2} 次乘法 (3)
n1=n 次加法 (4)
由(3)(4)可知,用朴素算法计算一元n次多项式时,乘法运算的时间复杂度为 O(n^{2}) ,
加法运算的时间复杂度为 O(n) 。当n很小时,乘法的次数尚可接受,当n很大时,乘法的次数将会影响程序的性能。
那么是否存在一种方法可以降低乘法运算的次数呢?是的,就是接下来要介绍的秦九韶算法。
秦九韶算法
一句话概括秦九韶算法是一种将一元n次多项式转换为n个一次式的简化算法。
以(1)为例,运用秦九韶算法
f(x)=4x^{3}+3x^{2}+2x^{1}+1x^{0}
=x(4x^{2}+3x^{1}+2)+1
=x(x(4x+3)+2)+1
计算 f(4) 时,计算最内层括号内一次多项式的值
4x+3=44+3=19
然后由内向外逐层计算一次多项式的值
x19+2=419+2=78
\Rightarrow x78+1=478+1=313
可以看到,一共进行了3次乘法,3次加法。并推出计算(2)时,总共需要至多n次乘法,n次加法。也就是说使用秦九韶算法计算一元n次多项式时,乘法运算的时间复杂度为 O(n) ,加法运算的时间复杂度为 O(n) 。对比朴素算法,大大简化了乘法运算的次数。
程序设计
秦九韶算法作为计算一元n次多项式的最优算法,怎么用代码实现呢?
给定次数和系数就可以唯一确定一个多项式,系数用一个数组存储,数组中的元素下标从 0\sim n ,刚好对应存入 a_{0}\sim a_{n} 。
然后po出(2)的秦九韶方法
f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+...+a_{1}x^{1}+a_{0}
=(...((a_{n}x+a_{n-1})x+a_{n-2})x+...+a_{1})x+a_{0}
可以发现,每一层的运算都是固定的格式 a_{i}x+a_{i-1} ,所以可以用一个 for 循环实现。
具体实现可参考我上传到GitHub上的代码,初次使用GitHub,还在熟悉ing...
第一次在知乎上发文,在内容上力求循序渐进,从问题导入引出解决办法,这也是我学习该算法时的逻辑顺序。
上一篇:调料大全:34种常见厨房调料用法大全
下一篇:五线谱入门基础教程
风水布局
- 属鸡和属狗情感合盘 佩戴吉祥物可避免感情之不
- 属蛇男和属马女相配吗
- 狂月今日星座运势预测今日星座运势分析2025年
- 孕妇梦中吃樱桃象征意义与心理解读
- 梦中小试探梦中情境揭露你的态度,小三的态度
- 梦里的丰收稻穗与麦穗的收获场景揭秘
- 生活中爱美的生肖,颜值非常高
- 属狗人今日有偏财运吗 属狗人偏财运佩戴什么好
- 三月老牛遍地走什么意思 2025年三月出生属牛人命
- 女人梦中与冤家争执,情感冲突显现
- 哥哥的八字配对算命 算命婚姻八字配对
- 女人梦到蛇的含义与暗示梦境解析及预示意义探
- 可能与小三共夫的血型星座女生
- 女人梦中现娘家父亲身影,梦境情感深度解读
- 观音灵签中签安稳 观音灵签中签签文
- 五种鼻子面相揭示婚姻不顺的特征分析