5.1 数据结构与算法效率-教学设计（表格式）

教学设计 课程基本信息 课题 5.1 数据结构与算法效率 教学目标 1. 启发学生认识数据结构与算法的关系。 2. 引导学生进行时间复杂度与空间复杂度的计算。 3. 通过实例的形式让学生进行空间复杂度的计算。 4. 知道空间复杂度。 5. 能理解数组与链表在操作中算法效率的异同。 6. 引导学生逐步自觉将算法的效率应用在算法程序设计中，根据问题选择合适的数据结构，提高算法效率。 指向的核心素养 ●信息意识：学生能够结合实例，自觉、主动地有意识地选择恰当的数据结构表达信息。 ●计算思维：学生能够结合实例，设计数据结构。 ●数字化学习与创新：培养学生自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。 ●信息社会责任：自觉遵守相应的伦理道德和法律法规。 教学内容 教学重点： 1.时间复杂度的计算。 2.选择合适的数据结构，提高算法效率。 教学难点： 提高算法效率。 教学过程 一、认识本节课的任务，自学教材内容。 二、情境导入：Google实验 联网上的检索技术，它能提高人们获取搜集信息的速度，为人们提供更好的网络使用环境，Google做过一个试验，显示10条搜索结果的页面载入需要0.4秒，显示30条搜索结果的页面载入需要0.9秒，结果后者使得Google总的流量和收入减少了20%。Google地图上线的时候，首页大小有100KB，后来下降到70~80KB。结果，流量在第一个星期上升了10%，接下来的3个星期又再上升了25%。 Amazon（亚马逊公司）的统计也显示了相近的结果，首页打开时间每增加100毫秒，网站销售量会减少1%。 三、算法效率的重要性： 1、算法+数据结构=程序 2、智慧农场监测系统、入口处的红外测温、人脸识别程序等两个程序应用来说明算法效率的重要性。 四、算法效率分析 1、时间复杂度：指该算法的时间耗费，是该算法中基本操作重复执行的次数与问题规模n的某个函数。 （1） 四个实例练习及分析： 1+2+3+……+100=？算法一 1+2+3+……+100=？算法二 二维矩阵输出 对分查找 分别计算执行次数，得出时间复杂度 （2）总结大O表示法 （3）小结常用的时间复杂度。 2、空间复杂度：指该算法执行所需要占用的存储空间。（主要指临时占用内存空间） 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。高中阶段主要考虑时间复杂度。 算法空间复杂度类似于时间复杂度，只是计算的不是运行次数，而是在运行过程中临时变量被运用次数。 五、比较数组和链表两种不同的数据结构对算法的影响。填写表格 数组链表应用场景组织结构操作特性访问：数据访问效率较高 时间复杂度：_____ 插入或删除：需要移动大量数组元素 时间复杂度：_____访问：需要从头结点开始寻找 时间复杂度：_____ 插入或删除：只要找出某个结点位置，可以方便操作 时间复杂度：_____ 六、课堂小结 七、自我评价 对自己的表现进行客观的评价，并思考后续完善的方向。（3=优秀，2=一般，1=仍需加油） 评分项自我评价能以高斯问题为例认识算法时间复杂度的概念 3 2 1能够对简单程序分析其算法时间复杂度 3 2 1能够对线性结构的算法时间复杂度进行简要分析 3 2 1能合理评估算法效率的重要性 3 2 1从此自觉将算法时间复杂度融入算法设计中 3 2 1 八、课后作业 1.度量某个算法效率高低的两个方面： 、 。 2.分析右侧流程图算法的时间复杂度是（ ）： A.常数阶 B.线性阶 C.指数阶 D.对数阶 三、分析程序段的时间复杂度： 作业答案： 1.时间复杂度 空间复杂度 2.B 3 ... ...