数据结构教学课件.ppt

算法定义算法举例“百钱买百鸡”问题：公鸡每只5钱，母鸡每只3钱，小鸡3只1钱，100钱买100只鸡，问各种鸡可买多少只?令公鸡母鸡小鸡分别为x,y,z只*例：for(x=0;x=100;x++){ for(y=0;y=100;y++){ for(z=0;z=100;z++){if(x+y+z==1005*x+3*y+z/3==100z%3==0){printf(“%d,%d,%d”,x,y,z);}}}算法定义算法举例欧几里德算法——辗转相除法求两个自然数m和n的最大公约数*输入:m,n输出:m和n的最大公约数r=m%n;循环直到r等于0{m=n;n=r;r=m%n;}输出n算法性能分析与度量算法效率的评价方法：事后统计将算法实现，统计其时间和空间开销事前分析对算法所消耗时间和空间资源的一种估算方法算法效率的分析时间复杂度空间复杂度*time(start); algorithm();time(stop); runTime=stop-start;算法性能分析与度量算法的时间复杂度*算法的运行时间=每条语句执行时间之和执行次数×执行一次的时间例：for(i=0;in;i++){ for(j=0;jn;j++){ c[i][j]=0;for(k=0;kn;k++){c[i][j]=c[i][j]+a[i][k]*b[k][j];}}}指令系统、代码质量有关每条语句执行次数之和基本语句执行次数算法性能分析与度量算法的时间复杂度算法的运行时间可表示为基本语句执行次数，它是问题规模的一个函数称这个函数的渐进阶为算法的时间复杂度*问题规模：n基本语句：c[i][j]=0c[i][j]=c[i][j]+a[i][k]*b[k][j]时间复杂度:O(n3)例：for(i=0;in;i++){ for(j=0;jn;j++){ c[i][j]=0;for(k=0;kn;k++){c[i][j]=c[i][j]+a[i][k]*b[k][j];}}}算法性能分析与度量算法的时间复杂度大O表示法：若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))*n0问题规模n执行次数n0之前的情况无关紧要T(n)c×f(n)表示当问题规模充分大时在渐进意义下的阶算法性能分析与度量算法的时间复杂度大O表示法：若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))例1：T(n)=3n+2当n≥2时，3n+2≤3n+n=4n因此T(n)=O(n)*算法性能分析与度量算法的时间复杂度大O表示法：若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))例2：T(n)=10n2+4n+2当n≥2时，10n2+4n+2≤10n2+5n又有当n≥5时，10n2+5n≤10n2+n2=11n2因此T(n)=O(n2)*算法性能分析与度量算法的时间复杂度大O表示法：若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))作业：求解T(n)=amnm+am-1nm-1+???a2n2+a1n+a0，并给出证明过程*算法性能分析与度量算法的时间复杂度T(n)=O(f(n))若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))给出算法复杂度的上界，不可能比c*f(n)更大例：T(n)=