多项式求的两种方法运行时间与理论值不符,为什么?该如何处理
多项式求的两种方法运行时间与理论值不符,为什么?
求多项式Fx=A(n)*X(n)+A(n-1)*X(n-1)+....+A(0) //A(i)为系数,X(i)为X的i次幂
方法1:
Fx=( (A(n)*X+A(n-1))*X+A(n-2) )*X+...A(0)
C++的代码为:
Fx=a[N-1];//Fx初始值,a[0--n-1]为系数
for(int i=N-1;i> =1;i--)
{
Fx=Fx*x+a[i-1];
}
方法2:
Fx=a[0];//Fx初始值
X=x;
for(int i=1;i <N;i++)
{
b=a[i]*X;
Fx=Fx+b;
X=X*x;
}
/************************/
理伦分析,
方法1中操作步数为:
'* '操作n-1次
'+ '操作n-1次
方法2中操作步数为:
'* '操作2*(n-1)次
'+ '操作n-1次
可知方法1比方法2少n-1次 '* '操作,其优于方法2.
然而,如果运行两种方法的话(VC6.0),发现方法2用的时间少于方法1.
以下是本人写的代码,求CSDN中的高手们帮帮小弟,说一下为什么.
/**************************************************************/
#include <iostream.h>
#include <ctime>
void method1( double x, double* a, double Fx);
void method2( double x, double* a, double Fx);
const long N0=10000000;//两种方法各重复做的次数
const long N=100;
const long NUM=10;
void main(void)
{
double x=2; //给x赋值
double a[N];
double Fx;
for(int i=0;i <N;i++)//initialize the array,其为多项式的系数
{
a[i]=i+1;
}
cout < < "The first: " < <endl; //第一次测试两种方法
Fx=0;
method2(x,a,Fx);
Fx=0;
method1(x,a,Fx);
cout < < "The second: " < <endl;//第二次测试两种方法,
//但调用两种方法次顺相反
Fx=0;
method1(x,a,Fx);
Fx=0;
method2(x,a,Fx);
}
void method1(double x, double* a, double Fx)
{
clock_t start,finish;
double time;
Fx=a[N-1]; //initialize the Fx
start=clock();
for(int j=1;j <=N0;j++)//repeat N0次
{
/**方法1核心代码**/
Fx=a[N-1];
for(int i=N-1;i> =1;i--)
{
Fx=Fx*x+a[i-1];
}
}
finish=clock();
cout < < "Dida= " < <finish-start < <endl;
time=(finish-start)/(CLK_TCK+0.0);
cout < < "Time used in method1= " < <time/N0 < <endl;
cout < < "Fx= " < <Fx < <endl;
}
void method2(double x, double* a, double Fx)
{
double b=0;
double X;
clock_t start,finish;
double time;
Fx=a[0]; //initialize the Fx
start=clock();
for(int j=1;j <=N0;j++)//repeat N0次
求多项式Fx=A(n)*X(n)+A(n-1)*X(n-1)+....+A(0) //A(i)为系数,X(i)为X的i次幂
方法1:
Fx=( (A(n)*X+A(n-1))*X+A(n-2) )*X+...A(0)
C++的代码为:
Fx=a[N-1];//Fx初始值,a[0--n-1]为系数
for(int i=N-1;i> =1;i--)
{
Fx=Fx*x+a[i-1];
}
方法2:
Fx=a[0];//Fx初始值
X=x;
for(int i=1;i <N;i++)
{
b=a[i]*X;
Fx=Fx+b;
X=X*x;
}
/************************/
理伦分析,
方法1中操作步数为:
'* '操作n-1次
'+ '操作n-1次
方法2中操作步数为:
'* '操作2*(n-1)次
'+ '操作n-1次
可知方法1比方法2少n-1次 '* '操作,其优于方法2.
然而,如果运行两种方法的话(VC6.0),发现方法2用的时间少于方法1.
以下是本人写的代码,求CSDN中的高手们帮帮小弟,说一下为什么.
/**************************************************************/
#include <iostream.h>
#include <ctime>
void method1( double x, double* a, double Fx);
void method2( double x, double* a, double Fx);
const long N0=10000000;//两种方法各重复做的次数
const long N=100;
const long NUM=10;
void main(void)
{
double x=2; //给x赋值
double a[N];
double Fx;
for(int i=0;i <N;i++)//initialize the array,其为多项式的系数
{
a[i]=i+1;
}
cout < < "The first: " < <endl; //第一次测试两种方法
Fx=0;
method2(x,a,Fx);
Fx=0;
method1(x,a,Fx);
cout < < "The second: " < <endl;//第二次测试两种方法,
//但调用两种方法次顺相反
Fx=0;
method1(x,a,Fx);
Fx=0;
method2(x,a,Fx);
}
void method1(double x, double* a, double Fx)
{
clock_t start,finish;
double time;
Fx=a[N-1]; //initialize the Fx
start=clock();
for(int j=1;j <=N0;j++)//repeat N0次
{
/**方法1核心代码**/
Fx=a[N-1];
for(int i=N-1;i> =1;i--)
{
Fx=Fx*x+a[i-1];
}
}
finish=clock();
cout < < "Dida= " < <finish-start < <endl;
time=(finish-start)/(CLK_TCK+0.0);
cout < < "Time used in method1= " < <time/N0 < <endl;
cout < < "Fx= " < <Fx < <endl;
}
void method2(double x, double* a, double Fx)
{
double b=0;
double X;
clock_t start,finish;
double time;
Fx=a[0]; //initialize the Fx
start=clock();
for(int j=1;j <=N0;j++)//repeat N0次