资源简介

(共19张PPT)
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
数据结构对算法效率的影响
小华规划自驾游路线，出发地为杭州，目的地为北京，途径地为上海、苏州、南京、济南、石家庄。用数组来实现其更改过程。
(1)小华想要查询第5个到达的城市，如何编程实现_______时间复杂度为______
(2)小华计划有变决定直接从上海出发，不从杭州出发，如何编程实现 时间复杂度为？
a=["杭州","上海","苏州","南京","济南","石家庄","北京"]
n=len(a)
q=0
for i in range(q,n-1):
________________
a.pop()
print(a)
a[i]=a[i+1]
a[4]
O(1)
O(n)
数据结构对算法效率的影响
小华规划自驾游路线，出发地为杭州，目的地为北京，途径地为上海、苏州、南京、济南、石家庄。用链表来实现其更改过程。
(1)小华想要查询第5个到达的城市，如何编程实现 时间复杂度为
b=[["杭州",2],["苏州",3],["上海",1],["南京",5],["北京",-1],["济南",6],["石家庄",4]]
head=0
k=head
m=1
while m<5:
____________
m=m+1
print(b[k][0])
k=b[k][1]
O(n)
(2)小华计划有变决定直接从上海出发，不从杭州出发，如何编程实现 时间复杂度为？
b=[["杭州",2],["苏州",3],["上海",1],["南京",5],["北京",-1],["济南",6],["石家庄",4]]
head=0
_________________
head=b[head][1]
O(1)
数据结构对算法效率的影响
数据结构 逻辑结构 存储结构 基本操作
数组 确定 连续 增、删、改、查
链表 明确的 不连续 增、删、改、查
查看第n个元素的 时间复杂度 插入、删除元素
时间复杂度
数组
链表
O(1)
O(n)
O(n)
O(1)
课堂小结
时间复杂度
空间复杂度
数据结构
影响
不同算法
不同的算法效率
具有
练一练
1.某算法的部分流程图如下，其时间复杂度为（ ）
A.常量阶 B.线性阶
C.指数阶 D.对数阶
输入a
a<5
b abs(a)
Y
a>10
N
Y
b sqrt(a)/2
N
b a/2
输出b
A
练一练
2.分析如下Python程序段，其算法时间复杂度是（ ）
s=input()
slen=len(s)
number={'0':0,'1':0,'2':0,'3':0,'4':0,'5':0,'6':0,'7':0,'8':0,'9':0}
for i in range(slen):
if (s[i]>='0'and s[i]<='9'):
number[s[i]]=number[s[i]]+1
A.O(1) B.O(n) C.O(n2) D.O()
B
算法效率
时间复杂度：O( )
n=int(input())
flag=True
for i in range(2,______):
if n%i==0:
flag=False
if flag==True:
print("是质数")
else:
print("不是质数")
print("循环次数：",m)
编程实现判断一个数是不是质数，并计算该程序的时间复杂度
n
n
THANK YOU
Speaker :wps powerpoint

展开更多......

收起↑