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