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

第1节 数据结构与算法效率（1课时） 第5章 数据结构与算法 浙教版（2019） 选修一 算法效率 01 数据结构对算法效率的影响 02 学习目录 能结合具体程序实例，理解算法效率分析的一般方法。 01 回顾线性结构的特性，总结不同数据结构对算法效率的影响。 02 学习目标 PART 01 算法效率 新课导入 想 想 一 一个人想要喝茶，但当时的情况是:开水没有，水壶要洗，茶壶和茶杯要洗;火已经生了，茶叶也有了怎么办? 问题：泡茶 烧开水 洗开 水壶 灌凉水 洗茶壶 洗茶杯 拿茶叶 泡茶喝 洗开 水壶 洗茶壶 洗茶杯 拿茶叶 灌凉水 烧开水 泡茶喝 洗开 水壶 灌凉水 烧开水 拿茶叶 洗茶壶 洗茶杯 泡茶喝 新课导入 看 看 一 搜索引擎是互联网上的检索技术，它能提高人们获取搜集信息的速度，为人们提供更好的网络使用环境，Google做过一个试验，显示10条搜索结果的页面载入需要0.4秒，显示30条搜索结果的页面载入需要0.9秒，结果后者使得Google总的流量和收入减少了20%。Google地图上线的时候，首页大小有100KB，后来下降到70~80KB。结果，流量在第一个星期上升了10%，接下来的3个星期又再上升了25%。Amazon(亚马逊公司)的统计也显示了相近的结果，首页打开时间每增加100毫秒，网站销售量会减少1%。 Google实验 新课导入 在计算机科学中，数据结构与算法有着密不可分的关系。 解决实际问题时，数据总是以一定的组织结构关系体现并存储，数据结构的设计和选择关注的是数据的逻辑结构、存储结构以及基本操作；算法的设计和选择更多的是关注如何在数据结构的基础上综合运用各种基本数据操作来解决实际问题。因此，算法的设计和选择总是依赖于数据结构，算法设计的同时也伴随着数据结构的设计，两者都是为最终解决问题服务。同时，数据结构的设计和选择会对算法效率产生一定的影响。 算法 算法效率 一 概念 算法是解决某一特定类型问题的有限求解步骤。描述一个算法可以采用某一计算机语言，也可以才用自然语言和流程图等。 算法的特征 有穷性 确定性 可行性 有1个或多个输出 有0个或多个输入 1 2 3 4 5 算法效率 一 一同一个问题可能会有不同的解决方法，也就是说可能有不同的算法，就如同“一题多解”一样。有的算法效率高一些，有的算法效率低一些。 算法:解决问题的方法 1 2 算法效率 时间复杂度 反映了算法执行所需要的时间 空间复杂度 反映了算法执行所需要占用的存储空间 算法效率的高低可由算法复杂度来度量。 算法效率 一 算法运行需要时间，一般将算法中语句的执行次数作为时间复杂度的度量标准。语句 总的执行次数T(n)是关于问题规模n的函数。 所谓问题规模（也称为输入的大小）是指处理问题的大小，即用来衡量输入数据量的整数。 在约瑟夫问题中，用数组或链表中元素的个数作为问题规模。 1 2 3 算法效率 一 时间复杂度 时间复杂度常用符号〇表示，不包括T(n)函数的低阶项和首项系数如-(n-1)的量级与n2相同，其时间复杂度可表示成〇(n2)。 用〇()来体现算法时间复杂度，称之为大〇记法。 算法效率 一 拓展链接 推导大〇阶的方法 用〇( )来体现算法时间复杂度，称之为大〇记法。其推导方法如下： 1.用常数1取代运行时间中的所有加法常数。 2.在修改后的运行次数函数中，只保留最高阶项。 3.如果最高阶项存在且不是1，那么去除与这个项相乘的常数。 得到的结果就是大〇阶。 例如，n(n-1) n2 n2 保留最高阶项 去除常数 算法效率 一 随着问题规模n的增大，函数值增长较慢的算法较优。 n=int(input()) s=(1+n)*n/2 print(s) #执行1次 #执行1次 #执行1次 算法一： 算法一是顺序结构，语句总的执行次数为3次，算法中语句的执行次数与问题规模n无关，时间复杂度为〇(1)，称为常量阶。 求 1+2+…+n的和 算法效率 一 随着问题规模n的增大，函数值增长较慢的算法较优。 n=int(input()) s=0 for i in range(1,n+1): s=s+i print(s) #执行1次 #执行1次 #执行n次 #执行n次 #执行1次 算法二： 算法二中有一重循环，语句总的执行次数为2n+3次，则算法中语句的执行次数与问题规模n呈线性增大关系，时间复杂度是〇(n)，称为线性阶。 求 1+2+…+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)等。 算法效率 一 拓展链接 常见时间复杂度的耗时比较 常见的时间复杂度耗费时间的大小关系为：〇(1)＜〇(log2n)＜〇(n)＜〇(n2)＜〇(n3)＜〇(2n)＜〇(n!)。一些常见函数的增长率,如右图所示。 常见函数的增长率 算法效率 一 一般将算法中语句的执行次数作为时间复杂度的度量标准。我们在分析时间复杂度的时候也只关注执行次数的增长次数及其常数倍。 语句总的执行次数T(n)是关于问题规模n的函数。 时间复杂度常用符号〇()表示。 输入规模 不管使用什么算法，输入规模越大，运行效率肯定会更长。 算法的平均效率、最差效率和最优效率 在输入最优情况下的算法就叫最优效率。 在输入最坏情况下的算法就叫最差效率。 增长次数 在大规模的输入情况下考虑执行次数的增长次数。 1 2 3 在分析算法的时间复杂度时，我们需要知道三个方面： 算法效率 一 算法的平均效率、最差效率和最优效率 最差效率 当输入规模为n时，算法在最坏情况下的效率。 最优效率 当输入规模为n时，算法在最优的情况下的效率。 平均效率 在实际的假设情况下，算法所可能发生的正推推断下所具有的效率。 1 2 3 一般是通过得到或者是假设各类输入的概率分布，以推导出我们所希望的基本操作次数。 算法效率 一 在以顺序查找算法为例： 算法的最差效率：n个数据，在最后一次判断才找到，效率为n。 算法的最优效率：n个数据，第一次就判断就找到，效率为1 算法的平均效率：n个数据，我们先假设能找到的概率，然后我们需要求得在第一次查找到的概率、第二次查找到的概率等等一直求，然后算得总的操作次数，得出算法的平均效率 两个经验性的规则： 最优效率的分析远远不如最差效率分析重要（因为最差效率可以确定算法运行时间的上界） 如果一个算法的最优效率都不能满足我们的要求，那么我们就可以立即抛弃它。 算法效率 一 只需知道数据之间相互链接的顺序 探讨与讨论 一 某算法的时间复杂度是〇(n),表明该算法( )。 A.问题规模是n B.问题规模与n成正比 C.执行时间等于n D.执行时间与n成正比 D 二 下列有关算法的时间复杂度的说法,错误的是( ) A.如果时间复杂度为常数,则时间复杂度为〇(0) B.仅包含顺序结构的算法的时间复杂度为〇(1) C.如果算法中语句的执行次数与问题规模n呈线性增大关系,则时间复杂度为〇(n) D.如果算法中语句的执行次数与问题规模n呈平方增大关系,则时间复杂度为〇(n2) A 数据结构对算法效率的影响率 二 数据结构与算法的关系 在计算机科学中，数据结构与算法有着密不可分的关系。解决实际问题时，数据总是以一定的组织结构关系体现并存储，数据结构的设计和选择关注的是数据的逻辑结构、存储结构以及基本操作；算法的设计和选择更多的是关注如何在数据结构的基础上综合运用各种基本操作来解决实际问题。 数据组织成不同的结构，是为了满足不同问题的需求，便于算法对数据的操作，提高孙发处理数据的效率。算法的设计和选择总是依赖于数据结构，算法设计的同时也伴随着数据结构设计，两者都是为最终解决问题服务。算法是编程思想，数据结构则是这些思想的基础。 数据结构对算法效率的影响率 二 现有一组n个数据需要存储。 第一种用数组的数据结构来存储记为n1 第二种用链表的数据结构来存储记为n2 02 01 若要对元素进行插入和删除操作，则n1的时间复杂度为〇(n)。n2的时间复杂度为〇(1)。 若要随机访问其中的一个数据，则n1的时间复杂度为〇(1)。n2的时间复杂度为〇(n)。 由此可见：数据结构的不同选择会影响算法的运行效率。 数据结构对算法效率的影响率 二 只需知道数据之间相互链接的顺序 探讨与讨论 1.用对分查找法从数列3、6、7、10、12、16、25、30、75中找到数据10的查找次数是( ) A.2 B.3 C.4 D.7 C 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") A 课堂小练 三 只需知道数据之间相互链接的顺序 探讨与讨论 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 A 小结 四 小 结 算法效率 数据结构对算法效率的影响 数据结构与 算法效率 谢谢观看 第1节 数据结构与算法效率 浙教版（2019） 选修一 $$