(
课件网) 必选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个思考与练习。 课后配套练习 ... ...
