5.1 数据结构与算法效率 课件（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取代运行时间中的所有加法