教学设计 课程基本信息 学科 信息技术 年级 高二 学期 秋季 课题 数据结构与算法效率 教学目标 1. 初步理解数据结构与算法的关系，能评判数据结构运用的合理性。 2. 通过分析具体程序实例，理解算法效率分析的必要性，学会常见算法分析方法。 3. 通过分析线性结构的特性，理解不同数据结构对算法效率的影响。 教学内容 教学重点： 会运用算法复杂度度量常见算法的效率。 教学难点： 理解不同数据结构对算法效率的影响。 教学过程 教学环节 教学过程 设计意图 知识回顾 1.回顾数据结构的概念及常见的数据结构类型。 2.引出同一问题采用不同的数据结构，算法的效率也会不尽相同。 回顾前面章节所学的数据结构知识，过渡到算法的效率问题探究。 情境描述 求和问题的效率探究。 1.高斯算法实现求和； 2.累加算法时间求和。 思考：两种算法的执行效率是否一样？ 通过导入生活中的算法问题，以便顺利过渡到算法效率的度量方式。 新课教学活动一：算法效率度量方式 方法一：计算算法执行所需时间度量算法效率。 学生在程序中导入time模块，通过time.time()命令记录程序开始和结束的时间点，两者相减得到运行时间。 例如：高斯算法的运行时间计算 import time start = time.time() n=int(input()) s=(1+n)*n/2 print(s) end = time.time() print(end - start) 同样的方法计算累加求和算法的运行时间。 通过计算机的计时功能，直接计算程序的运行时间，让学生通过尝试不同的n值输入，对比两种算法的运行时间，发现当数据规模n大到一定程度时，高斯算法的运行时间明显少于累加求和，进而得出高斯算法的算法效率高的结论。 方法二：预估算法复杂度度量算法效率 一、时间复杂度和空间复杂度的概念 二、重点探究算法时间复杂度的表示 在运行程序之前，事先预估算法的执行效率。通过分析上述求和案例，请学生比较教材中“算法一”、“算法二”等具体程序实例。 算法一： n=int(input()) #执行1次 s=(1+n)*n/2 #执行1次 print(s) #执行1次 算法二： n=int(input()) #执行1次 s=0 #执行1次 for i in range(1,n+1): #执行n+1次 s=s+i #执行n次 print(s) #执行1次 1.分析：两种算法的执行次数T(n),时间复杂度的表示方法O(T(n))； 2.推导：用大O阶的推导方法推导出算法一和算法二的时间复杂度。 算法三： 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) 3.试一试：学生自行推导时间复杂度并交流推导方法 三、常见的算法时间复杂度及耗时比较 有了对实际程序实例的对比分析后，学生对算法的时间复杂度概念有了基本的理解。这里主要侧重于理论分析，即比较不同程序的执行次数。通过教材中简单易懂的三个程序实例，搭建起学习的支架，可以让学生初步理解算法的时间复杂度分析的一般方法。通过对实际案例的对比分析，引导学生自主阅读教材内容，加深理解，从而实现知识的内化。在此基础上，引入“阶”的概念，简单介绍不同阶的时间复杂度。需要注意的是，“时间复杂度”并不与程序实际运行的“时间耗费”完全等价。程序的时间耗费依赖于不同的计算机硬软件等环境因素。 新课教学活动二：数据结构对算法效率的影响 问题导学：以我们曾经学习过的数组和链表为例，试回忆元素访问、插入、删除方面的效率差异，并完成下列表格。 教师引导学生使用相应的信息工具直观呈现二者操作的算法效率差异，并展示数组、链表中插入新元素之后的基本操作过程。 通过对以前所学知识的总结与归纳、提升，由旧知构建新知，实现抽象概念建立的顺利过渡，培养学生数据结构与算法关系密切相关的意识。本任务可以看成是活动一在本任务中的自然延伸。学生在回顾数组、链表中元素访问、插入、删除的操作时，可以利用相关信息工具 ... ...
~~ 您好，已阅读到文档的结尾了 ~~
