资源简介

(共16张PPT)
一个人想要喝茶，但当时的情况是：开水没有，水壶要洗，茶壶和茶杯要洗；火已经生了，茶叶也有了怎么办？
甲：
洗开水壶 灌凉水 洗茶壶 洗茶杯 拿茶叶 泡茶喝
烧开水
乙：
洗开水壶 洗茶壶 洗茶杯 拿茶叶 灌凉水 烧开水 泡茶喝
丙：
洗开水壶 灌凉水 烧开水 拿茶叶 洗茶壶 洗茶杯 泡茶喝
CHZX
5.1 数据结构与算法效率
浙江省高中信息技术 选择性必修一 《数据与数据结构》
算法效率
时间复杂度
空间复杂度
01
算法效率
suanfaxiaolv
同一个问题可能会有不同的解决方法，也就是说可能有不同的算法。
有的算法效率高一些，有的算法效率低一些。通常，算法效率的高低
可由算法复杂度来度量。
算法复杂度又分为算法的时间复杂度和空间复杂度，其中时间复杂度反映了算法执行所需要的时间，而空间复杂度反映了算法执行所需要占用的存储空间。
算法效率
suanfaxiaolv
算法运行需要的时间，一般将算法中语句的执行次数作为时间复杂度的度量标准。语句总的执行次数T（n）是关于问题规模n的函数。
所谓问题规模（也称为输入的大小）是指处理问题的大小，即用来衡量输入数据量的整数。
1
2
3
4
5
6
7
8
9
10
…
…
…
n
在约瑟夫问题中，用数组或链表中元素的个数作为问题规模。
时间复杂度
算法效率
suanfaxiaolv
时间复杂度常用符号O表示，不包括T(n)函数的低阶项和首项系数，
如n(n-1)的量级与n2相同，其时间复杂度可表示成O(n2)。
用O()来体现算法时间复杂度，称之为大O记法。
时间复杂度
算法效率
suanfaxiaolv
通常，随着问题规模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) 线性阶
时间复杂度
算法效率
suanfaxiaolv
时间复杂度
再来看下面的例子：
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)，称为平方阶。
算法效率
suanfaxiaolv
时间复杂度
算法效率
suanfaxiaolv
空间复杂度
程序运行过程中，一般将所占用的辅助存储空间大小作为度量算法空间复杂度的标准。一个算法在计算机存储器上占用的存储空间，主要包括程序代码占用的空间，输入或输出数据占用的空间，以及额外辅助程序运行占用的存储空间这三个方面。输入或输出数据占用的空间是必须的，程序代码占用的空间可以通过精简代码来实现，但非常有限。由于算法设计的差异，算法运行过程中的辅助空间相差较大，因此是衡量算法空间复杂度的关键因素。例如，算法中需要处理一个数据规模为n的连续整数数组，则其空间复杂度至少为O(n)。
数据结构对算法效率的影响
02
数据结构对算法效率的影响
Shujujiegou dui suanfaxiaolv de yingxiang
求解三角形面积
数据结构 逻辑结构 存储结构 基本操作
数组 确定 连续 增、删、改、查
链表 明确的 不连续 增、删、改、查
head
查看第n个元素的时间复杂度 插入、删除元素时间复杂度
数组 O(1) O(n)
链表 O(n) O(1)
移动
数据结构对算法效率的影响
Shujujiegou dui suanfaxiaolv de yingxiang
O(1)
O(n)
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

展开更多......

收起↑