Teenits 2008-5-14 19:59
数据结构教程 第四课 算法效率的度量和存储空间需求
[size=5]
本课主题： 算法效率的度量和存储空间需求
教学目的： 掌握算法的渐近时间复杂度和空间复杂度的意义与作用
教学重点： 渐近时间复杂度的意义与作用及计算方法
教学难点： 渐近时间复杂度的意义
授课内容：
一、算法效率的度量
算法执行的时间是算法优劣和问题规模的函数。评价一个算法的优劣，可以在相同的规模下，考察算法执行时间的长短来进行判断。而一个程序的执行时间通常有两种方法：
1、事后统计的方法。
缺点：不利于较大范围内的算法比较。（异地，异时，异境）
[/size][size=5]2、事前分析估算的方法。[/size]
[indent][table=500] [tr] [td=2,1][size=5]程序在计算机上运行所需时间的影响因素[/size][/td] [/tr] [tr] [td=1,1,215][size=5]算法本身选用的策略[/size][/td] [td][size=5] [/size][/td] [/tr] [tr] [td=1,1,215][size=5]问题的规模[/size][/td] [td][size=5]规模越大，消耗时间越多[/size][/td] [/tr] [tr] [td=1,1,215][size=5]书写程序的语言[/size][/td] [td][size=5]语言越高级，消耗时间越多[/size][/td] [/tr] [tr] [td=1,1,215][size=5]编译产生的机器代码质量[/size][/td] [td][size=5] [/size][/td] [/tr] [tr] [td=1,1,215][size=5]机器执行指令的速度[/size][/td] [td][size=5] [/size][/td] [/tr] [/table][size=5]综上所述，为便于比较算法本身的优劣，应排除其它影响算法效率的因素。[/size]
[size=5]从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。 （原操作在所有该问题的算法中都相同）[/size]
[align=center][size=5][i]T[/i](n)=[i]O[/i](f(n))[/size][/align][size=5]上示表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。[/size]
[/indent][indent][table=481] [tr] [td=1,1,131] [size=5]求4*4矩阵元素和，T(4)=O(f(4))[/size]
[size=5]f=n*n;[/size]
[/td] [td] [size=5]sum(int num[4][4]) [/size]
[size=5]{ int i,j,r=0;
for(i=0;i<4;i++)[/size]
[indent] [size=5]for(j=0;j<4;j++) [/size]
[indent] [size=5]r+=num[i][j]; /*原操作*/[/size]
[/indent][/indent] [size=5]return r;
}[/size]
[/td] [/tr] [tr] [td=1,1,131] [size=5]最好情况：
T（4）=O（0）[/size]
[size=5]最坏情况：
T（4）=O（n*n）[/size]
[/td] [td] [size=5]ispass(int num[4][4]) [/size]
[size=5]{ int i,j;
for(i=0;i<4;i++)[/size]
[indent] [size=5]for(j=0;j<4;j++) [/size]
[indent] [size=5]if(num[i][j]!=i*4+j+1)[/size]
[indent] [size=5]return 0; [/size]
[/indent][/indent][/indent] [size=5]return 1;
}[/size]
[/td] [/tr] [/table][size=5]原操作执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次数。[/size]
[table=478] [tr] [td=1,1,252][size=5]语句[/size][/td] [td][size=5]频度[/size][/td] [td=1,1,152][size=5]时间复杂度[/size][/td] [/tr] [tr] [td][size=5]{++x;s=0;}[/size][/td] [td=1,1,60][size=5]1[/size][/td] [td][size=5]O(1)[/size][/td] [/tr] [tr] [td=1,1,252] [size=5]for(i=1;i<=n;++i)[/size]
[indent] [size=5]{++x;s+=x;}[/size]
[/indent][/td] [td][size=5]n[/size][/td] [td=1,1,152][size=5]O(n)[/size][/td] [/tr] [tr] [td=1,1,252] [size=5]for(j=1;j<=n;++j)[/size]
[indent] [size=5]for(k=1;k<=n;++k)[/size]
[indent] [size=5]{++x;s+=x;}[/size]
[/indent][/indent][/td] [td][size=5]n*n[/size][/td] [td=1,1,152][size=5]O(n*n)[/size][/td] [/tr] [tr] [td][size=5] [/size][/td] [td=1,1,60][size=5] [/size][/td] [td][size=5]O(log n)[/size][/td] [/tr] [tr] [td=1,1,252][size=5] [/size][/td] [td][size=5] [/size][/td] [td=1,1,152][size=5]
[img]http://www.bianceng.cn/upimg/allimg/070510/231.gif[/img][/size][/td] [/tr] [/table][table=481] [tr] [td=2,1][size=5]基本操作的执行次数不确定时的时间复杂度[/size][/td] [/tr] [tr] [td=1,1,211][size=5]平均时间复杂度[/size][/td] [td][size=5]依基本操作执行次数概率计算平均[/size][/td] [/tr] [tr] [td=1,1,211][size=5]最坏情况下时间复杂度[/size][/td] [td][size=5]在最坏情况下基本操作执行次数[/size][/td] [/tr] [/table][/indent][size=5]二、算法的存储空间需求[/size]
[indent][size=5]类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间的量度。[/size]
[size=5]记作：[/size]
[align=center][size=5][i]S[/i](n)=[i]O[/i]([i]f[/i](n))[/size][/align][size=5]若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。[/size]
[size=5]如果所占空间量依赖于特定的输入，则除特别指明外，均按最坏情况来分析。[/size]
[/indent][size=5]三、总结[/size]
[indent][size=5]渐近时间复杂度[/size]
[size=5]空间复杂度[/size]
[/indent][size=5]
[/size]