1、利用clock（）函数计算程序运行时间
clock():捕捉从程序开始运行到clock() 被调用时所消耗的时间。这个时间单位是clock tick，即“时钟打点”。 常数CLK_TCK:机器时钟每秒所走的时钟打点数
#include <stdio.h> #include <time.h> #define MAXK 1e7 /*被测函数最大重复调用次数*/ clock_t start, stop; /*clock_t 是clock()函数返回的变量类型*/ double duration; /*记录被测函数运行时间，以秒为单位*/ int main() { /*不在测试范围内的准备工作写在clock()调用之前*/ start =clock(); /*开始计时 */ for(i=0;i<MAXK;i++) /*被测函数循环n次*/ MyFunction(); /*把被测函数加这里 */ stop =clock(); /*停止计时*/ duration = ((double)(stop - start))/CLK_TCK/MAXK; /*计算运行时间*/ /*其他不在测试范围的处理写在后面，例如输出duration的值*/ return 0; }
2、应用实例---多项式求解
//多项式求解--试用程序时间函数 #include <stdio.h> #include <math.h> #include <time.h> #define MAXN 10 /*多项式最大项数，即多项式阶乘数+1*/ #define MAXK 1e7 clock_t start,stop; double duration; double f1(int n,double a[],double x); double f2(int n,double a[],double x); int main() { int i; double a[MAXN]; /*储存多项式的系数*/ for(i=0;i<MAXN;i++) a[i]=double(i); /*测试f1*/ start = clock(); for(i=0;i<MAXK;i++) f1(MAXN-1,a,1.1); stop =clock(); duration =((double)(stop-start))/CLK_TCK/MAXK; printf("ticks1= %f ",(double)(stop-start)); printf("duration1=%6.2e ",duration); /*测试f2*/ start = clock(); for(i=0;i<MAXK;i++) f2(MAXN-1,a,1.1); stop =clock(); duration =((double)(stop-start))/CLK_TCK/MAXK; printf("ticks2= %f ",(double)(stop-start)); printf("duration2=%6.2e ",duration); return 0; } double f1(int n,double a[],double x) { int i; double p=a[0]; for(i=1;i<=n;i++)//(n*n+n)/2次乘法 { p+=a[i]*pow(n,i); } return p; } double f2(int n,double a[],double x) { int i; double p=a[n]; for(i=n;i>0;i--)//计算加减法的效率比乘除法快很多---n次乘法 { p=a[i-1]+x*p; } return p; }
3、应用实例---最大子列
四种算法对比理解时间复杂度
/*算法1------O(N^3)*/ int MaxSubseqSum1(int A[] ,int N) { int ThisSum,MaxSum = 0; int i,j,k; for(i=0;i<N;i++) //i是子列左端位置 { for(j=i;j<N;j++) //j是子列右端位置 { ThisSum=0; //ThisSum是A[i]-A[j]的子列和 for(k=i;k<=j;k++) { ThisSum +=A[k]; if(ThisSum > MaxSum)//如果刚得到的子列和更大，则更新结果 MaxSum = ThisSum; } }//j循环结束 }//i循环结束 return MaxSum; } /*算法2------O(N^2)*/ int MaxSubseqSum1(int A[] ,int N) { int ThisSum,MaxSum = 0; int i,j,k; for(i=0;i<N;i++) //i是子列左端位置 { ThisSum=0; //ThisSum是A[i]-A[j]的子列和 for(j=i;j<N;j++) //j是子列右端位置 { ThisSum +=A[j];//对于相同的i，不同的j，只要在j-1循环的基础上累加即可。 if(ThisSum > MaxSum)//如果刚得到的子列和更大，则更新结果 MaxSum = ThisSum; } }//j循环结束 }//i循环结束 return MaxSum; } /*算法3------O(nlogn)分而治之*/ /*算法4------O(N)*/ int MaxSubseqSum1(int A[] ,int N) { int ThisSum,MaxSum = 0; int i,j,k; ThisSum=0; //ThisSum是A[i]-A[j]的子列和 for(i=0;i<N;i++) //i是子列左端位置 { ThisSum+=A[i]; //向右累加 if(ThisSum > MaxSum) //如果刚得到的子列和更大，则更新结果 MaxSum=ThisSum; else if(ThisSum<0) //如果不能使后面部分和增大则舍去 ThisSum = 0; }//i循环结束 return MaxSum; }
结：算法+数据结构=程序。对算法有了初步的认识和了解后，将学习数据的逻辑结构（表，树，图，集合）和他们在机内的存储表示即存储结构。
看看我什么时候能将这个课程学完啊 = = 2017-12-09