5.1数据结构与算法效率课件2024-2025学年高二上学期选择性必修1《数据与数据结构》第五章浙教版（2019）

5.1 数据结构与算法效率 《数据与数据结构》 “数学王子”高斯在9岁时，数学老师给全班同学布置了一道算术题：1+2+…+99+100=？在老师刚说完题目不久，高斯就在他的小石板上端端正正地写下了答案5050，而其它同学哪怕是算到头昏脑胀，也无法计算出正确答案。后来，高斯成为了世界著名的数学家，人们为了纪念他，也将他的这种计算方法称为“高斯定理”。 n = int(input("请输入数字n：")) s = (1+n)*n/2 print("1+2+...+n=",s) 高斯算法 n = int(input("请输入数字n：")) s = 0 for i in range(1, n+1): s += i print("1+2+...+n=",s) “其它同学”算法 语句执行3次 语句执行2n+3次 一、算法效率 导入时间模块（time），分别记录当问题规模为n时两种算法的运行时间，思考算法对应程序的执行次数与运行时间之间的关系？ 提示：time.time()返回当前时间的时间戳。 import time n = int(input("请输入数字n：")) start = time.time() s = (1+n)*n/2 print("1+2+...+n=",s) end = time.time() runTime = end-start print("高斯算法运行时间：",runTime) import time n = int(input("请输入数字n：")) start = time.time() s = 0 for i in range(1, n+1): s += i print("1+2+...+n=",s) end = time.time() runTime = end-start print("'其它同学'算法运行时间：",runTime) 语句执行3次 语句执行2n+3次 一、算法效率 T(n)=3，时间稳定 T(n)=2n+3，时间与n成正比 用T(n)来表示语句总的执行次数 一、算法效率 评价一个算法一般从4个方面进行：正确性、简单性、占用空间和运行时间。 其中最主要的是算法的占用空间和运行时间。 ①占用空间：指计算机存储器上所占用的存储空间，主要考虑算法在运行过程中临时占用的辅助空间的大小，称为空间复杂度。 ②运行时间：指一个算法在计算机上运行所花费的时间，采用时间复杂度来衡量。所谓时间复杂度是指算法中包含简单操作的次数，只要大致计算出相应的数量级即可。时间复杂度常用符号O表示，采用大O记法。 一、算法效率 算法一： 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次 s = s + i #执行n次 print(s) #执行1次 算法一是顺序结构，语句总的执行次数为3次，时间复杂度为 ? 算法二是一重循环，语句总的执行次数为2n+3次，时间复杂度为? 一、算法效率--时间复杂度的大O阶记法 T(n)=3 T(n)=2n+3 O(1) O(n) 程序执行次数转换为算法时间复杂度规则： 1.只保留最高阶；2.与高阶相乘的常数去除；3.只有常数则用1取代 常量阶 线性阶 一、算法效率--时间复杂度的大O阶记法 程序执行次数转换为算法时间复杂度规则： 1.只保留最高阶；2.与高阶相乘的常数去除；3.只有常数则用1取代 O(1) O(n) O(n2) O(log2n) O(1) O(n) O(n2) O(log2n) O(n3) O(2n) O(n!) 常见时间复杂度大小关系 时间复杂度越低 算法效率越高 < < < < < < 【练习1】某程序中执行操作次数为6次，时间复杂度为__________。 【练习2】某程序中执行操作次数为11*n+20次，时间复杂度为__________。 【练习3】某程序中执行操作次数为次，时间复杂度为__________。 【练习4】某程序中执行操作次数为int(log2n)+1次，时间复杂度为__________。 一、时间复杂度计算 n=int(input("你输入问题规模n:")) s=0;c=0 if s>c: print ("结果是：",str(s)) else: print ("结果是：",str(c)) 1次 2次 1次 算法1: T(n)=5 时间复杂度：O(1) 1次 n=int(input("你输入问题规模n:")) s=0;c=0 for i in range(1,2*n+2,2): s=s+i c=c+1 print ("1+3+……+2*n+1的结果是：",str(s)) 算法2: T(n)=3*n+4 1次 2次 n次 n次 n次 时间复杂度：O(n) 1次 for循环语句执行次数计算：（终值-初值）//步长 一、时间复杂度计算 n=int(input("你输入问题规模n:")) s=0;c=0 for i in range(1,n+1): for j in range(1,n+1): s=s+i print ("结果是：",str(s)) 1次 2次 n次 n*n次 n*n次 1次 算法4: T(n)=2*n2+n+4 时间复杂度：O(n2) 平方阶 n=int(input("你输入问题规模n:")) s=0;c=0 for i in range(1,n+1): if s>c: print ("结果是：",str(s)) else: print ("结果是：",str(c)) print ("结果是：",str(s)) 1次 2次 n次 算法3: T(n)=3*n+4 时间复杂度：O(n) n次 n次 1次 一、时间复杂度计算 n=int(input("你输入问题规模n:")) s=0;c=0 for i in range(1,n+1): for j in range(1,i+1): s=s+i print ("结果是：",str(s)) 算法5: T(n)=n2+2*n+4 1次 2次 n次 时间复杂度：O(n2) 1次 1+2+……+n次 1+2+……+n次 平方阶 一、时间复杂度计算 n=int(input("你输入问题规模n:")) s=0;i=1 while i<=n: s=s+1 i=i*2 print ("结果是：",str(s)) 1次 2次 ?次 算法6: T(n)=3*log2n+4 时间复杂度：O(log2n) ?次 1次 ?次 i=1 i=2 i=4 i=8 i=16 i=n …… 循环体执行次数： log2n 对数阶 log2n log2n log2n 一、时间复杂度计算 def fun(a,x): L,R=0,len(a)-1 while L<=R: m=(L+R)//2 if a[m]==x: return m elif a[m]<x: L=m+1 else: R=m-1 算法6: T(n)=int(log2n)+1 时间复杂度：O(log2n) 深度为k的二叉树最多查找次数为: int(log2n)+1 对分查找的最多查找次数： 第1次查找元素个数：n 第2次查找元素个数：[n/2] 第3次查找元素个数：[n/4] .............. 第x次查找元素个数：[n/ [n/] = 1 =[ log2n ]+1 一、时间复杂度的大O阶记法 算法1t(n)=3运行时间稳定 算法2 t(n)=2*n+3运行时间与n成正比 算法3 t(n)=3*n+4运行时间与n成正比 O(1) O(n) O(n) 算法4 t(n)=n2+5运行时间与n成正比 O(n2) 算法5 t(n)=3*n2+5运行时间与n成正比 O(n2) 常数阶 线性阶 线性阶 平方阶 平方阶 一、时间复杂度的大O阶记法 O(1) O(n) O(n2) O(log2n) O(n3) O(2n) O(n!) 常见算法时间复杂度耗时比较 算法的时间复杂度在很大程度上能很好的反映出算法的优劣。 设计算法时，尽量减少循环的嵌套，减少基础语句运行次数。 现有10000种商品信息，为便于后期的查找定位需要，采用何种数据结构存储这些信息效率更高？若是需要频繁添加或删除信息，又该采用何种数据结构？ 数据结构 查找指定元素 时间复杂度 删除或者添加元素 时间复杂度 数组 链表 二、数据结构对算法效率的影响 ①数组元素插入 ②数组元素删除 ①链表元素插入 ②链表元素删除 数据结构 查找指定元素 时间复杂度 删除或者添加元素 时间复杂度 数组 链表 O(1) O(1) O(n) O(n) 二、数据结构对算法效率的影响 ②对元素做插入、删除操作，那么数据结构采用链表比较合适，这是因为在数组中插入或删除一个元素都可能引起大量元素的移动操作，时间复杂度O(n)；而在链表中插入或删除一个节点，只需要对个别节点的指针域进行修改，时间复杂度为O(1)。 ①对元素做查找操作，那么数据结构采用数组比较合适，这是因为在数组中查找一个元素可以通过下标直接找到这个元素，时间复杂度O(1)；而在链表中查找一个节点必须从头指针进入，依照先后顺序查找到该节点，时间复杂度为O(n)。 三、课堂总结 算法效率 时间复杂度 空间复杂度 大O阶记法 有具体程序则看语句执行次数 关注算法的循环次数 $$