资源简介

(共17张PPT)
一、 数据结构与算法效率
第五章　数据结构与算法
知识过关
1. 数据结构与算法
(1)数据总是以一定的组织结构关系体现并存储。
(2)数据结构的设计和选择关注的是数据的逻辑结构、存储结构以及基本操作。
(3)算法的设计和选择总是依赖于数据结构。
(4)算法是编程思想,数据结构是这些思想的基础。
2. 算法效率
(1)算法效率。
算法效率的高低可由算法的复杂度来衡量。算法复杂度又分为算法的时间复杂度和空间复杂度,其中时间复杂度反映了算法执行所需要的时间,而空间复杂度反映了算法执行所需要占用的存储空间。
(2)时间复杂度(用大O阶表示)。
时间复杂度常用符号O表示,不包括低阶项和首项系数。时间复杂度从低到高可以分为常量阶O(1)、对数阶O(log2n)、线性阶O(n)、平方阶O(n2)等。算法的时间复杂度在很大程度上能很好地反映出算法的优劣。
(3)推导大O阶的方法。
①用常数1取代运行时间中的所有加法常数。
②对于修改后的运行次数函数,只保留最高阶项。
③如果最高阶项存在且不是1,那么去除与这个项相乘的常数。
例如,算式:5n2+2n+3 ,其大O阶推导过程如下:
5n2+2n+3(用常数1取代加法常数)→5n2+2n+3(保留高阶)→5n2(去除高阶相乘常数)→n2
因此,该算式的大O阶(时间复杂度)结果为O(n2)。
一般而言,时间复杂度耗费时间的大小排序如下:
常数阶 O(1)<对数阶O(log2n)<线性阶 O(n)<线性对数阶 O(nlog2n)<平方阶 O(n2)<立方阶 O(n3)<指数阶 O(2n)……
3. 数据结构对算法效率的影响
数据组织成不同的结构,是为了满足不同问题的需求,便于算法对数据结构的操作。对于不同的问题,我们可以根据问题的特性选择数组、链表、字符串、栈、队列和二叉树等数据结构来组织数据,提高算法处理数据的效率。
4. 算法优化
【例题】用Python编写程序,解决“百钱百鸡”问题。已知一只公鸡值五钱,一只母鸡值三钱,三只小鸡值一钱。买100只鸡共花了100钱,问:公鸡、母鸡、小鸡的数量各是多少
算法分析:常规思路是假设i、j、k分别代表公鸡、母鸡和小鸡,结合题意可知,变量的范围分别是:i的范围是0~20,j的范围是0~33,k的范围是0~100。利用枚举算法,使用三重循环，程序如代码1所示,运行结果如下。
代码1(未经优化的三重循环结构):
for i in range(21):
　　for j in range(34):
　　　　for k in range(101):
　　　　　　if i+j+k==100 and i*5+j*3+k//3==100:
　　　　　　　　print(i,j,k)
代码2(根据题意,将三重循环改为两重循环,结果相同,但效率显著提升):
for i in range(21):
　　for j in range(34):
　　　　k=100－i－j
　　　　if i*5+j*3+k//3==100:
　　　　　　print(i,j,k)
由此可见,代码1的时间复杂度是O(n3),而代码2的时间复杂度为O(n2),算法效率大增。
继续优化算法,将方程i+j+k=100,以及i*5+j*3+k/3=100,进行消元(消去i),得到方程组:j=25－7*j//4;k=75+3*j//4,然后考虑变量大于等于0,且必须是整数,优化后得到的一重循环的代码3:
for i in range(21):
　　j=25－7*i//4
　　k=75+3*i//4
　　if i*5+j*3+k//3==100 and j>=0 and k%3==0:
　　　　　　print(i,j,k)
可见,代码3的时间复杂度为O(n),和前面的代码相比,效率大大提高。
典例精选
【例1】 线性表一般有两种存储结构,顺序存储结构和链表存储结构。现在对这两种存储结构进行操作,关于相应操作的运行效率,下列说法中正确的是(　　)
A. 读取操作时，顺序存储结构的运行效率要低于链表存储结构
B. 插入操作时，顺序存储结构的运行效率要高于链表存储结构
C. 删除操作时，顺序存储结构的运行效率要低于链表存储结构
D. 链表存储结构的各项操作运行效率均高于顺序存储结构
【解析】 删除、插入数据操作时，由于顺序存储结构需要移动大量数据,因此其运行效率要低于链表存储结构。而读取时，由于链表存储必须从头节点开始,因此顺序存储结构的运行效率要高于链表存储结构。C正确。
C
【例2】 有如下Python程序段:
n=int(input())
s=0
for i in range(1,n+1):
　　s+=i
print(s)
上述程序的时间复杂度为(　　)
A. O(1) B. O(log2n)
C. O(n) D. O(n2)
【解析】 本题算法中实现的功能是求1+2+3+…+n的和,其执行次数显然与问题规模n呈线性增长关系,因此其时间复杂度为O(n),C正确。
C
【例3】 以下两个程序段的功能相同,实现的功能是删除列表a(元素个数为n)中的重复元素(只保留一个),并将剩下的元素降序输出。
# 程序段①
# 对列表a进行降序排序,代码略
i=1
while i　　if a[i]=a[i－1]:
　　　　for j in range(i+1,n):
　　　　　　a[j－1]=a[j]
　　　　 ;n－=1
　　i+=1
# 输出列表元素a[0]到a[n－1],代码略 # 程序段②
max_num=max(a)#求出列表a中的最大值max_num
b=[0]*(max_num+1)
for i in range(0,n):
　　b[a[i]]+=1
:
　　if b[i]>0:
　　　　print(i,end=" ")
i－=1
for i in range(max_num,0,－1)
下列关于上述两个程序段及其功能的说法,正确的是(　　)
A. 同样的数据规模,两个程序段的运行时间效率一样
B. 程序段①加框处语句是否执行不受列表a原数据的影响
C. 程序段②加框处语句修改为“for i in range(1,max_num+1)”,输出结果不变
D. 在实现该功能的过程中,程序段②比程序段①需要更多的存储空间
【解析】 本题考查算法效率。程序段①时间复杂度为O(n2),程序段②时间复杂度为O(n),两个程序段的时间效率不同,A错误。程序段①中的加框处语句不能删除,否则若出现连续3个及以上的重复数字会出问题,B错误。程序段②加框处语句修改为“for i in range(1,max_num+1)”会导致最后结果升序输出,C错误。程序段②中需要预设一个长度为max_num的列表,会占用更多空间,D正确。
D
自我检测
1. 下列关于算法的时间复杂度的说法,错. 误. 的是 (　　)
A. 如果时间复杂度为常数,那么时间复杂度为O(0)
B. 仅包含顺序结构的算法的时间复杂度为O(1)
C. 若算法中语句执行次数与问题规模n呈线性增大关系,则时间复杂度为O(n)
D. 若算法中语句执行次数与问题规模n呈平方增大关系,则时间复杂度为O(n2)
【解析】 如果时间复杂度为常数,则其时间复杂度为O(1),A符合题意。
A
2. 下面程序段的时间复杂度是(　　)
c = 0
n = int(input())
for i in range(1, n+1):
　　for j in range(1, i+1):
　　　　c += 1
　　print(c)
A. Ο(1) B. Ο(n)
C. Ο(n2) D. Ο(log2n)
【解析】 本题考查对算法时间复杂度的判断。该程序段中包含二重循环,i从1到n,每次都让j循环i次,循环体为语句“c+=1”,其执行次数为n2次。则算法中语句的执行次数与问题规模n呈平方增大关系,因此时间复杂度为O(n2),C正确。
C
3. 下面这段Python代码的时间复杂度是(　　)
for i in range(n):
　　for j in range(n, i, －1):
　　　　if a[j] > a[j－1]:
　　　　　　a[j],a[j－1] = a[j－1],a[j－1]
A. O(1) B. O(log2n)
C. O(n) D. O(n2)
【解析】 由于该程序采用两重循环结构,故时间复杂度为O(n2),D正确。
D

展开更多......

收起↑