多项式求的两种方法运行时间与理论值不符,为什么?
求多项式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次
{
/**方法2核心代码**/
Fx=a[0];
X=x;
for(int i=1;i <N;i++)
{
b=a[i]*X;
Fx=Fx+b;
X=X*x;
}
}
finish=clock();
cout < < "Dida= " < <finish-start < <endl;
time=(finish-start)/(CLK_TCK+0.0);
cout < < "Time used in method2= " < <time/N0 < <endl;
cout < < "Fx= " < <Fx < <endl;
}
/************************************************************/
运行结果:
/************************************/
The first:
Dida=11281
Time used in method2=1.1281e-006
Fx=1.25497e+032
Dida=13172
Time used in method1=1.3172e-006
Fx=1.25497e+032
The second:
Dida=13297
Time used in method1=1.3297e-006
Fx=1.25497e+032
Dida=11110
Time used in method2=1.111e-006
Fx=1.25497e+032
Press any key to continue
/***********************************/
(程序中两种方法各重复了N0=10000000)
方法1中两次用的滴答数分别为:13172,13297
方法2中两次用的滴答数分别为:11281,11110
可知方法1所用时间是多于方法2的.
[解决办法]
从算法角度说两种方法的复杂度是一样的，就差一个常数，很难说那种好。
从具体程序来说，涉及的内容就不同了。方法1的方法每次迭代有数据依赖性(Fx)。所以方法二更适合现在的CPU并行执行（现在的CPU可是超标量的，每个时钟周期可以执行多条指令）。而且这个结果也和编译器，编译参数以及执行的cpu有关。你测出的时间差也只有20％左右，差距也不大。
[解决办法]
支持楼上的！
大O表示法只能度量算法的阶，不可能精确度量运行时间。只能说大O表示法所表示的复杂度近似的表示了算法的性能，但是并不是说复杂度低的算法在实际中效率一定比复杂度高的算法好，因为有常数因子的作用以及编译有关。
[解决办法]
主要原因是这样，编译器会循环展开，减少数据冲突，近似并行。
[解决办法]
"Fx=Fx*x+a[i-1]; "的右端表达式复杂,编译器要化更多的时间进行分析,
先要确定计算步骤,才能进行计算,而且计算时也一定会利用堆栈来实现,
而不是直接地址,速度就会变慢,而第二种方案没有这种问题,你已经为它
确定了每一个步骤(加,乘),CPU立刻就可进行运算,用不着分析,所以就快.
[解决办法]
试试N=10000;
