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

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的问题，解决方法见下面的链接：