迭代递归【解析p49-p52】

乐清中学2023级高二下信息技术校本作业（选修一轮专趣）数据结构与算法、迭代与递归【知识回顾】1.算法效率算法效率的高低可由算法复杂度来衡量。算法复杂度分为算法的时间复杂度和空间复杂度。2.时间复杂度(1)时间复杂度反映了算法执行所需要的时间，常用大“O”来表示。大O表示法是算法的一种特殊的表示法，指出了算法运行时间的增速。大O表示法的操作数是指最糟情况下的运行时间，而不是平均情况或最佳情况。大0表示法中，0(2m+n+1)=0(3n+n+3)=0(7n2+n)=0(n,保留最高项阶，只用0(n)表示。(2)算法中语句的执行次数作为时间复杂度度量标准。(3)语句总的执行次数T()是关于问题规模n的函数。所谓问题规模（也称输入的大小）是指处理问题的大小，即用衡量输入数据量的整数。(4)算法的时间复杂度反映了程序执行时间随问题规模增长而增长的量级，在很大程度上能很好地反映出算法的优劣。(5)常见的时间复杂度从高到低为：0(1)<01ogn)<0(n)<0(nlog2n)<02<0(㎡21og2m)<03)<02")<0(n).3.迭代算法和递归算法的区别(1)迭代是利用变量的旧值推算出变量的一个新值：而递归算法是指一个函数在其定义中直接或间接调用自身的一种方法，它通常把一个复杂的问题转化为一个与原问题相似的规模较小的问题来解决，可以极大地减少代码量，降低编程的难度。因此，迭代算法效率较高，而递归算法比较占用空间，程序运行效率较低。(2)递归是自己调用自己，而迭代就是不断地调用赋值语句：递归中一定有迭代，但是迭代中不一定有递归，大部分情况下递归和迭代可以相互转换。【历年真题】1.【25.1T11】对于任意非空字符串s,甲、乙程序段输出结果相同，则乙程序段加框处的正确代码为Ddef f(s,t):if t>=len(s)-2:n=len(s)return s[t]for i in range(0,n,2):return f(s,t+2)+s[t]print(f(s,0))print(r)甲程序段乙程序段A.r=s[n-i]+rB.r=r+s[n-i-1]C.r=r+s[i]D.r=s[i]+r2.【23.6T10】10.定义如下函数：3.【23.1T11】定义如下函数：def f(a,s):def rf(n):if a>=s:if n<3:return areturn nelse:return rf(n-1)+rf(n-3)return f(a+1,s-a)执行语句v=rf(⑤)，函数rf被调用的次数是C执行语句k=f(6,21)后，k的值为CA.1B.5C.7D.15A.6B.7C.8D.9【数据结构与算法基础练习】1.下列关于数据结构与算法的关系的说法，正确的是(B)A.随着问题规模n的增大，T(n)函数值增长较快的算法较优B.时间复杂度为0(1)的算法，其语句执行次数与问题规模n无关C.同一种数据结构在不同的算法中，时间复杂度相同XD.一般而言，对数阶的时间复杂度要大于指数阶的时间复杂度…53.