加法与乘法对算法性能的影响
加法与乘法对算法性能的影响
提问于 2013-02-19 09:45:29
我正在研究如何优化算法。(Skiena教授的算法指南)
其中一个练习要求我们优化一个算法：
Suppose the following algorithm is used to evaluate the polynomial
p(x) = a^(xn) + a^n−1(xn−1) + . . . + a(x) + a
p := a0;
xpower := 1;
for i := 1 to n do
xpower := x ∗ xpower;
p := p + ai ∗ xpower
end(这里xn，xn-1.是指定给不同常量的名称。
在对此进行了思考之后，我发现改进该算法的唯一方法如下
p := a0;
xpower := 1;
for i := 1 to n do
xpower := x ∗ xpower;
for j := 1 to ai
p := p + xpower
next j
next i
end有了这个解决方案，我把第二个乘法转换成一个for循环中的加法。
我的问题：
- 你有没有其他方法来优化这个算法？
- 我建议的替代方案是否比原来的更好？(编辑:正如评论中所建议的，这个问题虽然与问题有关，但也值得提出另一个问题。(请忽略。)
回答 1
Software Engineering用户
回答已采纳
发布于 2013-02-19 10:18:28
标准的解决方案是注意到，一个有许多乘法与相同的数字x。
所以而不是
p(x) = a_n*x^n + a_n−1*x^n−1 + . . . + a_1*x + a_0有人可能会写
p(x) = (...((a_n*x) + a_n−1)x + ... + a_1)*x + a_0也许更容易读懂：
p(x) := a_3*x^3 + a_2*x^2 + a_1*x + a_0
q(x) := ((a_3*x + a_2)*x + a_1)*x + a_0
p(x) == q(x)我们称之为这样的评价霍纳法。大致翻译为：
p := a_n;
for i is n-1 to 0
p := p*x + a_iHorner的方法有n个乘法和n个加法，并且是最优的。
页面原文内容由Software Engineering提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://softwareengineering.stackexchange.com/questions/187536
复制相关文章
相似问题
腾讯云开发者
