数据结构概念.ppt

执行时间与问题规模有关；表达式：赋值语句：循环语句：switch语句：if_then语句：函数执行/函数调用语句：动态存储管理语句：转移语句：第69页,共97页，星期六，2024年，5月程序步确定方法插入计数全局变量count建表，列出各语句的程序步数例以迭代方式求累加和的函数floatsum(floata[],intn){floats=0.0;for(inti=0;in;i++)s=s+a[i]; returns;}第70页,共97页，星期六，2024年，5月在求累加和程序中加入count语句floatsum(floata[],intn){floats=0.0;count++;//针对赋值语句for(inti=0;in;i++){count+=2;//针对for语句 s+=a[i]; count++;//针对赋值语句} count+=2;//针对for的最后一次returns;count++;//针对return语句}执行结束得程序步数count=3*n+4第71页,共97页，星期六，2024年，5月程序的简化形式voidsum(floata[],intn){for(inti=0;in;i++)count+=3;count+=4;}第72页,共97页，星期六，2024年，5月注意：一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。如下分析：例如：赋值语句x=sum(R,n)本身程序步数为1；一次执行对函数sum(R,n)的调用需要的程序步数为3*n+4；一次执行x=sum(R,n)的程序总步数为 1+3*n+4=3*n+5第73页,共97页，星期六，2024年，5月计算累加和程序

程序步数计算工作表格第74页,共97页，星期六，2024年，5月时间复杂度的渐进表示法例求两个n阶方阵的乘积C=A?BvoidMatrixMultiply(intA[n][n],intB[n][n],intC[n][n]){for(inti=0;in;i++)…2n+2for(intj=0;jn;j++){…n(2n+2)C[i][j]=0;…n2for(intk=0;kn;k++)…n2(2n+2)C[i][j]=C[i][j]+A[i][k]*B[k][j];…n3}}3n3+5n2+4n+2第75页,共97页，星期六，2024年，5月时间复杂度的渐进表示法算法中所有语句的频度之和是矩阵阶数n的函数T(n)=3n3+5n2+4n+2一般地，称n是问题的规模。则时间复杂度T(n)是问题规模n的函数。当n趋于无穷大时，把时间复杂度的数量级（阶）称为算法的渐进时间复杂度T(n)=O(n3)─大O表示法第76页,共97页，星期六，2024年，5月各种函数的增长趋势clog2nnnlog2nn2n32n3nn!加法规则针对并列程序段T(n,m)=T1(n)+T2(m) =O(max(f(n),g(m)))

第77页,共97页，星期六，2024年，5月T(n)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2))=