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。