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

方法1：

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：

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