5.1数据结构与算法效率教学设计-2024-2025学年浙教版（2019）高中信息技术选修一

教学设计 课程基本信息 学科 信息技术 年级 高二 学期 秋季 课题 5.1数据结构与算法效率 教学目标 1. 课标内容要求： 1.6 通过比较解决同一个问题的不同算法，体验算法效率的差别，理解算法的正确性、可读性、健壮性，掌握算法分析的一般方法和过程，会计算算法的时空复杂度。 2. 核心素养指向： 计算思维：学生通过分析和计算算法的时间复杂度，学会从复杂的实际问题中提取出关键要素，构建数学模型，从而锻炼了计算思维能力。 信息意识：学生能感知到算法效率在生活中的应用以及重要性。在面对具体问题时，学生能够根据算法的效率差异，选择合适的算法来解决问题。 3. 教学目标 （1）通过比较解决同一个问题的不同算法，体验算法效率的差别，体会算法效率必要性。 （2）分析具体程序，理解算法效率分析的一般方法，会计算程序时间复杂度。 （3）回顾线性结构的特性，总结不同数据结构对算法效率的影响。 教学重难点 教学重点： 1. 计算简单程序时间复杂度。 2. 对比链表和数组在访问、插入删除元素的效率差异。 教学难点： 1. 计算简单程序时间复杂度。 教学过程 教学环节 教学活动 设计意图 情境导入 根据传说中高斯计算从1加到100的总和的方法和其他同学的计算方法对比，引出算法的效率的概念。 用故事的方式激发学生兴趣，引导学生理解算法效率的概念，对提高算法效率的重要性有初步感受。 知识讲解 教师讲授：算法效率、时间复杂度、空间复杂度的概念。明确本节课研究时间复杂度，引出时间复杂度是反映算法执行所需要的时间。 承上启下，解释导入中算法效率的概念。展开知识体系，并将着力点聚集于时间复杂度，引出测试执行时间。 活动： 测试执行时间 教师讲授：用Python中的time模块，记录算法开始前和结束后的系统时间，其差值就是运行时间。 import time #导入time模块 start = time.time() #算法开始前的系统时间 #在此处添加需要执行的程序 end = time.time() #算法结束后的系统时间 print("%.10f" %(end-start)) #计算差值并保留10位小数 算法1 算法2 def sum1(n): sum = 0 for i in range(1,n+1): sum = sum+i return sum def sum2(n): sum = n*(n+1)/2 return sum 学生活动： 1.连续运行算法1和算法2五次，并记录每次运行时间。 2.改变变量n的值，观察运行时间的变化情况。 算法1： 第1次 第2次 第3次 第4次 第5次 n= 10000           n= 100000           n= 1000000         算法2： 第1次 第2次 第3次 第4次 第5次 n= 10000           n= 100000           n= 1000000         观察记录下的结果，可以得到什么结论？ 请同学来回答得到的结论。 利用学生能理解并使用的程序段来测量程序的执行时间。例子选用“计算从1加到100的总和”的两种方法，例子选取时和导入相呼应，同时算法1运行时间会线性增长，呈现的数值关系较为清晰。在看到两个算法时，学生会产生哪个算法效率高的模糊设想。通过测试运行时间让学生具体的、直观地体会到高斯的计算方法和其他同学的计算方法在运行时间上的差异。由于一旦计算数据过小，运行时间展示得不明显，所以n的值选取了10000，100000，1000000。通过多次运行同一算法，观察随着输入规模的增加，运行时间如何变化，并总结得出结论。 学生总结结论。预设学生提出（1）不同计算机运行时间不相同。（2）算法1呈线性增加，算法2运行时间与n无关且近似为0。 反思过渡 教师讲授：根据学生得到的结论，分析直接运行程序测试运行时间来评判算法效率的不妥之处。引发学生疑问如何找一种不需要运行程序，且与外界因素无关的度量指标来评估算法的执行时间。并通过如下推导将评估算法执行时间的指标定为语句的总执行次数。 通过结论反思测试执行时间的方法虽然可以直观地看出算法效率，但是有不妥之处。学生理解外部环境对算法运行时间的影响。通过讨论不同编程语言、不同设备对算法运行时间的影响，以及引入基于代码本身的评估方法，鼓励学生从更高的层面思考问题，培养他们的抽象思维能力。 知识讲解 教师讲授：分析算法1和算法2的语句执行次数T。1.对代码进行编号。2.逐句分析语句执行次数。最终得到语句的总执行次数和n相关的函数，并解释问题规模n的概念。 教师讲授：分析T（n）的式子，通过具体数值代入，感受对T(n)起主导作用的部分是n。并提出“大O记法”的概念，介绍推导大O阶的方法。 通过逐句分析代码执行次数，拆解代码，提高学生的问题解决能力，培养计算思维。 实例分析 计算时间复杂度 例1.该程序的时间复杂度是： n=int(input()) s = 0 x = 0 for i in range(1,n+1): for j in range(1,n+1): x = x + 1 s = s + x print(s) 例2.该程序的时间复杂度是： def f(n): s = 0 i = 1 while i < =n : s = s + i i = i * 2 return s print(f(4)) 两道题目可以及时检验学生对课程内容的理解程度和掌握情况，让学生掌握算法的时间复杂度分析的一般方法。通过第一道题目教师可以了解学生是否能够将所学知识应用到实际问题中，以及他们在解决问题时的思路和方法。第二道题目，有一定的难度，需要学生有计算思维和程序分析能力。 归纳提升 学生活动： for i in range(1,n+1): sum = sum+i for i in range(1,n+1): for j in range(1,n+1): x = x + 1 s = s + x while i <= n : s = s + i i = i * 2 问题1:如果问题规模(n)相同，比较三段代码的时间复杂度。 问题2:在将三段代码拼接后，新代码段的时间复杂度是多少？ 教师讲授：介绍了常见时间复杂度，了解常见函数中n变大的情况下的差异性，展示常见函数的增长情况。 学生活动：思考未来在设计算法的时候如何降低时间复杂度。 培养学生归纳总结能力，通过问题1，希望学生可以对O(logn)和O(n)直观地比较。通过问题2，希望学生理解“只保留最高阶项” 活动： 旧知新学 教师讲授：从“程序=数据结构+算法”导入，以曾经学习过的数组和链表为例，回忆元素访问、插入、删除方面的效率差异，教师利用动画演示对应过程。 学生活动：填写表格，总结结论 小结： （1）如果需要频繁地访问数据元素，则优先选择________。 （2）如果需要频繁地执行插入删除操作，则优先选择____。 立足于“最近发展区”，通过旧知构建新知，实现抽象概念建立的平滑过渡，深化学生对数据结构与算法之间紧密联系的认识。作为任务一的自然拓展。因为学生在第二章学习数组链表的过程中会有初步的意识，所以学生在回顾数组、链表中元素访问、插入、删除的操作时，对学习过的知识进一步的总结。 拓展提升 学生活动：思考并讨论，算法效率在生活中哪些方面发挥着作用呢？ 设计思考和讨论，让学生理解算法的重要性，并将知识连接生活，还能激发他们学习信息技术的兴趣。 课堂总结 师生共同小结：本节课我们学习了数据结构与算法效率，介绍了算法的复杂度，分为时间复杂度、空间复杂度。介绍了大O记法和简单的时间复杂度计算以及常见时间复杂度比较。对比链表和数组在访问、插入删除元素的效率差异，理解了数据结构对算法效率的影响。 让学生对本节课内容进行梳理与归纳，在知识建构的同时能根据具体情况选择数据结构和设计更合适的算法。 学科网（北京）股份有限公司 $$