项目一 任务三 算法的分析和评价（课件）-《算法与程序设计-C#》（河北科学技术出版社）同步精品课堂

1.3 算法的分析和评价 算法与程序设计——C# 同步精品课堂 河北科学技术出版社 1 一 教学目标 二 教学重难点 教学重点： 1.了解算法时间复杂度的定义 2.了解算法空间复杂度的定义 教学难点： 1.了解和算法执行时间相关有哪几部分因素 2.理解一个算法在计算机存储器上所占用的存储空间与哪些因素有关 三 导入新课 小明家里来了客人，小明要烧一壶水冲茶叶，具体步骤如下： 取茶叶2分钟，烧水10分钟，洗茶杯5分钟，冲茶3分钟 我们可以怎样尽快让完成为客人泡茶的任务？ 三 导入新课 小明家里来了客人，小明要烧一壶水冲茶叶，具体步骤如下： 取茶叶2分钟，烧水10分钟，洗茶杯5分钟，冲茶3分钟 我们可以怎样尽快让完成为客人泡茶的任务？ 方法一：按照上面步骤依次执行，共需要20分钟 方法二：在烧水的同时去取茶叶，洗茶杯，然后水烧开后再冲茶叶。 你会怎么选呢？ 四 新知讲授 定义：是衡量算法执行时间随输入规模增长而变化的度量 时间复杂度 注意：时间复杂度并不是一个具体的时间，而是一个函数 作用：估计算法在最坏情况下所需要的资源 四 新知讲授 1.问题方面 时间复杂度有关的因素 （1）数据存储的存储结构：数据结构是否复杂 （2）问题的规模：要处理信息的规模 实例举例：茶放在哪里了？洗茶壶在哪？ 实例举例：要招待的客人数量 四 新知讲授 2.算法方面 时间复杂度有关的因素 （1）算法采用的数据模型：数据特征的抽象 （2）算法设计的策略：算法的策略 实例举例：茶壶大小，茶杯个数和形状 实例举例：算法的不同 四 新知讲授 3.计算机方面 时间复杂度有关的因素 （1）实现算法的程序语言：数据特征的抽象 （2）编译出算法的质量：要洗出怎么茶杯，烧多少度的水 实例举例：茶壶大小，茶杯个数和形状 实例举例：编译方式和代码简洁度 （3）计算机的执行速度：计算机运行的速度 实例举例：执行这些任务的速度 四 新知讲授 定义：在陌生的找出班级中的一名同学。（手上有这个班级学生的基本信息，无照片） 项目例子： 参考实例： （1）让每个学生写一块带有自己名字牌子，和手中信息对比直接轻松找到 （2）依次每个同学报名字，直到报到对应的同学 （3）确定要找同学的信息，每次都描述一条同学信息，不符合的回到座位，最后剩下的就是要找的学生 四 新知讲授 时间复杂度常见分类 （1）常数时间复杂度（O（1））：算法执行时间保持不变 （2）线性时间复杂度（O（n））：算法执行时间与数据数量线性相关 （3）对数时间复杂度（O（log n））：算法执行时间随数据输入量增加而增加，不过比较慢 （4）平方时间复杂度（O（n^2））：算法执行时间随数据输入量增加呈平方级增长 （5）指数时间复杂度（O（2^n））：算法执行时间与数据输入量增加呈指数级增长 四 新知讲授 定义：该算法消耗的存储空间 空间复杂度 三个表现方面： （1）存储算法本身所占用的存储空间：例如我们平时下载的软件前端 （2）算法的输入输出数据所占用的存储空间：我们在使用软件时候生成的数据 （3）算法在运行过程中临时占用的存储空间：相当于运行内存存储的内容 尝试分析大型单机独立3D游戏，城市规划建模类软件，即时枪战类游戏分别对于空间复杂度哪些方面有较高需求。 五 师生互动 六 随堂练习 练习：下列对于时间复杂度描述正确的是（ ）。 A.衡量算法执行时间的度量 B.用来估计算法在最坏情况下所需要的资源 C.时间复杂度往往是一个具体的时间 D.与空间复杂度不会相互影响 B 七 课堂小结 八 布置作业 作业： （1）完成练习的对应内容。 （2）记忆有关算法复杂度的内容。 感谢观看 $$