还剩12页未读，
继续阅读
成套系列资料，整套一键下载
高中信息技术浙教版 (2019)选修1 数据与数据结构1.1 数据公开课课件ppt
展开
这是一份高中信息技术浙教版 (2019)选修1 数据与数据结构1.1 数据公开课课件ppt，共20页。PPT课件主要包含了学习目标，情境导入，Google实验，算法+数据结构程序，算法效率重要性分析，实例分析，算法效率分析，执行1次，常量阶，执行n次等内容，欢迎下载使用。
能理解数据结构与算法的关系。
能认识算法效率高低的主要的两个方面：时间复杂度与空间复杂度，及这两个方面的表示与计算。
能通过具体的实例分析算法的效率。
逐步自觉将算法的效率应用在算法程序设计中，根据问题选择合适的数据结构，提高算法效率。
能通过具体的实例认识算法效率的重要性。
搜索引擎是互联网上的检索技术，它能提高人们获取搜集信息的速度，为人们提供更好的网络使用环境，Ggle做过一个试验，显示10条搜索结果的页面载入需要0.4秒，显示30条搜索结果的页面载入需要0.9秒，结果后者使得Ggle总的流量和收入减少了20%。Ggle地图上线的时候，首页大小有100KB，后来下降到70~80KB。结果，流量在第一个星期上升了10%，接下来的3个星期又再上升了25%。 Amazn（亚马逊公司）的统计也显示了相近的结果，首页打开时间每增加100毫秒，网站销售量会减少1%。
算法：解析法、枚举法、递归、迭代、排序、查找等数据结构：数组、链表、队列、栈、字符串、树等
著名的计算机科学家、图灵奖获得者尼克劳斯•沃思（Niklaus Wirth）指出
（Algrithm+Data Structures=Prgrams）
算法依赖数据结构，算法与数据结构为程序服务，达成问题解决
智慧农场监测系统、气象预报程序必须在指定时间前完成。如果不能按时计算出预报结果，这个算法有价值吗？
入口处的红外测温、人脸识别程序，必须在几分之一秒内完成工作。过慢的算法会带来糟糕的用户体验，这样的设备有可能广泛采用吗？
“数学王子”高斯小时候，老师给从未上过算术课的同学们布置了一道题目：1+2+3+……+100=？
其他同学在仔细算题时，高斯快速巧妙地解决了问题，老师对他刮目相看。他的算法被称为“高斯算法”。
指该算法的时间耗费，是该算法中基本操作重复执行的次数与问题规模n的某个函数。
指该算法执行所需要占用的存储空间。（主要指临时占用内存空间）
算法效率分析:高斯算法
1+2+3+……+100=？算法一
该程序采用的推导方法：通过加法计算该程序运行了常数3次，用常数1取代运行时间中的所有加法常数。
1+2+3+……+100=？算法二
通过加法计算该程序运行了常数2n+3次，修改运行次数函数，只保留最高阶项，由于最高阶系数不是1，去除这个项的相乘系数2。
算法效率分析:输出二维矩阵算法
该程序段中包含二重循环，通过乘法计算该二重循环程序运行了n*n次，该算法中语句的执行次数与问题规模n呈平方增大。
算法效率分析:对分查找算法
#执行<=lg2n+2次
#执行<=lg2n+1次
该二分查找在最坏的情况下查找次数依次是n/2,n/4,n/8…… 一直到1为止，我们假设是x次才能查找到目标数。所以可以根据题意列出下面等式：n(1/2)x = 1
用O()来体现算法时间复杂度，称之为大O表示法。其推导方法如下：1.用常数1取代运行时间中的所有加法常数。2.在修改后的运行次数函数中，只保留最高阶项。3.如果最高阶项存在且不是1，那么去除与这个项相乘数的常数。得到的结果就是大O阶。
→ n2 去除常数项
算式： 15n2＋12n＋9，时间复杂度其大O阶为（ ）
15n2＋12n＋9大O阶推导过程：
(常数1取代加法常数）→15n2＋12n
(保留高阶)→15n2
(去除高阶相乘常数)→n2
因此该算式的大O阶(时间复杂度)为O(n2)。
#程序一imprt times = 0 #执行1次n = 2 * 10 ** 4start = time.time() fr i in range(1,n + 1): #执行n次 s = s + 1 #执行n次print(s)end = time.time()print(end - start)
#程序二imprt times = 0n = 2 * 10 ** 4start = time.time() fr i in range(1,n + 1): #执行n次 fr j in range(1,n + 1): s = s + 1 #执行n * n次print(s)end = time.time() print(end - start)
时间复杂度所耗费的时间是：
O(1)
空间复杂度(Space Cmplexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。高中阶段主要考虑时间复杂度。 算法空间复杂度类似于时间复杂度，只是计算的不是运行次数，而是在运行过程中临时变量被运用次数。
（学习118页完善表格）
数据结构对算法效率的影响
适合数据规模确定且在处理过程中保持数据规模稳定的问题
不需要预先分配存储空间，结点个数不受限制
用一段连续的存储单元来依次存储数组元素
由结点构成，每个结点中包含数据区域和指针区域，相邻结点间通过指针链接
数据结构与算法的关系
数组、链表不同操作的时间复杂度
对自己的表现进行客观的评价，并思考后续完善的方向。（3=优秀，2=一般，1=仍需加油）
能理解数据结构与算法的关系。
能认识算法效率高低的主要的两个方面：时间复杂度与空间复杂度，及这两个方面的表示与计算。
能通过具体的实例分析算法的效率。
逐步自觉将算法的效率应用在算法程序设计中，根据问题选择合适的数据结构，提高算法效率。
能通过具体的实例认识算法效率的重要性。
搜索引擎是互联网上的检索技术，它能提高人们获取搜集信息的速度，为人们提供更好的网络使用环境，Ggle做过一个试验，显示10条搜索结果的页面载入需要0.4秒，显示30条搜索结果的页面载入需要0.9秒，结果后者使得Ggle总的流量和收入减少了20%。Ggle地图上线的时候，首页大小有100KB，后来下降到70~80KB。结果，流量在第一个星期上升了10%，接下来的3个星期又再上升了25%。 Amazn（亚马逊公司）的统计也显示了相近的结果，首页打开时间每增加100毫秒，网站销售量会减少1%。
算法：解析法、枚举法、递归、迭代、排序、查找等数据结构：数组、链表、队列、栈、字符串、树等
著名的计算机科学家、图灵奖获得者尼克劳斯•沃思（Niklaus Wirth）指出
（Algrithm+Data Structures=Prgrams）
算法依赖数据结构，算法与数据结构为程序服务，达成问题解决
智慧农场监测系统、气象预报程序必须在指定时间前完成。如果不能按时计算出预报结果，这个算法有价值吗？
入口处的红外测温、人脸识别程序，必须在几分之一秒内完成工作。过慢的算法会带来糟糕的用户体验，这样的设备有可能广泛采用吗？
“数学王子”高斯小时候，老师给从未上过算术课的同学们布置了一道题目：1+2+3+……+100=？
其他同学在仔细算题时，高斯快速巧妙地解决了问题，老师对他刮目相看。他的算法被称为“高斯算法”。
指该算法的时间耗费，是该算法中基本操作重复执行的次数与问题规模n的某个函数。
指该算法执行所需要占用的存储空间。（主要指临时占用内存空间）
算法效率分析:高斯算法
1+2+3+……+100=？算法一
该程序采用的推导方法：通过加法计算该程序运行了常数3次，用常数1取代运行时间中的所有加法常数。
1+2+3+……+100=？算法二
通过加法计算该程序运行了常数2n+3次，修改运行次数函数，只保留最高阶项，由于最高阶系数不是1，去除这个项的相乘系数2。
算法效率分析:输出二维矩阵算法
该程序段中包含二重循环，通过乘法计算该二重循环程序运行了n*n次，该算法中语句的执行次数与问题规模n呈平方增大。
算法效率分析:对分查找算法
#执行<=lg2n+2次
#执行<=lg2n+1次
该二分查找在最坏的情况下查找次数依次是n/2,n/4,n/8…… 一直到1为止，我们假设是x次才能查找到目标数。所以可以根据题意列出下面等式：n(1/2)x = 1
用O()来体现算法时间复杂度，称之为大O表示法。其推导方法如下：1.用常数1取代运行时间中的所有加法常数。2.在修改后的运行次数函数中，只保留最高阶项。3.如果最高阶项存在且不是1，那么去除与这个项相乘数的常数。得到的结果就是大O阶。
→ n2 去除常数项
算式： 15n2＋12n＋9，时间复杂度其大O阶为（ ）
15n2＋12n＋9大O阶推导过程：
(常数1取代加法常数）→15n2＋12n
(保留高阶)→15n2
(去除高阶相乘常数)→n2
因此该算式的大O阶(时间复杂度)为O(n2)。
#程序一imprt times = 0 #执行1次n = 2 * 10 ** 4start = time.time() fr i in range(1,n + 1): #执行n次 s = s + 1 #执行n次print(s)end = time.time()print(end - start)
#程序二imprt times = 0n = 2 * 10 ** 4start = time.time() fr i in range(1,n + 1): #执行n次 fr j in range(1,n + 1): s = s + 1 #执行n * n次print(s)end = time.time() print(end - start)
时间复杂度所耗费的时间是：
O(1)
空间复杂度(Space Cmplexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。高中阶段主要考虑时间复杂度。 算法空间复杂度类似于时间复杂度，只是计算的不是运行次数，而是在运行过程中临时变量被运用次数。
（学习118页完善表格）
数据结构对算法效率的影响
适合数据规模确定且在处理过程中保持数据规模稳定的问题
不需要预先分配存储空间，结点个数不受限制
用一段连续的存储单元来依次存储数组元素
由结点构成，每个结点中包含数据区域和指针区域，相邻结点间通过指针链接
数据结构与算法的关系
数组、链表不同操作的时间复杂度
对自己的表现进行客观的评价，并思考后续完善的方向。（3=优秀，2=一般，1=仍需加油）
相关课件
信息技术选修1 数据与数据结构5.1 数据结构与算法的关系完美版ppt课件： 这是一份信息技术选修1 数据与数据结构5.1 数据结构与算法的关系完美版ppt课件，文件包含51数据结构与算法的关系课件pptx、51数据结构与算法的关系教学设计doc等2份课件配套教学资源，其中PPT共13页， 欢迎下载使用。
浙教版 (2019)选修1 数据与数据结构5.3 数据排序背景图课件ppt： 这是一份浙教版 (2019)选修1 数据与数据结构5.3 数据排序背景图课件ppt，共14页。PPT课件主要包含了确定数据比较的轮数，确定每一轮比较的次数等内容，欢迎下载使用。
高中信息技术浙教版 (2019)选修1 数据与数据结构5.4 数据查找多媒体教学ppt课件： 这是一份高中信息技术浙教版 (2019)选修1 数据与数据结构5.4 数据查找多媒体教学ppt课件，共28页。PPT课件主要包含了查找动物问题，猜数字游戏，抽象与建模，设计算法与数据结构，程序实现等内容，欢迎下载使用。
