5.1 数据结构与算法效率 课件-2021-2022学年浙教版（2019）高中信息技术选修1

5.1 数据结构与算法效率 一个人想要喝茶，但当时的情况是：开水没有，水壶要洗，茶壶和茶杯要洗；火已经生了，茶叶也有了怎么办？ 泡茶 甲： 洗开水壶 灌凉水 洗茶壶 洗茶杯 拿茶叶 泡茶喝 烧开水 乙： 洗开水壶 洗茶壶 洗茶杯 拿茶叶 灌凉水 烧开水 泡茶喝 丙： 洗开水壶 灌凉水 烧开水 拿茶叶 洗茶壶 洗茶杯 泡茶喝 在计算机科学中，数据结构与算法有着密不可分的关系。解决实际问题 时，数据总是以一定的组织结构关系体现并存储，数据结构的设计和选 择关注的是数据的逻辑结构、存储结构以及基本操作；算法的设计和选 择更多的是关注如何在数据结构的基础上综合运用各种基本数据操作来 解决实际问题。 因此，算法的设计和选择总是依赖于数据结构，算法设计的同时也伴随 着数据结构的设计，两者都是为最终解决问题服务。同时，数据结构的 设计和选择会对算法效率产生一定的影响。 算法效率 同一个问题可能会有不同的解决方法，也就是说可能有不同的算法。 有的算法效率高一些，有的算法效率低一些。通常，算法效率的高低 可由算法复杂度来度量。 算法复杂度又分为算法的时间复杂度和空间复杂度，其中时间复杂度 反映了算法执行所需要的时间，而空间复杂度反映了算法执行所需要 占用的存储空间。 算法运行需要的时间，一般将算法中语句的执行次数作为时间复杂度的 度量标准。语句总的执行次数T（n）是关于问题规模n的函数。 所谓问题规模（也称为输入的大小）是指处理问题的大小，即用来衡量 输入数据量的整数。 1 2 3 4 5 6 7 8 9 10 … … … n 在约瑟夫问题中，用数组或链表中元素的个数作为问题规模。 时间复杂度常用符号O表示，不包括T(n)函数的低阶项和首项系数， 如n(n-1)的量级与n2相同，其时间复杂度可表示成O(n2)。 用O()来体现算法时间复杂度，称之为大O记法。 通常，随着问题规模n的增大，函数值增长较慢的算法较优。 例如，求1+2+…+n的和可以用以下两种算法来实现： 算法一： n=int(input()) #执行1次 s=(1+n)*n/2 #执行1次 print(s) #执行1次 算法二： n=int(input()) #执行1次 s=0 #执行1