算法与复杂度：练习题及解析

1复杂度衡量什么

算法是解决一个问题的有限的、精确的步骤列表，例如给一个列表排序，或在电话簿中查找一个名字。

两个算法可以解决同一个问题，但所用的时间可能相差很大。复杂度描述的是输入变大时工作量如何增长。

输入的规模称为 n：要排序的项目数、列表的长度、图中的节点数。

想一想在一本 1000 页的电话簿里找一个名字。读每一页最多需要 1000 步。从中间翻开并每次减半，大约只需要 10 步。

时间复杂度计算步骤数。空间复杂度计算额外的内存。两者都写成 n 的函数。

通常看最坏情况：规模为 n 的所有输入中工作量最大的情况。有时题目问的是平均情况或最好情况。

2大 O 和增长类别

大 O 记号只保留对大的 n 重要的部分。你要舍去常数因子，只保留增长最快的项。

当 n = 1000 时，n² 项是 3 000 000，而 5n 只有 5000。较小的项几乎不改变总数。

这些类别反复出现，按增长从慢到快排列：

• O(1)，常数：通过下标读取数组元素。
• O(log n)，对数：二分查找，每一步使问题减半。
• O(n)，线性：对所有项目遍历一次，例如找最大值。
• O(n log n)：好的排序算法，例如归并排序。
• O(n²)，平方：对项目做两层嵌套循环，例如冒泡排序。
• O(2ⁿ)，指数：尝试每一个子集。它很快就变得不可用。

大 O 是一个上界：工作量增长最多这么快。Ω（大欧米伽）是下界，Θ（西塔）是紧确界，既是上界也是下界。

对数的底在大 O 中无关紧要，因为不同底的对数只相差一个常数因子。

3查找、排序和递归

几乎每门课程都会出现一些算法。把它们的复杂度当作事实记住。

• 线性查找逐项检查：O(n)。二分查找需要已排序的数组，每一步使范围减半：O(log n)。
• 冒泡、插入和选择排序在嵌套循环中比较并交换项目：O(n²)。对于已经排好序的数组，插入排序是 O(n)。
• 归并排序把数组分成两半，分别排序再合并：任何情况下都是 O(n log n)，额外内存为 O(n)。
• 快速排序围绕一个枢轴划分：平均 O(n log n)，但最坏情况是 O(n²)，例如以第一个元素为枢轴去排已排好序的数组。
• 只靠比较项目的排序，在最坏情况下不可能比 Ω(n log n) 更好。计数排序更快，因为它不做比较。

递归函数在更小的输入上调用自身，直到遇到可以直接回答的基本情形。它的运行时间写成递推式：

• T(n) = T(n/2) + O(1) 给出 O(log n)，像二分查找。
• T(n) = 2T(n/2) + O(n) 给出 O(n log n)，像归并排序。
• T(n) = T(n − 1) + O(n) 给出 O(n²)。
• T(n) = 2T(n − 1) + O(1) 给出 O(2ⁿ)。

有三种设计思想值得了解。分治是拆分、求解再合并。贪心每一步选取局部最优的选择。动态规划存储重叠子问题的答案，使它们只计算一次。

4分步方法

要求一段代码的时间复杂度：

1. 确定 n 是什么：输入的规模。
2. 数出每个循环运行的次数。每次加 1 的循环大约运行 n 次。每次翻倍或减半的循环大约运行 log₂ n 次。
3. 嵌套的循环相乘。依次执行的循环相加。
4. 对于递归函数，写出递推式：调用多少次、规模多大，再加上每次调用的工作量。
5. 保留增长最快的项，舍去常数。
6. 用一个小的数检验，例如 n = 8 或 n = 1024。

对于理论题，先指出它所描述的算法或思想，再回忆它的复杂度及条件（已排序的输入、非负权重、重叠子问题）。

5例题讲解

跟着每一步走。打开下一步之前，先试着预测它。

6常见错误

• 把依次运行的循环相乘。n + n = 2n 仍然是 O(n)。
• 保留常数，如 O(2n) 或 O(n/2)。两者都是 O(n)。
• 把翻倍的循环算作 n 轮。它大约运行 log₂ n 次。
• 对未排序的数据使用二分查找，或者对无法一步到达中间的链表使用二分查找。
• 题目问最坏情况时，却给出快速排序的平均情况。
• 以为大 O 表示“精确”。O(n²) 是上界；Θ(n²) 才是精确的增长。

7考试题是什么样的

• 简单：关键术语和事实。二分查找、归并排序或数组访问的复杂度，O、Ω 和 Θ 的含义，什么是递归。
• 中等：应用概念。一段代码的复杂度、要解的递推式、n 加倍时时间如何变化、哪个算法适合某项任务。
• 困难：情形与分析。主定理、快速排序的最坏情况、贪心与动态规划的比较，以及 P、NP 和 NP 完全这几个类。

P 包含可以在多项式时间内解决的问题。NP 包含其解可以在多项式时间内验证的问题。P 中的每个问题都在 NP 中；P = NP 是否成立仍然未知。