《数据结构与算法分析-C语言描述》（[url=http://users.cis.fiu.edu/~weiss/#dsaac2e]Data Structures and Algorithm Analysis in C[/url])习题2.6
该题要求计算几个循环的复杂度，并用程序计算出程序的执行时间。我在linux下的c程序如下：
#include <stdio.h> #include <sys/time.h> #include <math.h> #define MAXINPUT 260 #define STEP (MAXINPUT/20) #define ZOOMIN 100000000 int 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; i+=STEP) GetSpendTime(Fun5,i); /* GetSpendTime(Fun5,20);*/ return 0; }/* exercise 2.6 in <data structures and algorithm in c>*/
输出结果为：
N=65,SpendTime=0.497344,T/N3=181.099317,T/N4=2.786143,T/N5=0.042864,T/N4logN=0.667438
N=78,SpendTime=1.194641,T/N3=251.740800,T/N4=3.227446,T/N5=0.041378,T/N4logN=0.740799
N=91,SpendTime=2.600523,T/N3=345.093296,T/N4=3.792234,T/N5=0.041673,T/N4logN=0.840690
N=104,SpendTime=5.029540,T/N3=447.124275,T/N4=4.299272,T/N5=0.041339,T/N4logN=0.925691
N=117,SpendTime=9.153871,T/N3=571.540753,T/N4=4.884964,T/N5=0.041752,T/N4logN=1.025784
N=130,SpendTime=15.069480,T/N3=685.911698,T/N4=5.276244,T/N5=0.040586,T/N4logN=1.083966
N=143,SpendTime=24.084789,T/N3=823.634886,T/N4=5.759685,T/N5=0.040278,T/N4logN=1.160561
N=156,SpendTime=37.684631,T/N3=992.637029,T/N4=6.363058,T/N5=0.040789,T/N4logN=1.260047
N=169,SpendTime=55.917730,T/N3=1158.482343,T/N4=6.854925,T/N5=0.040562,T/N4logN=1.336269
N=182,SpendTime=82.133201,T/N3=1362.399844,T/N4=7.485713,T/N5=0.041130,T/N4logN=1.438452
N=195,SpendTime=115.332322,T/N3=1555.418291,T/N4=7.976504,T/N5=0.040905,T/N4logN=1.512707
N=208,SpendTime=159.712267,T/N3=1774.795297,T/N4=8.532670,T/N5=0.041022,T/N4logN=1.598615
N=221,SpendTime=217.001617,T/N3=.417005,T/N4=9.096910,T/N5=0.041162,T/N4logN=1.685186
N=234,SpendTime=337.556033,T/N3=2634.500602,T/N4=11.258550,T/N5=0.048113,T/N4logN=2.063774
N=247,SpendTime=408.777333,T/N3=2712.663639,T/N4=10.982444,T/N5=0.044463,T/N4logN=1.993405
此程序中计算第五个函数func5的运行时间，并将此时间分别除以（N^3),(N^4),(N^5)和(N^4*long(N))。因为N^5的值很大，而执行时间通常比较小，我又使用了一个放大系数ZOOMIN使得除法运算的结果不至于误差太大。还需要注意的是，如果换成其他的函数，可以根据需要调节ZOOMIN和MAXINPUT的值，使得程序运行结果能更准确的反映该函数的算法执行复杂度。
从输出结果来看，T/N5的值趋向于一个比较固定的数，所以func5应该是O（N^5)左右，这个算法可以用来验证自己计算的算法复杂度是否正确。
可惜的是，上面的算法只能用于unix/linux下，windows下测量函数段的执行时间可以使用其他的方法，例如：[url]/questions/2215744/c-programming-how-can-i-get-execution-time-of-a-program-in-milliseconds[/url]
