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

(共18张PPT)
5.1 数据结构与算法效率
数据结构概念及类型
常见类型：数组、链表、队列、栈、树和图等
数据结构指的是数据之间的相互关系，即数据组织形式。包括：
逻辑结构、存储结构、基本操作（数据运算）
对算法效率产生一定的影响
各有特点
5.1 数据结构与算法效率
5.1.1 算法效率
时间复杂度
空间复杂度
算法复杂度
学习任务
通过阅读书本116页5.1.1
1、认识： “时间复杂度”、“空间复杂度”
2、回答下面问题
思考并回答
下面两个算法，哪一个的时间复杂度更大
n=int(input())
s=(1+n)*n/2
print (s)
n=int(input())
s=0
for i in range(1,n+1):
s=s+i
print (s)
时间复杂度与渐近时间复杂度
时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数，T(n)
渐进时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级,O(n)
当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。
不包括T(n)函数的低阶项和首项系数
？
时间复杂度与渐近时间复杂度
n=int(input())
s=(1+n)*n/2
print (s)
N趋近于无穷大时，程序仍然只执行三次，是一个定值，用常数1代替运行时间中所有加法常数
O(1)
n=int(input())
s=0
for i in range(1,n+1):
s=s+i
print (s)
N趋近于无穷大时，2*n+3中的3可以省略，而两倍的影响也将减小
如果最高阶项存在且不是1，那么去除与这个项相乘的常数
O(n)
练一练
请计算下面算法的时间复杂度O()
n=int(input())
s=0
for i in range(1,4):
for j in range(1,n+1):
s=s+i
print (s)
n=int(input())
s=0
for i in range(1,n+1):
for j in range(1,n+1):
s=s+i
print (s)
空间复杂度
空间复杂度(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
列表的空间复杂度为列表的长度
空间复杂度
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如：
a = ”Python” # 空间复杂度为1
num = [1, 2, 3, 4, 5] # 空间复杂度为5
num = [[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]] # 空间复杂度为5*4
num = [[[1, 2], [1, 2]], [[1, 2], [1, 2]] , [[1, 2], [1, 2]]] # 空间复杂度为3*2*2
空间复杂度
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如：
def fac(n):
if n==0:
s=1
else:
s=n*fac(n-1)
return s
递归算法通过反复调用，创建了多个临时存储空间，其空间复杂度O(n)
5.1 数据结构与算法效率
5.1.2 数据结构对算法效率的影响
算法复杂度
效率
学习任务
通过阅读书本118页5.1.2
1、认识： 算法复杂度对效率的影响
2、描述数据结构特点（如：数组、链表）
3、回答下面问题
求解三角形面积
数组与链表的数据结构特点
2
数据结构 逻辑结构 存储结构 基本操作
数组 确定 连续 增、删、改、查
链表 明确的 不连续 增、删、改、查
head
查看第n个元素的时间复杂度 插入、删除元素时间复杂度
数组 O(1) O(n)
链表 O(n) O(1)
移动
具体如何度量某个算法的效率高低
3
具体算法具体分析
数据量、数据结构（逻辑结构、存储结构、基本操作）、……
学习体验
import time
s = 0 #执行1次
n = 10 ** 4
#n=int(input("请输入n值体验时间复杂度："))
#程序二
s = 0
start = time.time()
print("正在计算中,可以改变n的值体验时间长短")
for i in range(1,n + 1): #执行n次
for j in range(1,n + 1):
s = s + 1 #执行n * n次
print(s)
end = time.time()
print(end - start)
#程序一
start = time.time()
for i in range(1,n + 1): #执行n次
s = s + 1 #执行n次
print(s)
end = time.time()
print(end - start)
作业
AB练5.1的A