国内好的设计网站推荐,天气预报权威发布,陇南市网站建设,wordpress显示页面加载速度《数据结构与算法分析-C语言描述》#xff08;[urlhttp://users.cis.fiu.edu/~weiss/#dsaac2e]Data Structures and Algorithm Analysis in C[/url])习题2.6
该题要求计算几个循环的复杂度#xff0c;并用程序计算出程序的执行时间。我在linux下的c程序如下#xff1a;/* ex…《数据结构与算法分析-C语言描述》[urlhttp://users.cis.fiu.edu/~weiss/#dsaac2e]Data Structures and Algorithm Analysis in C[/url])习题2.6
该题要求计算几个循环的复杂度并用程序计算出程序的执行时间。我在linux下的c程序如下/* exercise 2.6 in data structures and algorithm in c*/#include stdio.h#include sys/time.h#include math.h#define MAXINPUT 260#define STEP (MAXINPUT/20)#define ZOOMIN 100000000int Fun1(int n){ int sum 0; int i; for(i 0; i n; i) sum; return sum;}int Fun2(int n){ int sum 0; int i,j; for(i 0; i n; i) for(j 0; j n; j) sum; return sum;}int Fun3(int n){ int sum 0; int i,j; for(i 0; i n; i) for(j 0; j n*n; j) sum; return sum;}int Fun4(int n){ int sum 0; int i,j; for(i 0; i n; i) for(j 0; j i; j) sum; return sum;}int Fun5(int n){ int sum 0; int i,j,k; for(i 0; i n; i) for(j 0; j i*i; j) for(k 0; k j; k) sum; return sum;}int Fun6(int n){ int sum 0; int i,j,k; for(i 0; i n; i) for(j 0; j i*i; j) if(j%i 0) for(k 0; k j; k) sum; return sum;}int GetSpendTime(int (* f)(int ), int n){ struct timeval StartTimer,EndTimer; double SpendTime; double NPow3,NPow4,NPow5,NPow4LogN; NPow3 pow(n,3); NPow4 pow(n,4); NPow5 pow(n,5); NPow4LogN pow(n,4)*log(n); gettimeofday(StartTimer,NULL); (*f)(n); gettimeofday(EndTimer,NULL); SpendTime EndTimer.tv_sec - StartTimer.tv_sec (EndTimer.tv_usec - StartTimer.tv_usec)/1000000.0; printf(N%d,SpendTime%.6f,T/N3%.6f,T/N4%.6f,T/N5%.6f,T/N4logN%.6f\n, n,SpendTime,SpendTime*(ZOOMIN/NPow3),SpendTime*(ZOOMIN/NPow4), SpendTime*(ZOOMIN/NPow5),SpendTime*(ZOOMIN/NPow4LogN)); return 0;}int main(void){ int i; for(i MAXINPUT/4; i MAXINPUT; iSTEP) GetSpendTime(Fun5,i); /* GetSpendTime(Fun5,20);*/ return 0;}
输出结果为
N65,SpendTime0.497344,T/N3181.099317,T/N42.786143,T/N50.042864,T/N4logN0.667438
N78,SpendTime1.194641,T/N3251.740800,T/N43.227446,T/N50.041378,T/N4logN0.740799
N91,SpendTime2.600523,T/N3345.093296,T/N43.792234,T/N50.041673,T/N4logN0.840690
N104,SpendTime5.029540,T/N3447.124275,T/N44.299272,T/N50.041339,T/N4logN0.925691
N117,SpendTime9.153871,T/N3571.540753,T/N44.884964,T/N50.041752,T/N4logN1.025784
N130,SpendTime15.069480,T/N3685.911698,T/N45.276244,T/N50.040586,T/N4logN1.083966
N143,SpendTime24.084789,T/N3823.634886,T/N45.759685,T/N50.040278,T/N4logN1.160561
N156,SpendTime37.684631,T/N3992.637029,T/N46.363058,T/N50.040789,T/N4logN1.260047
N169,SpendTime55.917730,T/N31158.482343,T/N46.854925,T/N50.040562,T/N4logN1.336269
N182,SpendTime82.133201,T/N31362.399844,T/N47.485713,T/N50.041130,T/N4logN1.438452
N195,SpendTime115.332322,T/N31555.418291,T/N47.976504,T/N50.040905,T/N4logN1.512707
N208,SpendTime159.712267,T/N31774.795297,T/N48.532670,T/N50.041022,T/N4logN1.598615
N221,SpendTime217.001617,T/N32010.417005,T/N49.096910,T/N50.041162,T/N4logN1.685186
N234,SpendTime337.556033,T/N32634.500602,T/N411.258550,T/N50.048113,T/N4logN2.063774
N247,SpendTime408.777333,T/N32712.663639,T/N410.982444,T/N50.044463,T/N4logN1.993405此程序中计算第五个函数func5的运行时间并将此时间分别除以N^3),(N^4),(N^5)和(N^4*long(N))。因为N^5的值很大而执行时间通常比较小我又使用了一个放大系数ZOOMIN使得除法运算的结果不至于误差太大。还需要注意的是如果换成其他的函数可以根据需要调节ZOOMIN和MAXINPUT的值使得程序运行结果能更准确的反映该函数的算法执行复杂度。从输出结果来看T/N5的值趋向于一个比较固定的数所以func5应该是ON^5)左右这个算法可以用来验证自己计算的算法复杂度是否正确。可惜的是上面的算法只能用于unix/linux下windows下测量函数段的执行时间可以使用其他的方法例如[url]http://stackoverflow.com/questions/2215744/c-programming-how-can-i-get-execution-time-of-a-program-in-milliseconds[/url]
