第四课算法效率的度量和存储空间需求.doc

数据结构教程第四课算法效率的度量和存储空间需求
作者：未知阅读人次：21638文章来源：HYPERLINK"http://www.bccn.net/ShowCopyFrom.asp?ChannelID=1&SourceName=未知"未知发布时间：2004-11-12HYPERLINK"http://www.bccn.net/article/comment/?/=232.html"\t"_blank"网友评论(11)条
本课主题：算法效率的度量和存储空间需求
教学目的：掌握算法的渐近时间复杂度和空间复杂度的意义与作用
教学重点：渐近时间复杂度的意义与作用及计算方法
教学难点：渐近时间复杂度的意义
授课内容：
一、算法效率的度量
算法执行的时间是算法优劣和问题规模的函数。评价一个算法的优劣，可以在相同的规模下，考察算法执行时间的长短来进行判断。而一个程序的执行时间通常有两种方法：
1、事后统计的方法。
缺点：不利于较大范围内的算法比较。（异地，异时，异境）
2、事前分析估算的方法。
程序在计算机上运行所需时间的影响因素算法本身选用的策略问题的规模规模越大，消耗时间越多书写程序的语言语言越高级，消耗时间越多编译产生的机器代码质量机器执行指令的速度综上所述，为便于比较算法本身的优劣，应排除其它影响算法效率的因素。
从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。（原操作在所有该问题的算法中都相同）
T(n)=O(f(n))
上示表示HYPERLINK"http://219.219.90.4:8080/datastru/class03/class03.htm"\l"0401"随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。
求4*4矩阵元素和，T(4)=O(f(4))
f=n*n;sum(intnum[4][4])
{inti,j,r=0;for(i=0;i<4;i++)
for(j=0;j<4;j++)
r+=num[i][j];/*原操作*/
returnr;}最好情况：T（4）=O（0）
最坏情况：T（4）=O（n*n）ispass(intnum[4][4])
{inti,j;for(i=0;i<4;i++)
for(j=0;j<4;j++)
if(num[i][j]!=i*4+j+1)
return0;
return1;}原操作执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次数。
语句频度时间复杂度{++x;s=0;}1O(1)for(i=1;i<=n;++i)
{++x;s+=x;}nO(n)for(j=1;j<=n;++j)
for(k=1;k<=n;++k)
{++x;s+=x;}n*nO(n*n)O(logn)
基本操作的执行次数不确定时的时间复杂度平均时间复杂度依基本操作执行次数概率计算平均最坏情况下时间复杂度在最坏情况下基本操作执行次数二、算法的存储空间需求
类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间的量度。
记作：
S(n)=O(f(n))
若额外空间相HYPERLINK"http://219.219.90.4:8080/datastru/class03/class03.htm"\l"0401"对于输入数据量来说是常数，则称此算法为原地工作。
如果所占空间量依赖于特定的输入，则除特别指明外，均按最坏情况来分析。
三、总结
渐近时间复杂度
空间复杂度