第14章（算法效率和递归）知识点梳理—2024届高考信息技术二轮复习知识点梳理

第十四章（算法效率和递归） 1.算法效率，同一个问题会有可能有不同的解决办法，也就是说可能有不同的算法，就如同“一题多解”一样。有的算法效率高一些，有的算法效率低一些。通常，算法效率的高低可由算法复杂度来度量。算法复杂度又分为时间复杂度和空间复杂度，时间复杂度反映算法执行所需要的时间，空间复杂度反映算法复杂度所需要占用的存储空间，每个算法的复杂度都不是固定的。 2.常见的时间复杂度的耗时比较：O(1)<=O(log2n)<=O(n)<=O(n²) 如下图所示 图1.1 常见算法复杂度 算法名 复杂度 解析 O(1) 枚举、递归 O(n) 冒泡排序、选择排序 O(n²) 对分查找法 O(log2n) 表1.1 递归 递归需要满足两个条件1.确定递归公式、2.递归结束条件 递归通过对递归工作栈的压栈和出栈操作实现计算 例如：求5！ def f(x): If x==1: #结束条件 return 1 else: return f(x-1)*x #递归公式 计算过程： f(5)=f(4)*5 递归工作栈中入栈*5 f(4)=f(3)*4 递归工作栈中入栈*4 f(3)=f(2)*3 递归工作栈中入栈*3 f(2)=f(1)*2 递归工作栈中入栈*2 f(1)=1 递归工作栈中入栈1 根据栈的原理，出栈顺序为1、*2、*3、*4和*5，最后计算得120 【仅供参考】 表1.2 原创精品资源学科网独家享有版权，侵权必究！6 学科网（北京）股份有限公司 $$