选择性必修1 专题五 迭代、递归算法及应用-【导与练】2024高考信息技术一轮复习高中总复习第1轮教学课件PPT（浙江专用）

专题五　迭代、递归算法及应用 思维导图 一、数据结构与算法的关系 1.算法的设计和选择总是依赖于数据结构,算法设计的同时也伴随着数据结构的设计。 2.算法是编程思想,数据结构则是这些思想的基础。 3.算法效率 算法效率的高低可由算法复杂度来度量。算法复杂度又分为算法的时间复杂度和空间复杂度。 4.时间复杂度 (1)时间复杂度反映了算法执行所需要的时间,常用O()来表示,称之为大O记法。 (2)算法中语句的执行次数作为时间复杂度的度量标准。 归纳提炼 (3)语句总的执行次数T(n)是关于问题规模n的函数。所谓问题规模(也称为输入的大小)是指处理问题的大小,即用来衡量输入数据量的整数。 (4)算法的时间复杂度反映了程序执行时间随问题规模增长而增长的量级,在很大程度上能很好地反映出算法的优劣。 (5)常见的时间复杂度耗费时间的大小关系为: O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n2log2n)<O(n3)<O(2n)<O(n!)。 5.空间复杂度 (1)空间复杂度反映了算法执行所需要占用的存储空间。 (2)空间复杂度比较常用的有:O(1)、O(n)、O(log2n)。 6.数据结构对算法效率的影响 选择不同的数据结构,算法的运行效率可能也会不同。 二、迭代算法 1.迭代算法的概念 不断用变量的原值递推出新值的过程称为迭代算法。 2.利用迭代算法解决问题,需要考虑的三个方面 ①确定迭代变量 ②建立迭代关系式 ③控制迭代过程 【归纳与提升】 迭代算法的难点在于寻找和建立正确的迭代公式,一般使用循环结构语句实现。 三、递归算法 1.递归算法的概念 一个函数在其定义中直接或间接调用自身来解决问题的方法称为递归算法。 递归算法的实质是:将规模大的问题分解成规模小的问题,然后从这些小问题的解中方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法。当递归到达某个边界,如问题规模缩减为0或1时,能直接得解。 2.设计递归算法时,需要满足的两个条件: ①确定递归公式。 ②确定递归结束条件。 3.递归过程的两个阶段 ①递推:把较复杂的问题的求解递推到一些简单问题的求解。 ②回归:当获得最简单情况的解后,逐级返回依次得到稍复杂问题的解。 【归纳与提升】 正确区分迭代算法和递归算法 (1)迭代是利用变量的原值递推出变量的一个新值;而递归算法是指一个函数在其定义中直接或间接调用自身来解决问题的一种方法,它通常把一个复杂的问题转化为一个与原问题相似的规模较小的问题来解决,可以极大地减少代码量,降低编程的难度。因此,迭代算法效率较高,而递归算法比较占用空间,程序运行效率较低。 (2)递归是自己调用自己,而迭代就是不断地调用赋值语句;递归中一定有迭代,但是迭代中不一定有递归,大部分情况下递归和迭代可以相互转换。 [例1] 下列四个常见的时间复杂度之间的大小关系正确的是(　　) A.O(log2n)<O(1)<O(n)<O(n2) <O(nlog2n) B.O(log2n)<O(1)<O(n)<O(nlog2n)<O(n2) C.O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2) D.O(1)<O(n2)<O(n3)<O(n!)<O(2n) 典型例题 解析:常见的时间复杂度从低到高为: O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n2log2n)<O(n3)<O(2n)<O(n!),因此答案为C。 C [例2] 输入n个学生的身高,求这n个学生的平均身高,代码如下: sumsg=0 avgsg=0 n=int(input(′请输入学生数:′)) for i in range(n): high=float(input(′请输入身高:′)) sumsg+=high avgsg=sumsg/n print(′平均身高为:′,avgsg) 上述程序的算法复杂度为(　　) A.O(1) B.O(n) C.O(n2) D.O(log2n) B 解析:该程序采用一重循环求n个身高的总和,因此时间复杂度为O(n),答案为B。 [例3] Python从最初发布到现在的版本不断更新的过程可以看出,一款软件从上市到最终框架的成型,是不断试错、不断根据用户体验反馈快速调整和完善得到的结果。这个例子体现的算法思想是(　　) A.枚举 B.解析 C.迭代 D.递归 C 解析:软件在原有的基础上不断更新、完善得到的结果,属于迭代思想,因此答案为C。 [例4] (2023·浙江1月选考)定义如下函数: def rf(n): 　　if n<3: 　　　return n 　　return rf(n-1)+rf(n-3) 执行语句v=rf(5),函数rf被调用的次数是(　　)