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

数据结构与算法效率 1 情境导入 高斯是一位杰出的天文学家、数学家和物理学家。传说在他还是个小孩子的时候，有一次数学课上，老师布置了一道特别繁琐的加法题：计算从1加到100的总和。其他学生都在一步一步地计算，1+2=3，3+3=6，6+4=10，而年幼的高斯不一会儿就报告了答案——5050。数学老师很惊讶，高斯居然可以在这么短的时间内算出正确答案。 效率 2 算法效率 算法效率的高低可由算法复杂度来度量。 时间复杂度： 反映了算法执行所需要的时间 空间复杂度： 反映了算法执行所需要占用的存储空间 3 活动：测量运行时间 对算法进行实际运行测试，获得真实的运行时间。可以通过Python的time模块，记录算法开始前和结束后的系统时间，其差值就是运行时间。 import time start = time.time() #在此处添加需要执行的程序 end = time.time() print("%.10f" %(end-start)) #算法开始前的系统时间 #算法结束后的系统时间 #计算差值并保留10位小数 4 活动：测量运行时间 def sum1(n): sum = 0 for i in range(1,n+1): sum = sum+i return sum 算法1（其他同学计算方法） def sum2(n): sum = n*(n+1)/2 return sum 算法2（高斯计算方法） 1.连续运行算法1和算法2五次，并记录每次运行时间。 2.改变变量n的值，观察运行时间的变化情况。 5 对比得到的数据，可以观察出什么结论？ 第1次 第2次 第3次 第4次 第5次 n= 10000 4.3×10-4 4.6×10-4 2.7×10-4 2.7×10-4 2.7×10-4 n= 100000 3.4×10-3 3.1×10-3 3.1×10-3 3.0×10-3 3.0×10-3 n= 1000000 3.2×10-2 3.1×10-2 3.0×10-2 3.1×10-2 3.0×10-2 第1次 第2次 第3次 第4次 第5次 n= 10000 2.1×10-6 0.9×10-6 0 0 0 n= 100000 0 0 0.9×10-6 0 0 n= 1000000 0 0 0.9×10-6 0 0 算法1 算法2 6 同一个算法，不同计算机设备运行时间会不相同，除此之外，用不同编程语言编写同一个算法，得到的运行时间也会不相同。这都是外部环境对算法运行时间的影响。不仅如此，有些算法无法先运行，事后统计运行时间，比如导弹控制算法。所以单纯的用执行时间来评估算法效率是不妥当的。 超级计算机 单片机 三张图均为AI生成 模拟导弹控制情境 7 我们要找一种不需要运行程序，且与外界因素无关的度量指标来评估算法的执行时间。 代码 语句 一段代码 的执行时间 每条语句 执行时间的总和 一条语句 执行时间相同 语句的 总执行次数 8 def sum1(n): sum = 0 for i in range(1,n+1): sum = sum+i return sum 语句总执行次数 ① ② ③ ④ #执行1次 #执行n次 #执行n次 #执行1次 算法1（其他同学计算方法） 9 问题规模 指处理问题的大小。问题规模是影响算法执行时间的主要因素 def sum1(n): sum = 0 for i in range(1,n+1): sum = sum+i return sum 算法1（其他同学计算方法） def sum2(n): sum = n*(n+1)/2 return sum 算法2（高斯计算方法） ① ② ① ② ③ ④ 语句总执行次数 10 = 可以看出，对起主导作用的部分是。我们保留主导部分，去除其他低价项得到的结果称作“大O记法”，记作。函数为函数中起主导的部分提供了简单的表示。 时间复杂度是 大O记法 11 大O记法 推导大O阶的方法： 1.用常数1取代运行时间中的所有加法常数。 2.在修改后的运行次数函数中，只保留最高阶项。 3.如果最高阶项存在且不是1,那么去除与这个项相乘的常数。得到的结果就是大O阶。 保留最高阶项 去除常数 12 小试牛刀 例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) 13 小试牛刀 例2.该程序的时间复杂度是： def f(n): s = 0 i = 1 while i < = n : s = s + i i = i * 2 return s print(f(4)) 关注循环执行次数 第1次 第2次 第3次 . . . . . . 第次 第次 执行次数： k < log2n 时间复杂度是 ×2 ×2 ×2 ×2 ×2 14 sum = sum+i 算法1 x = x + 1 s = s + x 例1 while i <= n : s = s + i 例2 问题1: 如果问题规模 相同，比较三段程序的时间复杂度。 < < i = i * 2 for i in range(1,n+1): for i in range(1,n+1): for j in range(1,n+1): i = i +1 15 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 问题2: 在将三段代码拼接后，新代码段的时间复杂度是多少？ 时间复杂度是 16 常见时间复杂度耗时比较 在分析算法效率的过程中，为了判断哪一项是起主导作用的，需要了解常见函数中n变大的情况下的差异性，下图展示了常见函数的增长情况。 常数阶 对数阶 线性阶 对数线性阶 平方阶 立法阶 指数阶 阶乘阶 此图原创 17 【思考】未来在设计算法的时候如何降低时间复杂度。 算法的时间复杂度反映了程序执行时间随问题规模增长而增长的量级，在很大程度上能很好地反映出算法的优劣。 18 【思考】未来在设计算法的时候如何降低时间复杂度。 设计算法时，尽量减少循环的嵌套。 调用函数减少重复计算。 算法的时间复杂度反映了程序执行时间随问题规模增长而增长的量级，在很大程度上能很好地反映出算法的优劣。 19 程序=数据结构+算法 20 数据结构对算法效率的影响 数组 链表 访问 通过下标获取数据 时间复杂度：________ 需要从头结点遍历寻找，直到找到目标节点 时间复杂度：_______ 如果需要频繁地访问数据元素，则优先选择数组。 数组访问 链表访问 以我们曾经学习过的数组和链表为例，回忆元素访问、插入、删除方面的效率差异，并完成下列表格： 21 数组 链表 插入、删除 需要移动大量数组元素以保持数组的连续性 时间复杂度：________ 只要找出某个结点位置，直接改变指针 时间复杂度：________ 数组插入 数组删除 数据结构对算法效率的影响 22 如果需要频繁地执行插入删除操作，则优先选择链表。 链表插入 链表删除 数组 链表 插入、删除 需要移动大量数组元素以保持数组的连续性 时间复杂度：________ 只要找出某个结点位置，直接改变指针 时间复杂度：________ 数据结构对算法效率的影响 23 【思考】算法效率在生活中哪些方面发挥着作用呢？ 24 【思考】算法效率在生活中哪些方面发挥着作用呢？ 交通导航 人脸识别 25 【思考】算法效率在生活中哪些方面发挥着作用呢？ 人脸识别 交通导航 26 课堂小结 27 $$