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