首页 > 代码库 > 算法笔记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规则)