Linux下算法效率的分析和测量

首先用两种方法计算1-1/x+1/x*x……然后比较其所用时间。本文涉及Linux下测量毫秒级时间精度的问题。

方法1：

[cpp]    

1. //Write in Ubuntu11.04


2. #include<stdio.h>   


3. #include<time.h>   


4. #include<sys/time.h>   


5. int main()  


6. {  


7.    struct timeval t_start,t_end;  


8.    double x,sum=1,sumx=1;  


9.    int  n,j,i;  


10.    printf(“Input x n\n”);  


11.    scanf(“%lf %d”,&x,&n);//lf 输入double 类型   


12.    gettimeofday(&t_start,NULL);//第一个参数存放当前时间，第二个存放时区信息   


13.    for(j=0;j<n;j++)  


14.    {  


15.       for(i=0;i<=j;i++)  


16.          sumx=sumx*(-1/x);  


17.       sum+=sumx;  


18.    }  


19.    gettimeofday(&t_end,NULL);  


20.    printf(“sum=%lf It takes %ldms.\n”,sum,(t_end.tv_sec-t_start.tv_sec)*1000+(t_end.tv_usec/1000-t_start.tv_usec/1000));//计算所用时间（毫秒）(ld输出long int)   


21.    return 0;  


22. }  

方法2：

[cpp]

1. #include<stdio.h>   


2. #include<time.h>   


3. #include<sys/time.h>   


4. int main()  


5. {  


6.    struct timeval t_start,t_end;  


7.    double x,sum=1,sumx=1;  


8.    int  n,j,i;  


9.    printf(“Input x n\n”);  


10.    scanf(“%lf %d”,&x,&n);//lf 输入double 类型   


11.    gettimeofday(&t_start,NULL);//第一个参数存放当前时间，第二个存放时区信息   


12.    for(j=0;j<n;j++)  


13.    {  


14.       sumx=sumx*(-1/x);  


15.       sum+=sumx;  


16.    }  


17.    gettimeofday(&t_end,NULL);  


18.    printf(“sum=%lf It takes %ldms.\n”,sum,(t_end.tv_sec-t_start.tv_sec)*1000+(t_end.tv_usec/1000-t_start.tv_usec/1000));//计算所用时间（毫秒）(ld输出long int)   


19.    return 0;  


20. }  

方法一时间复杂度为n^2,用时561ms，方法二时间复杂度为n,用时0ms。

在Linux 下用gettimeofday()可计算出精确到微妙级的时间，参考资料如下：

编译时遇到error: ‘for’ loop initial declarations are only allowed in C99 mode的问题，解决方法见下面的链接：http://www.linuxidc.com/Linux/2012-01/52153.htm