资源简介

(共16张PPT)
结
据
数
构
5.1 数据结构与算法的关系
与
算
法
问题提出
1+2+3+……+100=？
1+2+3+……+n=？(n>0)
n=int(input("你输入问题规模n:"))
s=(1+n)*n/2
print ("1+2+……+n的结果是：",str(s))
n=int(input("你输入问题规模n:"))
s=0
for i in range(1,n+1):
s=s+i
print ("1+2+……+n的结果是：",str(s))
VS
运行结果一致，算法思想等有什么差别？
顺序结构
循环结构
算法1语句执行次数共：3次
算法2语句执行次数共：2*n+3次
1次
1次
1次
1次
1次
n次
n次
1次
一、算法效率
n=int(input("你输入问题规模n:"))
s=(1+n)*n/2
print ("1+2+……+n的结果是：",str(s))
算法1: t(n)=3
n=int(input("你输入问题规模n:"))
s=0
for i in range(1,n+1):
s=s+i
print ("1+2+……+n的结果是：",str(s))
算法2: t(n)=2*n+3
导入时间模块，记录运行时间，比较算法对应程序的执行次数与执行时间的关系
import time
n=int(input("你输入问题规模n:"))
starttime = time.time()
s=(1+n)*n/2
print ("1+2+……+n的结果是：",str(s))
endtime = time.time()
dtime = endtime - starttime
print(“算法1运行时间：%.8s s" % dtime)
算法1和算法2运行次数和时间比较表
算法1t(n)=3运行时间稳定
算法2 t(n)=2*n+3运行时间与n成正比
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))
算法3: t(n)=3*n+4
1次
2次
n次
n次
n次
1次
算法3 t(n)=3*n+4运行时间与n成正比
二、算法效率的表示
时间是衡量效率的重要方面，算法执行所需要的时间用时间复杂度来反应
执行算法相应程序的时间与语句执行次数成正比（忽略其他硬软件设施）
算法执行所占用的存储空间也需要考虑，用空间复杂度来反应，硬件进步考虑较少
算法效率
时间复杂度
空间复杂度
算法的时间复杂度由程序基础语句的执行次数可推得
三、时间复杂度的大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(n2)
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))
算法6: t(n)=2*n*n+n+4
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))
算法7: t(n)=n*n+2*n+4
O(n2)
程序执行次数转换为算法时间复杂度规则：
1.只保留最高阶；2.与高阶相乘的常数去除；3.只有常数则用1取代
1次
2次
n次
n*n次
n*n次
1次
1次
2次
n次
1+2+……n次
1+2+……n次
1次
O(1)
n=int(input("你输入问题规模n:"))
s=0;c=0
if s>c:
print ("结果是：",str(s))
else:
print ("结果是：",str(c))
算法8: t(n)=5
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))
算法9: t(n)=3*n+4
O(n)
程序执行次数转换为算法时间复杂度规则：
1.只保留最高阶；2.与高阶相乘的常数去除；3.只有常数则用1取代
三、时间复杂度的大o阶记法
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阶记法
O(n3)
O(2n)
O(n!)
常见算法时间复杂度耗时比较
算法的时间复杂度在很大程度上能很好的反映出算法的优劣。
设计算法时，尽量减少循环的嵌套，减少基础语句运行次数。
算法效率
时间复杂度
空间复杂度
大O阶记法
有具体程序则看语句执行次数
关注算法的循环次数
总结
四、数据结构对算法效率的影响
数据结构的设计和选择关注：数据的逻辑结构、存储结构以及基本操作
算法的设计和选择更多关注：如何在数据结构的基础上综合运用各种基本数据操作来解决实际问题
算法和数据结构设计皆为最终解决问题服务
算法是编程思想，数据结构则是这些思想的基础
四、数据结构对算法效率的影响
数据结构 逻辑结构 存储结构 基本操作
数组 确定 连续 增、删、改、查
链表 明确的 不连续 增、删、改、查
查看第n个元素的时间复杂度 插入、删除元素时间复杂度
数组
链表
d[0]
d[1]
d[2]
d[3]
d[4]
d[5]
“赵”
“钱”
“孙”
“李”
“周”
“吴”
d[3]
“郑”
新数据插入位置
data3
null
data1
next
new
next
data2
next
O(1)
O(n)
O(n)
O(1)
实践探索
import time
n=int(input("你输入问题规模n:"))
starttime = time.time()
s=(1+n)*n/2
print ("1+2+……+n的结果是：",str(s))
endtime = time.time()
dtime = endtime - starttime
print("程序运行时间：%.8s s" % dtime)
import time
n=int(input("你输入问题规模n:"))
starttime = time.time()
s=0
for i in range(1,n+1):
s=s+i
print ("1+2+……+n的结果是：",str(s))
endtime = time.time()
dtime = endtime - starttime
print("程序运行时间：%.8s s" % dtime)
上机运行，体会程序的运行时间
观
谢
谢
看

展开更多......

收起↑