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

(共16张PPT)
5.1 数据结构与算法效率
一个人想要喝茶，但当时的情况是：开水没有，水壶要洗，茶壶和茶杯要洗；火已经生了，茶叶也有了怎么办？
泡茶
甲：
洗开水壶 灌凉水 洗茶壶 洗茶杯 拿茶叶 泡茶喝
烧开水
乙：
洗开水壶 洗茶壶 洗茶杯 拿茶叶 灌凉水 烧开水 泡茶喝
丙：
洗开水壶 灌凉水 烧开水 拿茶叶 洗茶壶 洗茶杯 泡茶喝
在计算机科学中，数据结构与算法有着密不可分的关系。解决实际问题
时，数据总是以一定的组织结构关系体现并存储，数据结构的设计和选
择关注的是数据的逻辑结构、存储结构以及基本操作；算法的设计和选
择更多的是关注如何在数据结构的基础上综合运用各种基本数据操作来
解决实际问题。
因此，算法的设计和选择总是依赖于数据结构，算法设计的同时也伴随
着数据结构的设计，两者都是为最终解决问题服务。同时，数据结构的
设计和选择会对算法效率产生一定的影响。
算法效率
同一个问题可能会有不同的解决方法，也就是说可能有不同的算法。
有的算法效率高一些，有的算法效率低一些。通常，算法效率的高低
可由算法复杂度来度量。
算法复杂度又分为算法的时间复杂度和空间复杂度，其中时间复杂度
反映了算法执行所需要的时间，而空间复杂度反映了算法执行所需要
占用的存储空间。
算法运行需要的时间，一般将算法中语句的执行次数作为时间复杂度的
度量标准。语句总的执行次数T（n）是关于问题规模n的函数。
所谓问题规模（也称为输入的大小）是指处理问题的大小，即用来衡量
输入数据量的整数。
1
2
3
4
5
6
7
8
9
10
…
…
…
n
在约瑟夫问题中，用数组或链表中元素的个数作为问题规模。
时间复杂度常用符号O表示，不包括T(n)函数的低阶项和首项系数，
如n(n-1)的量级与n2相同，其时间复杂度可表示成O(n2)。
用O()来体现算法时间复杂度，称之为大O记法。
通常，随着问题规模n的增大，函数值增长较慢的算法较优。
例如，求1+2+…+n的和可以用以下两种算法来实现：
算法一：
n=int(input()) #执行1次
s=(1+n)*n/2 #执行1次
print(s) #执行1次
算法二：
n=int(input()) #执行1次
s=0 #执行1次
for i in range(1,n+1): #执行n次
s=s+i #执行n次
print(s) #执行1次
时间复杂度为O(1)，常量阶
时间复杂度为O(n) 线性阶
再来看下面的例子：
n=int(input())
s=0
x=0
for i in range(1,n+1):
for j in range(1,n+1):
x=x+1 #执行n*n次
s=s+x
print(s)
时间复杂度是O(n2)，称为平方阶。
此外，算法的时间复杂度还有对数阶O()、指数阶O(2n)等。
算法的时间复杂度反映了程序执行时间随问题规模增长而增长的量级，
在很大程度上能很好地反映出算法的优劣。
举例说明空间复杂度是如何度量的。
程序运行过程中，一般将所占用的辅助存储空间大小作为度量算法空间
复杂度的标准。一个算法在计算机存储器上占用的存储空间，主要包括
程序代码占用的空间，输入或输出数据占用的空间，以及额外辅助程序
运行占用的存储空间这三个方面。输入或输出数据占用的空间是必须的，
程序代码占用的空间可以通过精简代码来实现，但非常有限。由于算法
设计的差异，算法运行过程中的辅助空间相差较大，因此是衡量算法空
间复杂度的关键因素。例如，算法中需要处理一个数据规模为n的连续
整数数组，则其空间复杂度至少为O(n)。
数据结构对算法效率的影响
数据组织成不同的结构，是为了满足不同问题的需求，便于算法对数据
的操作，提高算法处理数据的效率。
例1：要显示10000种商品中某个商品的价格
在设计数据结构时，可以将这10000中商品的价格数据采用数组或链表
来组织。但从算法效率的角度考虑，此时数据结构采用数组比链表更方
便，这是因为数组中的元素可以按其下标方便地被随机访问，时间复杂
度为O(1)；而在链表中访问任何节点都必须从首节点（或尾节点）开始
按序访问到指定节点，时间复杂度为O(n)。
例2：要在10000种商品中添加或删除某个商品信息
算法需要对元素做插入、删除操作，那么数据结构采用链表比较合适，
这是因为在数组中插入或删除一个元素都可能引起大量元素的移动操作，
时间复杂度为O(n)；而在链表中插入或删除一个节点只需要对个别节点
的链域进行修改，时间复杂度为O(1)。
因此，数据结构的不同选择会影响算法的运行效率。
练一练
1.某算法的部分流程图如下：
输入a
a<5
b Abs(a)
Y
a>10
N
Y
b Sqr(a)/2
N
b a/2
输出b
其算法的时间复杂度是（ ）
A.常量阶 B.线性阶
C.指数阶 D.对数阶
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
3.下列四个常见的时间复杂度之间的大小关系正确的是（ ）
A.O()B.O()C. O(1)< O()D. O(1)C
谢 谢