资源简介

(共20张PPT)
5.1 数据结构与算法效率
册 别：选择性必修1
学 科：高中信息技术（浙教版）
学习目标：
能理解数据结构与算法的关系。
能认识算法效率高低的主要的两个方面：时间复杂度与空间复杂度，及这两个方面的表示与计算。
能通过具体的实例分析算法的效率。
逐步自觉将算法的效率应用在算法程序设计中，根据问题选择合适的数据结构，提高算法效率。
能通过具体的实例认识算法效率的重要性。
情境导入
Google实验
搜索引擎是互联网上的检索技术，它能提高人们获取搜集信息的速度，为人们提供更好的网络使用环境，Google做过一个试验，显示10条搜索结果的页面载入需要0.4秒，显示30条搜索结果的页面载入需要0.9秒，结果后者使得Google总的流量和收入减少了20%。Google地图上线的时候，首页大小有100KB，后来下降到70~80KB。结果，流量在第一个星期上升了10%，接下来的3个星期又再上升了25%。 Amazon（亚马逊公司）的统计也显示了相近的结果，首页打开时间每增加100毫秒，网站销售量会减少1%。
资料来源：互联网
算法+数据结构=程序
算法：解析法、枚举法、递归、迭代、排序、查找等
数据结构：数组、链表、队列、栈、字符串、树等
著名的计算机科学家、图灵奖获得者尼克劳斯 沃思（Niklaus Wirth）指出
（Algorithm+Data Structures=Programs）
算法依赖数据结构，算法与数据结构为程序服务，达成问题解决
算法效率重要性分析
智慧农场监测系统、气象预报程序必须在指定时间前完成。如果不能按时计算出预报结果，这个算法有价值吗？
入口处的红外测温、人脸识别程序，必须在几分之一秒内完成工作。过慢的算法会带来糟糕的用户体验，这样的设备有可能广泛采用吗？
实例分析：
“数学王子”高斯小时候，老师给从未上过算术课的同学们布置了一道题目：1+2+3+……+100=？
其他同学在仔细算题时，高斯快速巧妙地解决了问题，老师对他刮目相看。他的算法被称为“高斯算法”。
源于教材P116例子
算法效率分析
算法的效率
时间复杂度
空间复杂度
指该算法的时间耗费，是该算法中基本操作重复执行的次数与问题规模n的某个函数。
指该算法执行所需要占用的存储空间。
（主要指临时占用内存空间）
算法效率分析:高斯算法
时间复杂度
n=int(input())
s=(1+n)*n/2
print(s)
#执行1次
1+2+3+……+100=？算法一
#执行1次
#执行1次
该程序采用的推导方法：通过加法计算该程序运行了常数3次，用常数1取代运行时间中的所有加法常数。
O(1)
常量阶
算法效率分析:高斯算法
时间复杂度
1+2+3+……+100=？算法二
n=int(input())
s=0 for i in range(1,n+1):
s=s+i
print(s)
#执行1次
#执行1次
#执行n次
#执行n次
#执行1次
通过加法计算该程序运行了常数2n+3次，修改运行次数函数，只保留最高阶项，由于最高阶系数不是1，去除这个项的相乘系数2。
O(n)
线性阶
算法效率分析:输出二维矩阵算法
时间复杂度
n=int(input())
for i in range(1,n+1):
for j in range(1,n+1):
x=random.randint(10,99)
print(x,end=””)
#执行1次
#执行n次
#执行n*n次
#执行n*n次
#执行n*n次
该程序段中包含二重循环，通过乘法计算该二重循环程序运行了n*n次，该算法中语句的执行次数与问题规模n呈平方增大。
O(n2)
平方阶
算法效率分析:对分查找算法
时间复杂度
i=0;n=len(d);j=n-1
while i<=j:
m=(i+j)//2
if key>=d[m]:
j=m-1
else:
i=m+1
#执行3次
#执行<=log2n+2次
#执行<=log2n+1次
该二分查找在最坏的情况下查找次数依次是n/2,n/4,n/8…… 一直到1为止，我们假设是x次才能查找到目标数。所以可以根据题意列出下面等式：n(1/2)x = 1
O(log2n)
对数阶
→2x=n
→x=log2n
大O表示法
用O()来体现算法时间复杂度，称之为大O表示法。其推导方法如下：
1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中，只保留最高阶项。
3.如果最高阶项存在且不是1，那么去除与这个项相乘数的常数。得到的结果就是大O阶。
例如： n(n-1)
→ n2
保留最高阶项
→ n2
去除常数项
课堂小练
算式： 15n2＋12n＋9，时间复杂度其大O阶为（ ）
15n2＋12n＋9大O阶推导过程：
O(n2)
(常数1取代加法常数）→15n2＋12n
(保留高阶)→15n2
(去除高阶相乘常数)→n2
因此该算式的大O阶(时间复杂度)为O(n2)。
课堂上机操作实验：
#程序一
import time
s = 0 #执行1次
n = 2 * 10 ** 4
start = time.time()
for i in range(1,n + 1): #执行n次
s = s + 1 #执行n次
print(s)
end = time.time()
print(end - start)
#程序二
import time
s = 0
n = 2 * 10 ** 4
start = time.time()
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)
大O表示法具体实例
时间复杂度所耗费的时间是：
执行次数函数 阶 术语描述
16 ｏ(1) 常量阶
3n+6 ｏ(n) 线性阶
5n2+5n+6 ｏ(n2) 平方阶
7log2n+18 ｏ(log2n) 对数阶
8n3+8n2+8n+6 ｏ(n3) 立方阶
3n ｏ(3n) 指数阶
O(1)常见函数的增长率
问题讨论：举例说明空间复杂度的度量
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。高中阶段主要考虑时间复杂度。
算法空间复杂度类似于时间复杂度，只是计算的不是运行次数，而是在运行过程中临时变量被运用次数。
（学习118页完善表格）
数据结构对算法效率的影响
数组 链表
应用场景
组织结构
操作特性 访问：数据访问效率较高 时间复杂度：________ 插入或删除：需要移动大量数组元素 时间复杂度：________ 访问：需要从头结点开始寻找
时间复杂度：________
插入或删除：只要找出某个结点位置，可以方便操作
时间复杂度：________
O(1)
O(n)
O(n)
O(1)
适合数据规模确定且在处理过程中保持数据规模稳定的问题
不需要预先分配存储空间，结点个数不受限制
用一段连续的存储单元来依次存储数组元素
由结点构成，每个结点中包含数据区域和指针区域，相邻结点间通过指针链接
课堂小结
算法的效率
时间复杂度 空间复杂度
数据结构与算法的关系
数组、链表不同操作的时间复杂度
算法效率的重要性
学习评价
对自己的表现进行客观的评价，并思考后续完善的方向。（3=优秀，2=一般，1=仍需加油）
评分项 自我评价
能以高斯问题为例认识算法时间复杂度的概念 3 2 1
能够对简单程序分析其算法时间复杂度 3 2 1
能够对线性结构的算法时间复杂度进行简要分析 3 2 1
能合理评估算法效率的重要性 3 2 1
从此自觉将算法时间复杂度融入算法设计中 3 2 1
课后作业
1.度量某个算法效率高低的两个方面： 、 。
2.分析右侧流程图算法的时间复杂度是（ ）：
A.常量阶 B.线性阶 C.指数阶 D.对数阶
（1）a=int(input())
b=int(input())
if a>b:
max=a
else:
max=b
（2）n=int(input())
i=1;s=1
while i<=n:
s=s*i
i+=1
3.分析程序段的时间复杂度：

展开更多......

收起↑