考研笔记

算法和算法评价

第 1 章真正要考的是这一节。 教材【命题追踪】列了两条：选择题「分析算法的时间复杂度」（2011—2014、2017、2019、2022），算法设计题「分析时空复杂度」（2010—2013、2015、2016、2018—2021）。后者就是每道算法大题的第 3 问，几乎年年有。

机制

1.2.1 五个特性与四个目标

算法是对特定问题求解步骤的一种描述，是指令的有限序列，每条指令表示一个或多个操作。

算法必须具备的五个特性「好」算法应当达到的四个目标
有穷性：有穷步之后结束，且每一步都在有穷时间内完成正确性：能正确地求解问题
确定性：每条指令有确切含义，相同的输入只能得出相同的输出可读性：帮助人们理解
可行性：操作都能通过已实现的基本运算执行有限次来实现健壮性：对非法输入能做出反应或处理
输入：零个或多个高效率与低存储量需求
输出：一个或多个

左栏是算法的定义，右栏是设计要求。 选择题常把可读性、健壮性、正确性混进「重要特性」的选项里。

1.2.2 时间复杂度

频度是一条语句在算法中被重复执行的次数。所有语句的频度之和记为 。基本运算（最深层循环中的语句）的频度与 同数量级，所以直接用基本运算执行次数的数量级作为时间复杂度： 的严格定义：若存在正常数 和 ，使得当 时都满足 。实际使用时取 中随 增长最快的项，系数置为 1，例如 记为 。

时间复杂度不仅依赖问题规模 ，还依赖输入数据的性质（如初始状态）。在数组中顺序查找 ：没有 时比较 次，最后一个元素就是 时比较次数为常数。由此有三种说法：

  • 最坏时间复杂度：最坏情况下的时间复杂度。
  • 平均时间复杂度：所有可能的输入实例等概率出现时，算法的期望运行时间。
  • 最好时间复杂度：最好情况下的时间复杂度。

一般考虑最坏情况，以保证运行时间不会比它更长。

两条运算规则：

加法规则：乘法规则：

并列的程序块用加法规则，嵌套的程序块用乘法规则。 常见量级由小到大：统考真题常把 写成 ，默认底数为 2。

1.2.2 空间复杂度

只分析除输入数据和程序本身之外的额外空间。 输入数据所占空间只取决于问题本身，与算法无关。若算法新建了几个与规模 相同的辅助数组，空间复杂度为 。

算法原地工作指所需的辅助空间为常量，即 。

手算模板

教材【归纳总结】把这类题分成两种形式，外加递归。

① 循环变量出现在循环条件里（while 型）

  1. 找基本运算（循环体里改变循环变量的那句），设它执行了 次。
  2. 写出执行 次后循环变量的值。
  3. 代入循环条件，解出 关于 的式子，取最高次项。

例：i=1; while(i<=n) i=i*2; 执行 次后 ，由 得 ，即 。

② 循环变量与循环条件无关（多层 for 型）

从内往外累加，只关注最内层语句的执行次数。外层变量按倍数变化时，列表写出「外层变量的取值 → 内层执行次数」，再求和，不能直接把两层的次数相乘。

③ 递归

写出递推式。每次调用只做常数量的工作时，时间复杂度等于调用次数：六道统考真题一张表（每道都用脚本数过循环次数）：

年份程序段执行 次后 / 求和结论
2011x=2; while(x<n/2) x=2*x;，即
2012fact(n)：if(n<=1) return 1; return n*fact(n-1);递归调用 次
2014for(k=1;k<=n;k*=2) for(j=1;j<=n;j++) count++;外层 轮，每轮 次
2017while(sum<n) sum += ++i;
2019x=0; while(n>=(x+1)*(x+1)) x=x+1;
2022for(i=1;i<n;i*=2) for(j=0;j<i;j++) sum++;，介于 与 之间

边界

说法判断说明
「可读性、健壮性、正确性是算法的重要特性」❌这是「好」算法的设计目标；五个特性是有穷性、确定性、可行性、输入、输出
「算法至少有一个输入」❌输入是零个或多个；输出才是一个或多个
「算法的时间效率取决于执行所花的 CPU 时间」❌指时间复杂度，即执行的计算工作量
「算法设计中不允许用牺牲空间效率的方式换取时间效率」❌允许。对时间要求高、对空间要求不高的场景就会这样做
「 表示问题规模是 」❌问题规模仍是 ； 表示执行时间与 成正比，即
「空间复杂度 表示不需要辅助空间」❌表示所需辅助空间的大小与问题规模 无关，是常量
「空间复杂度要算上输入数据占的空间」❌只算除输入和程序之外的额外空间
「平均时间复杂度是最好与最坏的平均值」❌是所有可能的输入等概率出现时的期望运行时间
「一般讨论平均时间复杂度」❌一般考虑最坏时间复杂度
「有 if-else 时取两个分支的平均」❌取各分支中最大的时间复杂度
「两层嵌套循环一定是 」❌外层按倍数增长时要列表求和：2014 是 ，2022 是
「return 2*Func(n/2)+n; 的时间复杂度含 」❌+n 是函数值的一部分，不是工作量。每次调用 ，共 次，为
「 和 是两个量级」❌统考默认底数为 2；换底只差常数因子，量级相同

错题复盘：2014 与 2022，外层都是乘 2，结论差了一个

两道题的外层循环都是 *=2，共约 轮，区别全在内层：

  • 2014 内层是 j<=n，与外层变量无关，每轮都是 次，总数 ，为 。
  • 2022 内层是 j<i，次数随外层变量翻倍，总数 。等比数列的和由最后一项主导，约为 ，为 。

2022 若按「外层 × 内层最多 」直接相乘，会错选 。内层次数依赖外层变量时，只能求和。

错题复盘：2017 的 sum += ++i

sum += ++i 等价于 ++i; sum = sum + i;，所以 次之后 。 由 得 ，为 。 按平方增长，所以循环次数是开方级，容易误选 。

错题复盘：递归函数的返回值不是工作量（1.2.3 第 11 题）

if(n==1) return 1; else return 2*Func(n/2)+n; 答案是 。 递推式里的 2*…+n 描述的是函数的返回值，与运行时间无关。 每次调用只做一次判断和一次运算，共递归 次。套主定理得出 或 都是把「值」当成了「代价」。

错题复盘：2013 合并两个有序链表

本节习题未收，但【命题追踪】列了 2013。题目：两个长度分别为 、 的升序链表合并为一个降序链表，最坏情况下的时间复杂度是 。 最坏情况下两个链表交替取完，比较 次，而 。 是最好情况（一个链表的元素全部小于另一个）。

考点

  • 五个特性 vs 四个目标；输入零个或多个，输出一个或多个。
  • 常见量级的大小顺序。
  • 最坏 / 平均 / 最好的定义，一般考虑最坏。
  • while 型设 次解不等式；嵌套型从内向外求和；递归型写递推式。
  • 空间复杂度只算额外空间；原地工作即 。
  • 算法设计题的第 3 问：时间复杂度和空间复杂度，几乎每年都有。

链接

反向链接