(
课件网) 5.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 算法效率 同一个问题可能会有不同的解决方法,也就是说可能有不同的算法,就如同“一题多解”一样。有的算法效率高一些,有的算法效率低一些。 ·算法:解决问题的方法 ·时间复杂度 反映了算法执行所需要的时间 ·空间复杂度 反映了算法执行所需要占用的存储空间 ·算法效率 算法效率的高低可由算法复杂度来度量。 算法效率 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) 定义一个或多个变量,空间复杂度都是为1 列表的空间复杂度为列表的长度 ·空间复杂度 数据结构对算法效率的影响 PART 02 数据结构对算法效率的影响 小华规划自驾游路线,出发地为杭州,目的地为北京,途径地为上海、苏州、南 ... ...