5.1 数据结构与算法效率(教学设计)信息技术浙教版选择性必修1
年级 | 高二年级 | 授课时间 | 1课时 |
课题 | 5.1 数据结构与算法效率 | ||
教学 目标 | 1.能结合具体程序实例,理解算法效率分析的一般方法。 2.回顾线性结构的特性,总结不同数据结构对算法效率的影响。 | ||
教学 重难点 | 重点:1.时间复杂度的计算。 2.选择合适的数据结构,提高算法效率。 难点:提高算法效率。 | ||
教学 准备 | 多媒体课件、多媒体教室、课本教材 | ||
教师活动 | 学生活动 | |
新 课 导 入
| 一、课堂导入 1.情境导入,展示问题1:一个人想要喝茶,但当时的情况是:开水没有,水壶要洗,茶壶和茶杯要洗;火已经生了,茶叶也有了怎么办? 2.情境导入,Google实验:搜索引擎是互联网上的检索技术,它能提高人们获取搜集信息的速度,为人们提供更好的网络使用环境,Google做过一个试验,显示10条搜索结果的页面载入需要0.4秒,显示30条搜索结果的页面载入需要0.9秒,结果后者使得Google总的流 | 以生活实际为例,吸引学生参与课堂,抛出问题,让学生思考并观看教师的PPT课件上的图片提示,从而引出本堂课的主题。
|
原创精品资源学科网独家享有版权,侵权必究!
学科网(北京)股份有限公司
学科网(北京)股份有限公司
| 量和收入减少了20%。Google地图上线的时候,首页大小有100KB,后来下降到70~80KB。结果,流量在第一个星期上升了10%,接下来的3个星期又再上升了25%。Amazon(亚马逊公司)的统计也显示了相近的结果,首页打开时间每增加100毫秒,网站销售量会减少1%。 在计算机科学中,数据结构与算法有着密不可分的关系。 解决实际问题时,数据总是以一定的组织结构关系体现并存储,数据结构的设计和选择关注的是数据的逻辑结构、存储结构以及基本操作;算法的设计和选择更多的是关注如何在数据结构的基础上综合运用各种基本数据操作来解决实际问题。因此,算法的设计和选择总是依赖于数据结构,算法设计的同时也伴随着数据结构的设计,两者都是为最终解决问题服务。同时,数据结构的设计和选择会对算法效率产生一定的影响。 |
通过导入生活中的算法问题和计算机科学领域的算法问题,以便顺利过渡到算法“时间复杂度”、“空间复杂度”的分析。 |
新 知 讲 授
| 二、算法效率 1.算法 概念:算法是解决某一特定类型问题的有限求解步骤。描述一个算法可以采用某一计算机语言,也可以才用自然语言和流程图等。 特征: ①有穷性 ②确定性 ③可行性 ④有0个或多个输入 ⑤有1个或多个输出 2.算法效率 算法:解决问题的方法 一同一个问题可能会有不同的解决方法,也就是说可能有不同的算法,就如同“一题多解”一样。有的算法效率高一些,有的算法效率低一些。 |
通过知识的回忆,算法的概念和特征,从而让学生能够更有效的理解什么是算法效率。
有了对实际程序实例的对比分析后,学生 |
原创精品资源学科网独家享有版权,侵权必究!
学科网(北京)股份有限公司
学科网(北京)股份有限公司
| 算法效率的高低可由算法复杂度来度量。 ①时间复杂度 反映了算法执行所需要的时间 ②空间复杂度 反映了算法执行所需要占用的存储空间 算法运行需要时间,一般将算法中语句的执行次数作为时间复杂度的度量标准。语句 总的执行次数T(n)是关于问题规模n的函数。 所谓问题规模(也称为输入的大小)是指处理问题的大小,即用来衡量输入数据量的整数。 在约瑟夫问题中,用数组或链表中元素的个数作为问题规模。 3.时间复杂度 时间复杂度常用符号〇表示,不包括T(n)函数的低阶项和首项系数如-(n-1)的量级与n2相同,其时间复杂度可表示成〇(n2)。 用〇()来体现算法时间复杂度,称之为大〇记法。 4.拓展链接:推导大〇阶的方法 用〇( )来体现算法时间复杂度,称之为大〇记法。其推导方法如下: (1)用常数1取代运行时间中的所有加法常数。 (2)在修改后的运行次数函数中,只保留最高阶项。 (3)如果最高阶项存在且不是1,那么去除与这个项相乘的常数。 得到的结果就是大〇阶。 随着问题规模n的增大,函数值增长较慢的算法较优。 | 对算法的时间复杂度概念有了基本的理 解。这里主要侧重于理论分析,即比较不同程序的执行次数。需要注意的是,“时间复杂度”并不与程序实际运行的“时间耗费”完全等价。程序的时间耗费依赖于不 同的计算机硬软件等环境因素,并且程序 的运行时间往往还与测试数据的规模也有 很大关系,比如求1+2+…+n的和,通过教材中简单易懂的三个程序实例,搭建起学习的“脚手 |
原创精品资源学科网独家享有版权,侵权必究!
学科网(北京)股份有限公司
学科网(北京)股份有限公司