本文主要是介绍算法笔记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规则）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
