度量空间:法效率的度量和存储空间需求

课主题: 算法效率度量和存储空间需求
教学目: 掌握算法渐近时间复杂度和空间复杂度意义和作用
教学重点: 渐近时间复杂度意义和作用及计算思路方法
教学难点: 渐近时间复杂度意义
授课内容:
、算法效率度量
算法执行时间是算法优劣和问题规模评价个算法优劣可以在相同规模下考察算法执行时间长短来进行判断而个执行时间通常有两种思路方法:
1、事后统计思路方法
缺点:不利于较大范围内算法比较(异地异时异境) 
2、事前分析估算思路方法
在计算机上运行所需时间影响原因 
算法本身选用策略

问题规模
规模越大消耗时间越多
书写语言
语言越高级消耗时间越多
编译产生机器代码质量

机器执行指令速度

综上所述为便于比较算法本身优劣应排除其它影响算法效率原因
从算法中选取种对于所研究问题来说是基本操作原操作以该基本操作重复执行次数作为算法时间量度 (原操作在所有该问题算法中都相同)
T(n)=O(f(n))
上示表示随问题规模n增大算法执行时间增长率和f(n)增长率相同称作算法渐近时间复杂度简称时间复杂度
求4*4矩阵元素和T(4)=O(f(4))
f=n*n;
sum( num[4][4]) 
{  i,j,r=0; 
for(i=0;i<4;i)
for(j=0;j<4;j) 
rnum[i][j]; /*原操作*/
 r; 
}
最好情况:
T(4)=O(0)
最坏情况:
T(4)=O(n*n)
ispass( num[4][4]) 
{  i,j; 
for(i=0;i<4;i)
for(j=0;j<4;j) 
(num[i][j]!=i*4+j+1)
 0; 
 1; 
}
原操作执行次数和包含它语句频度相同语句频度指是该语句重复执行次数
语句 
频度 
时间复杂度 
{x;s=0;}
1 
O(1) 
for(i=1;i<=n;i)
{x;sx;}
n 
O(n) 
for(j=1;j<=n;j)
for(k=1;k<=n;k)
{x;sx;}
n*n 
O(n*n) 

O(log n) 


 

基本操作执行次数不确定时时间复杂度 
平均时间复杂度
依基本操作执行次数概率计算平均
最坏情况下时间复杂度
在最坏情况下基本操作执行次数

2、算法存储空间需求
类似于算法时间复杂度空间复杂度可以作为算法所需存储空间量度
记作:
S(n)=O(f(n))
若额外空间相对于输入数据量来说是常数则称此算法为原地工作
如果所占空间量依赖于特定输入则除特别指明外均按最坏情况来分析
3、整理总结
渐近时间复杂度
空间复杂度

延伸阅读