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

5.1数据结构与算法效率 1 算法效率 第一天往钱罐子里面投入1元，存钱罐总金额为1元 第二天往钱罐里面投入2元，存钱罐总金额为3元 第三天往存钱罐里面投入3元，存钱罐里面总金额为6元 那么第n天时存钱罐里面一共有多少钱？ #算法1（顺序结构） s1=0 n=int(input("存钱天数：")) s1=(1+n)*n/2 print("存钱罐的钱数：", s1) #算法2（循环结构） n=int(input("存钱天数：")) s2=0 for i in range(1,n+1): s2=s2+i print("存钱罐的钱数：",s2) 思考：所有语句的总执行次数是多少？哪一种方法更好？ 算法1语句执行次数共：4次 算法2语句执行次数共：2*n+3次 1次 1次 1次 1次 1次 n次 n次 1次 1次 算法效率 PART 01 3 算法效率 同一个问题可能会有不同的解决方法，也就是说可能有不同的算法，就如同“一题多解”一样。有的算法效率高一些，有的算法效率低一些。 ·算法：解决问题的方法 ·时间复杂度 反映了算法执行所需要的时间 ·空间复杂度 反映了算法执行所需要占用的存储空间 ·算法效率 算法效率的高低可由算法复杂度来度量。 算法效率 1.用常数1取代运行时间中的所有加法常数。 2.在修改后的运行次数函数中，只保留最高阶项。 3.如果最高阶项存在且不是1，那么去除与这个项相乘的常数。得到的结果就是大O阶。 例如：T(n)=n(n-1)的量级与n2相同，其时间复杂度可表示成O(n2)。 语句总的执行次数T(n) 用O()来体现算法时间复杂度，称之为大O记法。其推到过程如下 ·时间复杂度 算法效率 时间复杂度：O( ) 时间复杂度：O( ) #算法1（顺序结构） s1=0 n=int(input("存钱天数：")) s1=(1+n)*n/2 print("存钱罐的钱数：", s1) #算法2（循环结构） n=int(input("存钱天数：")) s2=0 for i in range(1,n+1): s2=s2+i print("存钱罐的钱数：",s2) 任务一：请计算下列程序的时间复杂度 1 n 算法1语句总执行次数：T(n)=4 O(1) 常数阶 算法2语句总执行次数：T(n)=2*n+3 O(n) 线性阶 1次 1次 1次 1次 1次 n次 n次 1次 1次 算法效率 时间复杂度：O( ) 时间复杂度：O( ) #算法3 n=int(input()) s3=0 for i in range(1,n+1): for j in range(1,n+1): s3=s3+j print(s3) #算法4 n=int(input()) s4=0;i=1 while i<=n: s4=s4+1 i=i*2 print (s4) n2 log2n 1次 n次 1次 1次 1次 log2n 次 1次 1次 n*n次 n*n次 算法3语句总执行次数：T(n)=2*n2+n+3 O(n2) 平方阶 算法4语句总执行次数：T(n)=3*log2n+3 O(log2n) 对数阶 log2n 次 log2n 次 任务一：请计算下列程序的时间复杂度 算法效率 任务一：请计算下列程序的时间复杂度 O(log2n) n=int(input("你输入问题规模n:")) s=0;i=1 while i<=n: s=s+1 i=i*2 print ("结果是：",str(s)) 算法10: 关注循环体执行次数即可 i=1 i=2 i=4 i=8 i=16 i=n …… 循环体执行次数： log2n 对数阶 算法效率 O(1) O(n) O(n2) O(log2n) O(n3) O(2n) O(n!) 算法的时间复杂度在很大程度上能很好的反映出算法的优劣。 设计算法时，尽量减少循环的嵌套，减少基础语句运行次数。 ·常见复杂度的耗时比较： 关注最内层循环体执行次数即可 算法效率 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如： s=[0]*100 for i in range(0,100): temp = i 定义了有100个元素的数组，所以空间复杂度100*O(1) temp=0 for i in range(1,n+1): temp = i 定义了一个temp，所以空间复杂度1*O(1) 定义一个或多个变