5.1 数据结构与算法的关系 课件（13张PPT）
文档属性
| 名称 | 5.1 数据结构与算法的关系 课件（13张PPT） |  | |
| 格式 | pptx | ||
| 文件大小 | 876.8KB | ||
| 资源类型 | 教案 | ||
| 版本资源 | 浙教版（2019） | ||
| 科目 | 信息技术（信息科技） | ||
| 更新时间 | 2021-10-25 18:17:18 | ||
图片预览
文档简介
(共13张PPT)
必选1《数据与数据结构》
第五章 数据结构与算法
5.1 数据结构与算法的关系
数学家高斯的故事
Google试验
情境导入
数学家高斯的故事
“数学王子”高斯小时候，老师给从未上过算术课的同学们布置了一道题目：1+2+3+……+100=？
高斯很快地巧妙地解决了问题，老师对他刮目相看。他的算法被称为“高斯算法”。
返回
Google实验
返回
互联网的搜索引擎能够快速地访问与检索信息，Google做过一个试验，显示10条搜索结果的页面载入需要0.4秒，显示30条搜索结果的页面载入需要0.9秒，结果后者使得Google总的流量和收入减少了20%。Google地图上线的时候，首页大小有100KB，后来下降到70~80KB。结果，流量在第一个星期上升了10%，接下来的3个星期又再上升了25%。Amazon的统计也显示了相近的结果，首页打开时间每增加100毫秒，网站销售量会减少1%。
算法的效率
时间复杂度
空间复杂度
算法效率分析
时间复杂度
算法效率分析：高斯算法
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=int(input())
s=0
x=0
for i in range(1,n+1):
for j in range(1,n+1):
x=x+1
s=s+x
print(s)
算法的时间复杂度是指该算法的时间耗费，是该算法中基本操作重复执行的次数与问题规模n的某个函数。
小组讨论
结合“导入2”案例，并与教材中下列案例进行比较分析：
天气预报程序必须在指定时间前完成气象指数的计算。如果不能按时计算出预报结果，这个算法就毫无价值。
数字相机的人脸识别程序，必须在几分之一秒内完成工作。过慢的算法会带来糟糕的用户体验，照相机的制造商不可能采用。
数据结构对算法效率的影响
数组 链表
应用场景 适合数据规模确定且在处理过程中保持数据规模稳定的问题 不需要预先分配存储空间，结点个数不受限制
组织结构 用一段连续的存储单元来依次存储数组元素 由结点构成，每个结点中包含数据区域和指针区域，相邻结点间通过指针链接
操作特性 访问：数据访问效率较高 时间复杂度：________ 插入或删除：需要移动大量数组元素 时间复杂度：________ 访问：需要从头结点开始寻找
时间复杂度：________
插入或删除：只要找出某个结点位置，可以方便操作
时间复杂度：________
算法的效率
时间复杂度
空间复杂度
数据结构与算法的关系
数组、链表不同操作的时间复杂度
课堂小结
学习评价
对自己和同伴的表现进行客观的评价，并思考后续完善的方向。（5=优秀，4=超出一般水平，3=满意，2=有待改进，1=不太理想）
评分项 自我评价 同学互评
能完成新课导入中的问题并建立算法时间复杂度的概念 5 4 3 2 1 5 4 3 2 1
能够对简单程序分析其算法时间复杂度 5 4 3 2 1 5 4 3 2 1
能够对线性结构的算法时间复杂度进行简要分析 5 4 3 2 1 5 4 3 2 1
能合理评估算法效率的重要性 5 4 3 2 1 5 4 3 2 1
课堂作业
本节课的1个问题与讨论和2个思考与练习。
课后配套练习
必选1《数据与数据结构》
第五章 数据结构与算法
5.1 数据结构与算法的关系
数学家高斯的故事
Google试验
情境导入
数学家高斯的故事
“数学王子”高斯小时候，老师给从未上过算术课的同学们布置了一道题目：1+2+3+……+100=？
高斯很快地巧妙地解决了问题，老师对他刮目相看。他的算法被称为“高斯算法”。
返回
Google实验
返回
互联网的搜索引擎能够快速地访问与检索信息，Google做过一个试验，显示10条搜索结果的页面载入需要0.4秒，显示30条搜索结果的页面载入需要0.9秒，结果后者使得Google总的流量和收入减少了20%。Google地图上线的时候，首页大小有100KB，后来下降到70~80KB。结果，流量在第一个星期上升了10%，接下来的3个星期又再上升了25%。Amazon的统计也显示了相近的结果，首页打开时间每增加100毫秒，网站销售量会减少1%。
算法的效率
时间复杂度
空间复杂度
算法效率分析
时间复杂度
算法效率分析：高斯算法
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=int(input())
s=0
x=0
for i in range(1,n+1):
for j in range(1,n+1):
x=x+1
s=s+x
print(s)
算法的时间复杂度是指该算法的时间耗费，是该算法中基本操作重复执行的次数与问题规模n的某个函数。
小组讨论
结合“导入2”案例，并与教材中下列案例进行比较分析：
天气预报程序必须在指定时间前完成气象指数的计算。如果不能按时计算出预报结果，这个算法就毫无价值。
数字相机的人脸识别程序，必须在几分之一秒内完成工作。过慢的算法会带来糟糕的用户体验，照相机的制造商不可能采用。
数据结构对算法效率的影响
数组 链表
应用场景 适合数据规模确定且在处理过程中保持数据规模稳定的问题 不需要预先分配存储空间，结点个数不受限制
组织结构 用一段连续的存储单元来依次存储数组元素 由结点构成，每个结点中包含数据区域和指针区域，相邻结点间通过指针链接
操作特性 访问：数据访问效率较高 时间复杂度：________ 插入或删除：需要移动大量数组元素 时间复杂度：________ 访问：需要从头结点开始寻找
时间复杂度：________
插入或删除：只要找出某个结点位置，可以方便操作
时间复杂度：________
算法的效率
时间复杂度
空间复杂度
数据结构与算法的关系
数组、链表不同操作的时间复杂度
课堂小结
学习评价
对自己和同伴的表现进行客观的评价，并思考后续完善的方向。（5=优秀，4=超出一般水平，3=满意，2=有待改进，1=不太理想）
评分项 自我评价 同学互评
能完成新课导入中的问题并建立算法时间复杂度的概念 5 4 3 2 1 5 4 3 2 1
能够对简单程序分析其算法时间复杂度 5 4 3 2 1 5 4 3 2 1
能够对线性结构的算法时间复杂度进行简要分析 5 4 3 2 1 5 4 3 2 1
能合理评估算法效率的重要性 5 4 3 2 1 5 4 3 2 1
课堂作业
本节课的1个问题与讨论和2个思考与练习。
课后配套练习