浙教版(2019)高中信息技术选修1——数据结构与算法 教学课件

选修1《数据与数据结构》 第五章 数据结构与算法 算法的概念 算法是解决某一特定类型问题的有限求解步骤。描述一个算法可 以采用某一计算机语言，也可以才用自然语言和流程图等 算法的特征 1.有穷性 2. 确定性 3.可行性 4.有0个或多个输入 5.有1个或多个输出 算法效率 算法效率 抽算法效率的高低可由算法复杂度来度量。 时间复杂度 反映了算法执行所需要的时间 空间复杂度 反映了算法执行所需要占用的存储空间 算法效率 推导大O 阶的方法 1、用常数1取代运行时间中的所有加法常数，即O(1) 2、在修改后的运行次数函数中，只保留最高阶项。 例如：n²+n 的时间效率为O(n) 3、如果最高阶项存在且不是1,那么去除与这个项相乘的 常数，得到的结果就是大O阶。 例如： 的时间效率为0(n) 算法效率 算法一是顺序结构，语句总的执行次数为3次，时间复杂度为0(1),称为 常量阶。 算法二是一重循环，语句总的执行次数为2n+3次，时间复杂度为O(n), 称为线性阶。 算法二： (input()) for i in range(1,n+1):#执行n 次 s=S+i #执行n次 print(s) #执行1次 0 nt s n 算法效率 算法一： n =int(input()) s=(1+n)*n/2 print(s) #执行1次 #执行1次 #执行1次 #执行1次 #执行1次 实例 算法的时间复杂度是指该 算法的时间耗费，是该算 法中基本操作重复执行的 次数与问题规模n的某个 函数。 n=int(input()) s=0 x=0 for i in range(1,n+1): for jin range(1,n+1): X=x+1 S=S+X print(s) 小组讨论 时间复杂度 一般将算法中语句的执行次数作为时间复杂度的度量标准。我们在分析时 间复杂度的时候也只关注执行次数的增长次数及其常数倍。 语句总的执行次数T(n)是关于问题规模n的函数。 时间复杂度常用符号0()表示。 在分析算法的时间复杂度时，我们需要知道三个方面： 输入规模 不管使用什么算法，输入规模越大，运行效率肯定会更长。 算法的平均效率、最差效率和最优效率 在输入最优情况下的算法就叫最优效率。 在输入最坏情况下的算法就叫最差效率。 增长次数 在大规模的输入情况下考虑执行次数的增长次数。 注意：经过半个多世纪的发展，计算机的速度和存储容量都已经提升了好 几个数量级。现在空间效率已经不是我们关注的重点。 算法效率 算法\输 入数据 N=50 K=50 N=200 K=100 N=500 K=500 N=2000 K=2000 N=5000 K=8000 N=10000 K=20000 N=20000 K=20000 N=20000 K=200000 白泡排序 0ms 15ms 89ms 1493ms 9363ms 36951ms 147817ms 143457ms 插入排序 1ms 13ms 82ms 1402ms 8698ms 34731ms 134817ms 134836ms 希尔排序 0ms 1ms 6ms 30ms 110ms 257ms 599ms 606ms 选择排序 0ms 5ms 31ms 461ms 2888ms 11736ms 45308ms 44838ms 堆排序 0ms 3ms 9ms 40ms 124ms 247ms 525ms 527ms 归并排序 2ms 6ms 18ms 75ms 199ms 392ms 778ms 793ms 快速排序 0ms 1ms 2ms 14ms 36ms 84ms 196ms 163ms 计数排序 0ms 1ms 1ms 5ms 15ms 32ms 51ms 62ms 基数排序 0ms 1ms 4ms 19ms 47ms 114ms 237ms 226ms 桶排序 0ms 2ms 6ms 25ms 68ms 126ms 254ms 251ms 算法效率 输入规模(各种排序算法的效率) 利用随机数，随机生成区间0～K 之间的序列，共计N个数字，利用各种算法进行排序，记录 排序所需时间，测试环境为i7+vs2015+Debug版本。 算法的平均效率、最差效率和最优效率 1. 算法的最差效率：当输入规模为n时，算法在最坏情况下的效率。 2. 算法的最优效率：当输入规模为n时，算法在最优的情况下的效率。 3. 算法的平均效率：在实际的假设情况下，算法所可能发生的正推推断下所具有的效率。 一般是通过得到或者是假设各类输入的概率分布，以推导出我们所希望的基本操作次数。 在以顺序查找算法为例： ·算法的最差效率： n个数据，在最后一次判断才找到，效率为n。 ·算法的最优效率：n个数据，第一次就判断就找到，效率为1 ·算法的平均效率：n 个数据，我们先假设能找到的概率，然后我们需要求得在第一次查 找到的概率、第二次查找到的概率等等一直求，然后算得总的操作次数，得出算法的平 均效率 两个经验性的规则： 1. 最优效率的分析远远不如最差效率分析重要(因为最差效率可以确定算法运行时间的上界) 2. 如果一个算法的最优效率都不能满足我们的要求，那么我们就可以立即抛弃它。 算法效率 增长次数 1. 如果一个算法在输入规模变大时，但运行时间平缓增长，那么我们就可 以说它就是一个效率高的算法。 2. 如果一个算法在输入规模变大时，它的运行时间成指数级增长，那就可 以说这个算法的效率很差。 增长函数表：对于算法分析具有重要意义的函数值(近似值) n log₂n n¹ nlog₂n n² n³ 2n n! 101 3.3 101 3.3×101 102 103 210 3.6×106 102 6.6 102 6.6×102 104 106 1.3×1030 9.3×10157 10³ 10 10³ 1.0×104 106 109 104 13 104 1.3×105 108 1012 10⁵ 17 10⁵ 1.7×106 1010 1015 指数 增长 106 20 106 2.0×107 1012 1018 规模 对数 线性 n-log-n 二次 三次 指数 阶乘 算法效率 对时间复杂度O的 计 算，其实就是求解算 法的增长函数。 1 log₂n n¹ nlog₂n n² n³ 2" n! 101 3.3 101 3.3×101 102 103 210 3.6×106 102 6.6 102 6.6×102 104 106 1.3X1030 9.3×10157 10³ 10 10³ 1.0×104 106 109 104 13 104 1.3×105 108 1012 105 17 10⁵ 1.7X106 1010 1015 指数 增长 106 20 106 2.0×107 1012 1018 规模 对数 线性 n-log-n 二次 三次 指数 阶乘 算法效率 时间复杂度的耗时比较 增长函数表：对于算法分析具有重要意义的函数值(近似值) No Image 由上图可知： O(1)<0(log₂ )<O(n)<0( )kO()0()<0(n!) 油 数据结构与算法的关系 1、在计算机科学中，数据结构与算法有着密不可分的关系。解决实际问题时， 数据总是以一定的组织结构关系体现并存储，数据结构的设计和选择关 注的是数据的逻辑结构、存储结构以及基本操作；算法的设计和选择 更多的是关注如何在数据结构的基础上综合运用各种基本操作来解决实际问 题。 2、数据组织成不同的结构，是为了满足不同问题的需求，便于算法对数据的 操作，提高孙发处理数据的效率。算法的设计和选择总是依赖于数据结构， 算法设计的同时也伴随着数据结构设计，两者都是为最终解决问题服务。算 法是编程思想，数据结构则是这些思想的基础。 数据结构对算法效率的影响 2、若要对元素进行插入和删除操作，则n1的时间复杂度为O(n)。 n2的时间复杂度为0(1)。 由此可见：数据结构的不同选择会影响算法的运行效率。 数据结构对算法效率的影响 1、若要随机访问其中的一个数据，则n1的时间复杂度为0(1)。 n2的时间复杂度为O(n)。 现有一组n个数据需要存储。 第一种用数组的数据结构来存储记为n1 第二种用链表的数据结构来存储记为n2 实例 $$