算法笔记02--归纳法之多项式求值（Horner规则）

本文主要是介绍算法笔记02--归纳法之多项式求值（Horner规则），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

多项式求值

假设有n+2个实数a0,a1,...,an和x的序列，求多项式

p_nx = a_nx^n + a_n-1x^n-1 + ...+ a_1x + a_0;

则需要乘法：n+n-1 + ...+2+1 = n(n+1)/2

需要加法：n

可见算法效率为O（n^2）

而p_nx = ((...((((a_n)x + a_n-1)x + a_n-2)x + a_n-3)....)x + a_1x) + a_0

因此思路：

p_0x = a_n

p_1x = xp_0x + a_n-1

p_2x = xp_2x + a_n-2

......

p_nx = xp_n-1x + a_0

时间复杂度：

令T（n）为n次项所需加法和乘法之和，这里假设乘法为O（1）

T（1）= 1+1 = 2

T（2）= T（1）+ 1 +1 = T（1）+2

T（n）= T（n-1) + 1 +1 = T（n-1) + 2

因此 T（n）= T（1） + 2*（n-1） = 2*n = n +n

即乘法n次，加法n次，时间复杂度O(n)

代码：

#include<iostream>using namespace std;int solve_px(int a[],int x, int n)
{int px = a[0];for(int i =1; i<n;i++){px = px*x + a[i];}return px;
}int main()
{//px4 = 3*x^4+6*x^3+2*x^2+5*x+6//px0 =         3(a[0])//px1 = x*px0 + 6(a[1])//px2 = x*px1 + 2(a[2])//px3 = x*px2 + 5(a[3])//px4 = x*px3 + 6(a[4])int a[5] = {3,6,2,5,6};int x = 2;cout<<solve_px(a,x,5)<<endl;return 1;
}

这篇关于算法笔记02--归纳法之多项式求值（Horner规则）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---