5.1 数据结构与算法效率（教学设计）信息技术浙教版2019选择性必修1

5.1 数据结构与算法效率 1课时（教学设计） 年级 高二年级 授课时间 1课时 课题 5.1 数据结构与算法效率 教学 目标 1.能结合具体程序实例，理解算法效率分析的一般方法。 2.回顾线性结构的特性，总结不同数据结构对算法效率的影响。 教学 重难点 重点：1.时间复杂度的计算。 2.选择合适的数据结构，提高算法效率。 难点：提高算法效率。 教学 准备 多媒体课件、多媒体教室、课本教材 教学过程 教师活动 学生活动 新 课 导 入 一、课堂导入 1.情境导入，展示问题1：一个人想要喝茶，但当时的情况是:开水没有，水壶要洗，茶壶和茶杯要洗;火已经生了，茶叶也有了怎么办? 2.情境导入，Google实验：搜索引擎是互联网上的检索技术，它能提高人们获取搜集信息的速度，为人们提供更好的网络使用环境，Google做过一个试验，显示10条搜索结果的页面载入需要0.4秒，显示30条搜索结果的页面载入需要0.9秒，结果后者使得Google总的流量和收入减少了20%。Google地图上线的时候，首页大小有100KB，后来下降到70~80KB。结果，流量在第一个星期上升了10%，接下来的3个星期又再上升了25%。Amazon(亚马逊公司)的统计也显示了相近的结果，首页打开时间每增加100毫秒，网站销售量会减少1%。 在计算机科学中，数据结构与算法有着密不可分的关系。 解决实际问题时，数据总是以一定的组织结构关系体现并存储，数据结构的设计和选择关注的是数据的逻辑结构、存储结构以及基本操作；算法的设计和选择更多的是关注如何在数据结构的基础上综合运用各种基本数据操作来解决实际问题。因此，算法的设计和选择总是依赖于数据结构，算法设计的同时也伴随着数据结构的设计，两者都是为最终解决问题服务。同时，数据结构的设计和选择会对算法效率产生一定的影响。 以生活实际为例，吸引学生参与课堂，抛出问题，让学生思考并观看教师的PPT课件上的图片提示，从而引出本堂课的主题。 通过导入生活中的算法问题和计算机科学领域的算法问题，以便顺利过渡到算法“时间复杂度”、“空间复杂度”的分析。 新 知 讲 授 二、算法效率 1.算法 概念：算法是解决某一特定类型问题的有限求解步骤。描述一个算法可以采用某一计算机语言，也可以才用自然语言和流程图等。 特征： ①有穷性 ②确定性 ③可行性 ④有0个或多个输入 ⑤有1个或多个输出 2.算法效率 算法:解决问题的方法 一同一个问题可能会有不同的解决方法，也就是说可能有不同的算法，就如同“一题多解”一样。有的算法效率高一些，有的算法效率低一些。 算法效率的高低可由算法复杂度来度量。 ①时间复杂度 反映了算法执行所需要的时间 ②空间复杂度 反映了算法执行所需要占用的存储空间 算法运行需要时间，一般将算法中语句的执行次数作为时间复杂度的度量标准。语句 总的执行次数T(n)是关于问题规模n的函数。 所谓问题规模（也称为输入的大小）是指处理问题的大小，即用来衡量输入数据量的整数。 在约瑟夫问题中，用数组或链表中元素的个数作为问题规模。 3.时间复杂度 时间复杂度常用符号〇表示，不包括T(n)函数的低阶项和首项系数如-(n-1)的量级与n2相同，其时间复杂度可表示成〇(n2)。 用〇()来体现算法时间复杂度，称之为大〇记法。 4.拓展链接:推导大〇阶的方法 用〇( )来体现算法时间复杂度，称之为大〇记法。其推导方法如下： (1)用常数1取代运行时间中的所有加法常数。 (2)在修改后的运行次数函数中，只保留最高阶项。 (3)如果最高阶项存在且不是1，那么去除与这个项相乘的常数。 得到的结果就是大〇阶。 随着问题规模n的增大，函数值增长较慢的算法较优。 求1+2+…+n的和 算法一： n=int(input()) #执行1次 s=(1+n)*n/2 #执行1次 print(s) #执行1次 算法一是顺序结构，语句总的执行次数为3次，算法中语句的执行次数与问题规模n无关，时间复杂度为〇(1)，称为常量阶。 算法二： n=int(input()) #执行1次 s=0 #执行1次 for i in range(1,n+1): #执行n次 s=s+i #执行n次 print(s) #执行1次 算法二中有一重循环，语句总的执行次数为2n+3次，则算法中语句的执行次数与问题规模n呈线性增大关系，时间复杂度是〇(n)，称为线性阶。 n=int(input()) s=0 x=0 for i in range(1,n+1): for j in range(1,n+1): x=x+1 #执行n*n次 s=s+x print(s) 程序段中包含二重循环，i从1到n，每次都让j循 环n次，而内 循 环 的 循 环 体 由 语 句“x=x+1” 和“s=s+x”组成，其执行次数就是n×n次，也就是这个算法中的循环体需要执行n2次，则算法中语句的执行次数与问题规模n呈平方增大关系，时间复杂度是〇(n2)，称为平方阶。此外，算法的时间复杂度还有对数阶〇(log2n)、指数阶〇(2n)等。 5.拓展链接:常见时间复杂度的耗时比较 常见的时间复杂度耗费时间的大小关系为：〇(1)＜〇(log2n)＜〇(n)＜〇(n2)＜〇(n3)＜〇(2n)＜〇(n!)。一些常见函数的增长率,如右图所示。 常见函数的增长率 一般将算法中语句的执行次数作为时间复杂度的度量标准。我们在分析时间复杂度的时候也只关注执行次数的增长次数及其常数倍。 语句总的执行次数T(n)是关于问题规模n的函数。 时间复杂度常用符号〇()表示。 在分析算法的时间复杂度时，我们需要知道三个方面： ①输入规模 不管使用什么算法，输入规模越大，运行效率肯定会更长。 ②算法的平均效率、最差效率和最优效率 在输入最优情况下的算法就叫最优效率。 在输入最坏情况下的算法就叫最差效率。 ③增长次数 在大规模的输入情况下考虑执行次数的增长次数。 算法的平均效率、最差效率和最优效率 ①最差效率 当输入规模为n时，算法在最坏情况下的效率。 ②最优效率 当输入规模为n时，算法在最优的情况下的效率。 ③平均效率 在实际的假设情况下，算法所可能发生的正推推断下所具有的效率。 一般是通过得到或者是假设各类输入的概率分布，以推导出我们所希望的基本操作次数。 算法的平均效率、最差效率和最优效率 ①最差效率 当输入规模为n时，算法在最坏情况下的效率。 ②最优效率 当输入规模为n时，算法在最优的情况下的效率。 ③平均效率 在实际的假设情况下，算法所可能发生的正推推断下所具有的效率。 一般是通过得到或者是假设各类输入的概率分布，以推导出我们所希望的基本操作次数。 在以顺序查找算法为例： 算法的最差效率：n个数据，在最后一次判断才找到，效率为n。 算法的最优效率：n个数据，第一次就判断就找到，效率为1 算法的平均效率：n个数据，我们先假设能找到的概率，然后我们需要求得在第一次查找到的概率、第二次查找到的概率等等一直求，然后算得总的操作次数，得出算法的平均效率 两个经验性的规则： ①最优效率的分析远远不如最差效率分析重要（因为最差效率可以确定算法运行时间的上界） ②如果一个算法的最优效率都不能满足我们的要求，那么我们就可以立即抛弃它。 6.探讨与讨论 （1）某算法的时间复杂度是〇(n),表明该算法( )。 A.问题规模是n B.问题规模与n成正比 C.执行时间等于n D.执行时间与n成正比 （2）下列有关算法的时间复杂度的说法,错误的是( ) A.如果时间复杂度为常数,则时间复杂度为〇(0) B.仅包含顺序结构的算法的时间复杂度为〇(1) C.如果算法中语句的执行次数与问题规模n呈线性增大关系,则时间复杂度为〇(n) D.如果算法中语句的执行次数与问题规模n呈平方增大关系,则时间复杂度为〇(n2) 三、 数据结构对算法效率的影响率 数据结构与算法的关系 1.在计算机科学中，数据结构与算法有着密不可分的关系。解决实际问题时，数据总是以一定的组织结构关系体现并存储，数据结构的设计和选择关注的是数据的逻辑结构、存储结构以及基本操作；算法的设计和选择更多的是关注如何在数据结构的基础上综合运用各种基本操作来解决实际问题。 2.数据组织成不同的结构，是为了满足不同问题的需求，便于算法对数据的操作，提高孙发处理数据的效率。算法的设计和选择总是依赖于数据结构，算法设计的同时也伴随着数据结构设计，两者都是为最终解决问题服务。算法是编程思想，数据结构则是这些思想的基础。 实例：现有一组n个数据需要存储。 第一种用数组的数据结构来存储记为n1 第二种用链表的数据结构来存储记为n2 ① 若要对元素进行插入和删除操作，则n1的时间复杂度为〇(n)。n2的时间复杂度为〇(1)。 ②若要随机访问其中的一个数据，则n1的时间复杂度为〇(1)。n2的时间复杂度为〇(n)。 由此可见：数据结构的不同选择会影响算法的运行效率。 3.探讨与讨论 （1）用对分查找法从数列3、6、7、10、12、16、25、30、75中找到数据10的查找次数是( ) A.2 B.3 C.4 D.7 （2）有如下Python程序代码: a=int(input("a=")) b=int(input("b=")) print("a=",a,"b=",b) a,b=b,a print("a=",a,"b=",b) 则该算法的时间复杂度为( ) A.〇(1) B.〇(n) C.〇(n) D.〇(2") 四、 课堂小练 1.某同学网购的书,三本书是三个不同的物流公司派送的,将图中每个节点进行编号,作为根节点的“家”编号为“H”其3个子节点(快递门店A，快递门店 B，快递门店 C)分别编号为“A”“B”“C”，图中两结点的连接线表示“权”,值为用时，详见下图。依次列出所有可能走法的分析树，求出取书用时最短时的路径，下列选择正确的是( ) A.H-A-C-B-H B.HC-B-A-H C.H-A-B-CH D.H-B-A-C-H 五、小结 1.算法效率 2.数据结构对算法效率的影响 通过知识的回忆，算法的概念和特征，从而让学生能够更有效的理解什么是算法效率。 有了对实际程序实例的对比分析后，学生 对算法的时间复杂度概念有了基本的理 解。这里主要侧重于理论分析，即比较不同程序的执行次数。需要注意的是，“时间复杂度”并不与程序实际运行的“时间耗费”完全等价。程序的时间耗费依赖于不 同的计算机硬软件等环境因素，并且程序 的运行时间往往还与测试数据的规模也有 很大关系，比如求1+2+…+n的和，通过教材中简单易懂的三个程序实例，搭建起学习的“脚手架”，可以让学生初步理解算法的时间复杂度分析的一般方法。通过对实际案例的对 比分析，引导学生自主阅读教材内容，加深理解，从而实现知识的内化。在此基础上，教师可以引入“阶”的概念，简单介 绍不同阶的时间复杂度。 算法效率对实际生活产生非常大的影响， 对算法效率分析可以从两个维度展开:“时 间复杂度”即算法的时间耗费，“空间复杂度”即算法的空间耗费。在此基础上，可以从三个方面输入规模、算法的平均效率、最差效率和最优效率、增长次数来分析算法的复杂度。 通过课堂练习，加深同学们对算法效率的理解。 通过案例讲解：现有一组n个数据需要存储， 体验算法效率对实际生活产生非常大的影响，逐步形成运用有效的算法效率解决问题的思维方式和学科方法。 用练习巩固课堂知识，帮助学生更好地掌握。 课 堂 练 习 （有题有答案有解析） 1.算法效率的高低可由 来度量。 2.算法的时间耗费是 。 3.算法的空间耗费是 。 4.用O( )来体现算法时间复杂度，称之为 。 5.常见的算法的时间复杂度有： 、 、 、 、 、 、 。 6.算法的特征包括： 、 、 、 、 。 7..时间复杂度常用符号 表示。 8.下列常见的时间复杂度耗费时间的大小中的最小值是（） A.O(1) B.O(n) C.O(n3 ) )D.O(n!) 9.某算法的时间复杂度是〇(n),表明该算法()。 A.问题规模是n B.问题规模与n成正比 C.执行时间等于n D.执行时间与n成正比 参考答案： 1.算法复杂度 2.时间复杂度 3.空间复杂度 4.大O记法 5.O(1)、O(log2n)、O(n)、O(n2 )、O(n3 ) 、O(2n )、O(n!) 6.有穷性、确定性、可行性、有0个或多个输入、有1个或多个输出 7.〇 8.【答案】A [解析]常见的时间复杂度耗费时间的大小关系为：O(1)＜O(log2n)＜O(n)＜O(n2 )＜O(n3 ) ＜O(2n )＜O(n!)。 9.【答案】D [解析]算法的时间复杂度是〇(n),这是设定问题规模为n的分析结果,所以A、B都不对;它也不表明执行时间等于n,它只表明算法的执行时间T(n)≤cXn(c为比例常数)。有的算法,如nXn矩阵的转置,时间复杂度为〇(n),不表明问题规模是n。 课 堂 小 结 课堂小结 1.算法效率 2.数据结构对算法效率的影响 作 业 设 计 1.下列有关算法的时间复杂度的说法,错误的是() A.如果时间复杂度为常数,则时间复杂度为〇(0) B.仅包含顺序结构的算法的时间复杂度为〇(1) C.如果算法中语句的执行次数与问题规模n呈线性增大关系,则时间复杂度为〇(n) D.如果算法中语句的执行次数与问题规模n呈平方增大关系,则时间复杂度为〇(n2) 2.递归算法的函数调用时,处理参数和返回地址,通常使用的数据结构是 A.数组 B.链表 C.队列 D.栈 3.算法的时间复杂度是指什么?() A.算法执行所需的时间 B.算法中语句的数量 C.算法所需内存空间 D.算法执行所需时间随输入规模增长的趋势 4.下列关于算法效率分析的说法,正确的是() A.算法复杂度是指算法控制结构的复杂程度 B.算法的时间复杂度是指算法执行的速度 C.算法的空间复杂度是指算法执行所需的时间 D.算法的时间复杂度是指算法在执行过程中基本运算的次数 5.有如下 Python程序代码: n=int(input("n=")) t=1 while 2 ** t<n: t=t+1 print("t=",t) 则该算法的时间复杂度为（） A.〇(1) B.〇(n) C.〇(log2n) D.〇(2n) 6.有如下 Python程序代码: s=0 n=int(input( "n=")) s=n*(n+1)//2 print("s=",s) 则该算法的时间复杂度为() A.〇(1) B.〇(n) C.〇(n2） D.〇(2n) 7.用对分查找法从数列3、6、7、10、12、16、25、30、75中找到数据10的查找次数是() A.2 B.3 C.4 D.7 8.有如下Python程序代码: a=int(input("a=")) b=int(input("b=")) print("a=",a,"b=",b) a,b=b,a print("a=",a,"b=",b) 则该算法的时间复杂度为() A.〇(1) B.〇(n) C.〇(n) D.〇(2") 9.某 Python 程序如下： n=int(input("n=") ansl=ans2=0 fori in range(0,n,2): for j in range(n): ansl=ans1+2 ans2=ans2+2*ans1 print("ansl=",ans1,"ans2=",ans2) 该算法的时间复杂度是 A.〇(1) B.〇(n) C.〇(n²) D.〇(2n) 10.有如下 Python程序段: n=int(input('请输入n:')) s=0 x=0 for i in range(n-1): for j in range(i+1,n): x=i+j s=s+x print(s) 该算法的时间复杂度为() A.〇(1) B.〇(n) C.〇(n²) D.〇(log2n) 11.某同学网购的书,三本书是三个不同的物流公司派送的,将图中每个节点进行编号,作为根节点的“家”编号为“H”其3个子节点(快递门店A，快递门店 B，快递门店 C)分别编号为“A”“B”“C”，图中两结点的连接线表示“权”,值为用时，详见下图。依次列出所有可能走法的分析树，求出取书用时最短时的路径，下列选择正确的是() A.H-A-C-B-H B.H-C-B-A-H C.H-A-B-C-H D.H-B-A-C-H 12.有如下 Python程序代码: n=int(input("please input n:")) s=0 for i in range(n-1): for j in range(n): s=s+i print("s=",s) 则该程序的时间复杂度为() A.〇(1) C.〇(log2n) B.〇(n) D.〇(n2) 参考答案： 1.【答案】A [解析]本题主要考查的是时间复杂度的表示。如果时间复杂度为常数,则时间复杂度为〇(1),因此答案为A。 2.【答案】D [解析]本题主要考查的是递归算法。计算机在执行递归程序时，是通过栈结构的调用来实现的，因此答案为D。 3.【答案】A [解析]所谓算法的时间复杂度，是指执行算法所需要的计算:工作量。为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程叶，所需基本运算的执行次数米度量.算法的工作量。故选:A。 4.【答案】D [解析]算法复杂度分为时间复杂度和空间复杂度,其中时间复杂度反映了算法执行所需要的时间,而空间复杂度反映了算法执行所需要占用的存储空间。 5.【答案】C [解析]本题主要考查的是时间复杂度的计算。观察程序,可计算出t=log2n，因此其时间复杂度〇(log2n),答案为C。 6.【答案】A [解析]本程序只包含顺序结构，时间复杂度为〇(1),因此,答案为A。 7.【答案】C [解析]假设数列存储于数组a中，以下为查找10的过程: 第一次查找:i=1，j=9，m=(i+j)\2=5，a(5)=12，12>10，j=m-1=4; 第二次查找:i=1，j=4，m=(i+j)\2=2，a(2)=6，6<10，i=m+1=3; 第三次查找:i=3，j=4，m=(i+j)\2=3，a(3)=7，7<10，i=m+1=4; 第四次查找:i=4，j=4，m=(i+j)\2=4，a(4)=10，找到数据，共查找了四次， 故选:C. 8.【答案】A [解析]本题主要考查的是时间复杂度的计算。本题中的程序控制结构只包含顺序结构，可知时间复杂度为〇(1),因此,答案为A。 9.【答案】C [解析]本题考查时间复杂度的计算。题中的程序为二重循环,语句的执行次数为一㎡,与量级㎡ 相同,因此其时间复杂度为〇(n2)。 10.【答案】C [解析]本题使用二重循环求s的值,因此时间复杂度为〇(n),答案为C。 11.【答案】A [解析]将图中的图结构可以转换为下图的数结构，依次计算每一种情况。其中路径H-A-C-B-H、H-B-C-A-H用时最短，其时长为2+6+4+5=17故选:A。 12.【答案】D [解析]本题程序使用的是二重循环,外循环共执行n一1次,内循环共执行n次,因此,时间复杂度为 〇(n),答案为 D。 反 思 评 价 本堂课讲解的是理论方面的知识，比较枯燥，只有通过大量的举例来充实课堂。通过列举实例，分析数据结构与算法效率，让学生们通过实际问题，恰当地选择有效的算法。体验用数据结构与算法解决问题的基本流程，逐步形成运用数据结构与算法解决问题的思维方式和学科方法。最终能够熟练掌握数据结构与算法效率。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$