资源简介

教学设计
课程基本信息
学科 信息技术 年级 高二 学期 秋季
课题 数据结构与算法效率
教学目标
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.试一试：学生自行推导时间复杂度并交流推导方法 三、常见的算法时间复杂度及耗时比较 有了对实际程序实例的对比分析后，学生对算法的时间复杂度概念有了基本的理解。这里主要侧重于理论分析，即比较不同程序的执行次数。通过教材中简单易懂的三个程序实例，搭建起学习的支架，可以让学生初步理解算法的时间复杂度分析的一般方法。通过对实际案例的对比分析，引导学生自主阅读教材内容，加深理解，从而实现知识的内化。在此基础上，引入“阶”的概念，简单介绍不同阶的时间复杂度。需要注意的是，“时间复杂度”并不与程序实际运行的“时间耗费”完全等价。程序的时间耗费依赖于不同的计算机硬软件等环境因素。
新课教学活动二：数据结构对算法效率的影响 问题导学：以我们曾经学习过的数组和链表为例，试回忆元素访问、插入、删除方面的效率差异，并完成下列表格。 教师引导学生使用相应的信息工具直观呈现二者操作的算法效率差异，并展示数组、链表中插入新元素之后的基本操作过程。 通过对以前所学知识的总结与归纳、提升，由旧知构建新知，实现抽象概念建立的顺利过渡，培养学生数据结构与算法关系密切相关的意识。本任务可以看成是活动一在本任务中的自然延伸。学生在回顾数组、链表中元素访问、插入、删除的操作时，可以利用相关信息工具进行直观演示即可，并不需要代码具体实现，从而可以保证课堂效率。
试一试：计算斐波那契数列第n项的值 （1）编写程序。 （2）比较不同算法实现的时间复杂度和空间复杂度。
拓展思考 1.你知道空间复杂度是如何度量的吗？ 2.有人认为现代计算机的运行速度足够快了，已经没有必要研究算法的效率了，你有什么体会？ 在学生掌握时间复杂度的基础上，让学生主动探究空间复杂度的度量问题和算法效率在实际生活中的应用问题，进一步提升解决问题的能力。
课堂小结 1. 算法效率分析的一般方法，时间复杂度的基本概念； 2. 数据结构与算法的紧密关系； 3. 合理评估算法效率的重要性。 概念学习需要先从生活实例出发，通过分析实例，培养学生对概念的感性认识，为深刻理解概念提供事实基础；有了事实基础和体验过程，还需要对知识进行归纳和总结，纳入原有知识结构，实现知识的升华。
教学设计思路
本课内容分配1课时完成，内容为数据结构与算法的关系。本节内容在梳理本书前四章内容的基础上进行归纳、提升，相关概念在本章后续学习中进一步深化。本节第一部分为探究求和问题的算法效率。方法一通过呈现“算法一”、“算法二”程序运行时间上的差异结果，让学生直观感受到同一问题运用不同算法的执行效率的差异。方法二通过“算法一”、“算法二及其延伸等具体程序实例，介绍算法效率分析中的时间复杂度分析方法。第二部分则从学生已经熟悉的线性结构出发，简要分析数组与链表在元素访问、插入、删除方面的效率差异，体现出数据结构与算法效率之间的紧密关系。
指向的核心素养
信息意识：通过设置真实问题情境，引导学生发现不同的数据结构对算法效率有不同的影响，在处理实际问题能够有意识地选择合适的数据结构进行问题建模。 计算思维：运用简化、归约的基本思想方法，即排除掉其它无关的影响因素，从理论角度对实际程序进行算法的效率分析，对算法的运行效率进行评估、预测，并进行验证。 信息社会责任：能够思考、归纳出数据结构与算法在社会生活中的各项运用，它所带来的效率提升对科技发展、社会进步的重要意义。

展开更多......

收起↑