chap1数据结构.ppt

例4：求和程序 float sum(float a[ ], const int n) { float s = 0.0; /* 1 */ for(int i= 0; i n; i++) { /* 2(n+1) */ s += a[i]; /* n */ } return s; /* 1 */ } 数字媒体技术教研室 乐小燕 * T(n)=3n+4 当n充分大时， T(n)与n是同阶的。 该算法时间复杂度为：T(n)=O(n) 例4：求和程序（递归） float rsum (float a[ ], const int n) { if (n = 0) { /* 1 */ return 0; /* 1 */ } else { return rsum (a,n-1)+a[n-1]; /* 1+ Trsum(n-1) */ } 数字媒体技术教研室 乐小燕 * s=0; /* 1 */ for (i=0; in; i ++) /* 2(n+1) */ for (j=0; jn; j ++) /* 2(n+1)*2n */ s+=B [i][j]; /* n2 */ sum=s; /* 1 */ 时间复杂度: ？？？ 思考练习 T(n)=O(5n2+6n+3)=O(n2) 如何估算 算法的时间复杂度？ 方法1：计算所有语句执行次数； 方法2：计算原操作语句执行次数； 方法3：计算算法在最坏情况下的执行次数； 方法4：分别计算算法在最好、最坏情况下的执行 次数，再取平均。 最后用时间复杂度表示。 例4：两个NxN矩阵相乘 两个NxN矩阵相乘的算法中乘法运算是基本操作，其重复执行的次数为n3。 该算法的时间复杂度为:　T(n) = O(n3)。for (i=1; i=n;++i) for(j=1;j=n;++j){ c[i,j]=0; for(k=1;k=n;++k) c[i,j] += a[i,k]*b[k,j]; }注意：由于算法的时间复杂度只是对于问题规模n的增长率，在难以精确计算语句频度的情况下，只需求出它关于n的增长率或阶即可。 考 平均时间复杂度 ---时间复杂度与输入数据有关时采用 采用平均时间复杂度或最坏时间复杂度（默认） 例如: 冒泡排序算法. Void bubble_sort(int a[], int n){ for (i=n-1,change = TRUE; i1change; --i) { change = false; for (j= 0; ji; ++j)  if(a[j] a[j+1]){ a[j] ←→a[j+1]; change=TURE;} } }//bubble_sort 时间复杂度: O(n2) 考 通常涉及的增长率(阶)(从大到小) nn n!（阶乘阶） cn(c1), 2n , 3n（指数阶） nc(c1), n2, n3（方阶） nlog(n), nlog2(n)（对数阶） nr(0r1.0) log(n), log2(n) n(线性阶) 1（常量阶） O(1)O(log2n)O(n) nlog2(n)O(nc)nn 例：百钱买百鸡问题 100元钱买100只鸡，母鸡每只5元，公鸡每只3元，小鸡3只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？ 解：设母鸡、公鸡、小鸡各为x, y, z只。则有： x + y + z = 100 5x + 3y + z/3 = 100 方法1： for(i=0;i=100;i++) 　for(j=0; j=100; j++) 　　for(k=0; k=100;k++) { 　　　　if(k%3 ==0i+j+k==100 5*I+3*j+k/3==100) 　　　printf(“%d,%d,%d\n”,