两种多项式算法和运行时间比较

数据结构学习笔记

题目如上图所示。
第一种算法：按照多项式定义，计算一项加上一项

int f1(int n,double a[],double x)
{
	int i;
	double p=a[0];
	for(i=1;i<=n;i++){
		p+=a[i]*pow(x,i);
	}
	return p;
}

第二种算法：运用结合律，将多项式形式改变一下

代码如下：

int f2(int n,double a[],double x)
{
	int i;
	double p=a[n];
	for(i=n;i>0;i--){
		p=a[i-1]+x*p;
	}
	return p;
}

下面来比较一下两种算法的运行时间，因为运行一次的话，两种方法的运行时间太短，所以重复运行MAXK次再求平均。

clock_t start,stop;
//clock_t是clock()函数返回的变量类型
double duration;
//记录被测函数运行时间，以秒为单位

int main(){
	//举例，n=9,a[i]=i,x=1.2
	for(int i=0;i<MAXN;i++)
	a[i]=double(i);
	
	start=clock();
	for(int i=1;i<=MAXK;i++)
	f1(MAXN-1,a,1.1);
	stop=clock();
	duration=((double)(stop-start))/CLK_TCK/MAXK;
	cout<<duration<<endl;
	
	start=clock();
	for(int i=1;i<=MAXK;i++)
	f2(MAXN-1,a,1.1);
	stop=clock();
	duration=((double)(stop-start))/CLK_TCK/MAXK;
	cout<<duration<<endl;
} 

运行结果如下：

可以看到第二种方法比第一种方法快了一个数量级，效率提高。