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

来源：百度文库 编辑：神马文学网 时间：2024/04/27 23:57:54
本课主题： 算法效率的度量和存储空间需求
教学目的： 掌握算法的渐近时间复杂度和空间复杂度的意义与作用
教学重点： 渐近时间复杂度的意义与作用及计算方法
教学难点： 渐近时间复杂度的意义
授课内容：
一、算法效率的度量
算法执行的时间是算法优劣和问题规模的函数。评价一个算法的优劣，可以在相同的规模下，考察算法执行时间的长短来进行判断。而一个程序的执行时间通常有两种方法：
1、事后统计的方法。
缺点：不利于较大范围内的算法比较。（异地，异时，异境）
2、事前分析估算的方法。
程序在计算机上运行所需时间的影响因素
算法本身选用的策略
问题的规模规模越大，消耗时间越多
书写程序的语言语言越高级，消耗时间越多
编译产生的机器代码质量
机器执行指令的速度
综上所述，为便于比较算法本身的优劣，应排除其它影响算法效率的因素。
从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。 （原操作在所有该问题的算法中都相同）
T(n)=O(f(n))
上示表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。
求4*4矩阵元素和，T(4)=O(f(4))
f=n*n;
sum(int num[4][4])
{ int i,j,r=0;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
r+=num[i][j]; /*原操作*/
return r;
}
最好情况：
T（4）=O（0）
最坏情况：
T（4）=O（n*n）
ispass(int num[4][4])
{ int i,j;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
if(num[i][j]!=i*4+j+1)
return 0;
return 1;
}
原操作执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次数。
语句频度时间复杂度
{++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(log n)

基本操作的执行次数不确定时的时间复杂度
平均时间复杂度依基本操作执行次数概率计算平均
最坏情况下时间复杂度在最坏情况下基本操作执行次数
二、算法的存储空间需求
类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间的量度。
记作：
S(n)=O(f(n))
若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。
如果所占空间量依赖于特定的输入，则除特别指明外，均按最坏情况来分析。
三、总结
渐近时间复杂度
空间复杂度
第四课 算法效率的度量和存储空间需求 角的度量 教学设计和反思 勇气，度量和智慧 李开复的做事三原则：勇气，度量和智慧0 李开复的做事三原则：勇气，度量和智慧ORZ 极品人生的度量 武则天的度量 角的度量 华应龙 第四章?大六壬算法讲解 搜索引擎蜘蛛的爬行规律和算法 搜索引擎蜘蛛的爬行规律和算法 角的度量 片断赏析 理性立法和法律实施的效率 我国市场对第三方和第四方物流有何需求 TMS320C54x系列DSP存储空间的配置 团队学习的需求和方法 一、需求分析的概念和原则 男人和女人的爱情需求 团队学习的需求和方法 需求获取和需求分析 需求获取和需求分析 第四课 教练的基本能力和素质 【精华】数据结构和算法版旧的精华贴 数据结构与算法 第二帖 1.个人的年份(流年)算法及解释 2.个人特质算法和解释