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

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

方法1：

//Write in Ubuntu11.04
#include<stdio.h>
#include<time.h>
#include<sys/time.h>
int main()
{
   struct timeval t_start,t_end;
   double x,sum=1,sumx=1;
   int  n,j,i;
   printf("Input x n\n");
   scanf("%lf %d",&x,&n);//lf 输入double 类型
   gettimeofday(&t_start,NULL);//第一个参数存放当前时间，第二个存放时区信息
   for(j=0;j<n;j++)
   {
      for(i=0;i<=j;i++)
         sumx=sumx*(-1/x);
      sum+=sumx;
   }
   gettimeofday(&t_end,NULL);
   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)
   return 0;
}

结果：

方法2：

#include<stdio.h>
#include<time.h>
#include<sys/time.h>
int main()
{
   struct timeval t_start,t_end;
   double x,sum=1,sumx=1;
   int  n,j,i;
   printf("Input x n\n");
   scanf("%lf %d",&x,&n);//lf 输入double 类型
   gettimeofday(&t_start,NULL);//第一个参数存放当前时间，第二个存放时区信息
   for(j=0;j<n;j++)
   {
      sumx=sumx*(-1/x);
      sum+=sumx;
   }
   gettimeofday(&t_end,NULL);
   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)
   return 0;
}

结果如下：

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

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

编译时遇到error: ‘for’ loop initial declarations are only allowed in C99 mode的问题，解决方法如下：