算法分析入门：从循环计数到渐进增长与贪心证明
插画：原神官方
一段代码执行得快不快，可以用秒表测量；输入规模扩大十倍之后，它还是否高效，则需要分析工作量怎样增长。
例如，“排序花费 $O(n\log n)$”描述的是输入规模与工作量的关系。理解这个结论，可以从三个问题开始：$n$ 如何确定，操作次数如何计算，以及 $O$ 怎样把具体次数概括成增长上界。
本文沿着三个相互衔接的主题展开：
- 把渐进符号翻译成带有常数和门槛的不等式。
- 比较两个函数在输入不断增大时的增长速度。
- 把一维覆盖问题建模，并说明贪心选择为什么不会损失最优解。
0. 从算法设计走向算法分析
上一篇《算法设计与分析入门》介绍了问题建模与几类代表性算法。这一篇从最基础的操作计数开始，把分析这些算法所使用的数学语言逐步建立起来。
各部分之间的关系如下：
| 阶段 | 阅读内容 | 读完应能回答 |
|---|---|---|
| 明确研究对象 | 上一篇第1至2节：问题、算法、程序与输出形式 | 输入和目标是什么？ |
| 再学分析语言 | 本文第1至6节 | 怎样数步骤、读渐进符号、组织证明？ |
| 练习比较增长率 | 本文第7至8节 | 为什么开根、取对数后更容易比较？ |
| 开始证明算法 | 本文第9至11节 | 为什么一个局部选择能属于某个最优解？ |
| 继续学习 | 上一篇第5节之后的进阶内容 | 怎样分析动态规划和图算法？ |
集合的“属于”和“包含”，可先看集合与子集；指数与对数的运算规则，可回看对数与指数。本文只补上它们在算法分析中的用法。
1. n 是输入规模，T(n) 是随规模变化的工作量
假设输入是一个长度为 $n$ 的数组，要求找最大元素：
def maximum(values):
if not values:
raise ValueError("Expected a nonempty list")
best = values[0]
for i in range(1, len(values)):
value = values[i]
if value > best:
best = value
return best当数组有5个元素时，比较4次；有100个元素时，比较99次。如果只统计 value > best 的执行次数，就有：
注意这里统计的是一种操作的次数，不是所有机器指令的精确总数。做复杂度分析前，要说清楚采用的模型和统计对象。
本文先采用常见的简化模型：一个机器字内的比较、加法和数组索引，视为常数时间。任意精度大整数的乘法不能无条件视为常数时间；课件第42页专门按整数位数分析这一点。
这段实现按下标读取数组，只保存下标、当前值和当前最大值，使用常数额外空间。
最坏情况与平均情况不是同一个函数
线性查找一个目标时：
- 第一个位置就找到，可能只比较1次。
- 最后才找到，或根本不存在，可能比较 $n$ 次。
固定输入规模，把所有合法输入里最慢的工作量作为 $T_{\mathrm{worst}}(n)$，这才是最坏情况函数。平均情况还需要指定输入的概率分布，不能直接理解成“最好加最坏再除以2”。
$O$ 和 $\Theta$ 都能描述最坏情况或平均情况。它们本身不决定讨论的是哪一种情况。2. 先数循环次数，再写复杂度
2.1 一层循环与顺序执行
重复 n 次：做一次比较
再重复 n 次：做一次比较比较总次数是 $n+n=2n$，不是 $n^2$。顺序执行的工作量相加。
2.2 两层循环不一定恰好是 n² 次
for i = 1, ..., n:
for j = 1, ..., i:
做一次操作当 $n=4$ 时，四轮分别做1、2、3、4次，总共10次。
一般情况下：
$$ C(n)=\sum_{i=1}^{n}i=\frac{n(n+1)}{2}=\frac12n^2+\frac12n $$这里的 $\sum$ 只是“把每一轮次数相加”的缩写。次数不是恰好 $n^2$，但与 $n^2$ 同阶。第4节再给“同阶”一个严格定义。
2.3 为什么反复翻倍会出现 log n
从1开始，每轮翻倍，直到大于 $n$：
1, 2, 4, 8, ..., 2^k做到第 $k$ 次翻倍时，数值是 $2^k$。能继续处理的条件是 $2^k\le n$，也就是 $k\le\log_2 n$。
因此，对正整数 $n$，访问这些数值的次数是 $\lfloor\log_2 n\rfloor+1$。例如 $n=16$，访问1、2、4、8、16，共5次。下取整符号表示向下取整。
折半查找不断把候选范围缩小一半，同样会出现对数；具体算法不在这里重复，可看顺序查找和折半查找。
2.4 用小程序核对计数
def triangular_count(n):
count = 0
for i in range(1, n + 1):
for _ in range(i):
count += 1
return count
def doubling_count(n):
count = 0
value = 1
while value <= n:
count += 1
value *= 2
return count
for n in (1, 4, 16):
triangle = triangular_count(n)
doubling = doubling_count(n)
assert triangle == n * (n + 1) // 2
assert doubling == n.bit_length()
print(n, triangle, doubling)输出为：
1 1 1
4 10 3
16 136 5这个程序用于核对有限样例；一般公式仍需由求和或不等式推出，不能只靠测试归纳结论。
3. 为什么不能只比较某一个 n 的数值
考虑两种工作量：
$$ A(n)=100n,\qquad B(n)=n\log_2 n $$当 $n=16$ 时，前者是1600，后者是64，B 更少。但当 $n>2^{100}$ 时，$\log_2 n>100$，A 反而更少。
所以渐进分析关注的是：当 n 足够大后，工作量以什么速度增长，而不是宣称在所有规模上某种算法都更快。常数在实际运行中仍然重要，只是在讨论增长阶时被统一吸收。
对照一下翻倍的效果：
| 工作量 | n 变成 2n 后，与原来的比值 |
|---|---|
| $n$ | 2 |
| $n^2$ | 4 |
| $n^3$ | 8 |
| $2^n$ | $2^n$，不是固定常数 |
多项式时间通常指关于输入长度有某个固定次数的多项式上界。它不保证实际一定快，也不能把指数里的 $n$ 当成固定常数。
4. O、Ω、Θ：先看不等式，再记名字
下面讨论最终非负的函数；涉及比值时，还要求分母最终为正。“最终”表示从某个门槛开始，对后面所有整数 $n$ 都成立。
4.1 O：能否用常数倍从上面压住
$$ f\in O(g) \quad\Longleftrightarrow\quad \exists c>0,\ \exists n_0,\ \forall n\ge n_0:\quad 0\le f(n)\le c g(n) $$逐字翻译：能找到一个固定倍数 $c$ 和一个起点 $n_0$，使得后面的 $f(n)$ 始终不超过 $c g(n)$。
例如 $f(n)=5n^2+3n$。当 $n\ge1$ 时，$3n\le3n^2$，因此：
$$ 5n^2+3n\le8n^2 $$取 $c=8,n_0=1$，就证明了 $f\in O(n^2)$。常数不必选得最小，但不能随 $n$ 改变。
如果为了证明 $n^2\in O(n)$ 而取 $c=n$，就违反了定义：这不是固定常数。
4.2 Ω：能否用常数倍从下面托住
$$ f\in\Omega(g) \quad\Longleftrightarrow\quad \exists c>0,\ \exists n_0,\ \forall n\ge n_0:\quad 0\le c g(n)\le f(n) $$同一个例子里，$5n^2\le5n^2+3n$，所以取 $c=5,n_0=1$ 即可证明 $f\in\Omega(n^2)$。
4.3 Θ：上下同时夹住
$$ f\in\Theta(g) \quad\Longleftrightarrow\quad \exists c_1,c_2>0,\ \exists n_0,\ \forall n\ge n_0:\quad 0\le c_1g(n)\le f(n)\le c_2g(n) $$合并刚才两条不等式：
$$ 5n^2\le5n^2+3n\le8n^2\qquad(n\ge1) $$所以 $5n^2+3n\in\Theta(n^2)$。这就是“同阶”的严格含义。
4.4 小 o 与小 ω：严格慢于或快于
分母最终为正时，可以用比值记忆：
$$ f\in o(g)\iff\lim_{n\to\infty}\frac{f(n)}{g(n)}=0, \qquad f\in\omega(g)\iff\lim_{n\to\infty}\frac{f(n)}{g(n)}=+\infty $$例如 $n\in o(n^2)$，因为比值为 $1/n\to0$；但 $3n$ 不属于 $o(n)$，因为比值恒为3。
$O$ 给出增长上界，小 o 则把“严格增长得更慢”表达得更精确。5. f ∈ O(g) 与 O(f) = O(g) 不是同一句话
$O(g)$ 是一组函数组成的集合。$f\in O(g)$ 表示 f 是其中一个成员；$O(f)=O(g)$ 表示两个函数集合完全相同。这和“3属于整数集合”与“两个集合相等”的区别一样。课件也提醒，常见写法 $f(n)=O(g(n))$ 中的等号是习惯记法，不是普通数值等式。
例如：
$$ n\in O(n^2),\qquad\text{但}\quad O(n)\ne O(n^2) $$因为二次函数属于右边的集合，却不属于左边的集合。
5.1 证明集合相等，需要两个方向
先用一个具体例子说明：
$$ O(5n^2+3n)=O(n^2) $$第一步，证明左边包含于右边。任取 $h\in O(5n^2+3n)$。按定义，存在固定常数 $a>0$ 和门槛 $N$，在 $n\ge N$ 时有 $0\le h(n)\le a(5n^2+3n)$。于是当 $n\ge\max(N,1)$：
$$ 0\le h(n)\le a(5n^2+3n)\le8a n^2 $$新常数取 $8a$，说明 $h\in O(n^2)$。
第二步，证明右边包含于左边。任取 $h\in O(n^2)$，存在 $b>0$ 和门槛 $M$，使得 $0\le h(n)\le bn^2$。当 $n\ge\max(M,1)$ 时：
$$ 0\le h(n)\le bn^2\le b(5n^2+3n) $$所以 $h\in O(5n^2+3n)$。两个方向都成立，集合才相等。
5.2 为什么两项之和与较大项具有相同增长阶
把具体的多项式推广为最终非负的函数 f、g，令 $m(n)=\max\{f(n),g(n)\}$。对非负数，较大的一项不超过两项之和，而两项之和不超过较大项的两倍：
$$ m(n)\le f(n)+g(n)\le2m(n) $$任取 $h\in O(f+g)$。从某个门槛开始，有 $0\le h(n)\le c(f(n)+g(n))\le2c m(n)$，所以 $h\in O(m)$。
反过来，任取 $h\in O(m)$。从某个门槛开始，有 $0\le h(n)\le d m(n)\le d(f(n)+g(n))$，所以 $h\in O(f+g)$。两个方向使用的门槛均再与非负性成立的门槛取最大值，就得到：
$$ O(f+g)=O(\max\{f,g\}) $$这也解释了分析顺序执行代码时，为什么可以用增长较快的部分概括总工作量。
这里非负性不能省略。若随意允许一正一负，例如 $f(n)=n,g(n)=-n$，两者相加会抵消，上面的夹逼关系就不成立。
也不需要先猜 f 和 g 谁最终更大；它们可能交替更大。$\max$ 是对每一个 n 取较大值，不是提前固定选一个函数。
6. 把数学证明写成可检查的步骤
6.1 “存在”与“任意”的次序
$O$ 的定义顺序是：先找到固定的 $c,n_0$，再保证所有 $n\ge n_0$ 都满足不等式。不能对每个 n 临时选一个 c，也不能只检查100、1000、10000这几个数。可以把定义想成一份承诺：“从这个门槛以后，同一把尺子始终适用。”
若两个条件分别从 $N_1$ 和 $N_2$ 开始成立，合并时取 $\max(N_1,N_2)$，就能保证两个条件同时可用。
6.2 归纳法：先做最小情形，再接下一步
以第2节求和式为例：
- 基础：$n=1$ 时，两边都等于1。
- 假设：前 $k$ 项之和是 $k(k+1)/2$。
- 递推：再加上 $k+1$，得到 $(k+1)(k+2)/2$，恰好是下一规模的公式。
因此公式对所有正整数成立。贪心算法里“处理一次后，对剩余问题重复”的论证，也常用这种结构，但要先证明剩余问题确实具有相同形式。
6.3 反例、测试和证明的分工
一个合法反例足以推翻“该策略对所有输入都最优”。很多成功样例，却不足以证明该策略永远正确。
还要分清三件事：
| 要证明什么 | 需要回答什么 |
|---|---|
| 可行性 | 算法输出满足所有约束吗？ |
| 最优性 | 有没有任何合法方案比它更好？ |
| 复杂度 | 排序、扫描、存储分别花多少资源？ |
“覆盖了所有房屋”只说明可行，还没有证明基站数最少；“程序跑得快”也不能替代最优性证明。
7. 增长率比较：先化简，再看比值
这一节的 $\log n$ 统一表示 $\log_2 n$。若对数底只差固定常数且都大于1，通常不改变这里的渐进比较结果。
7.1 根号、常数和多项式
先看一个训练用函数：
$$ \sqrt{5n}=\sqrt5\,n^{1/2}\in\Theta(n^{1/2}) $$根号里面的5变成了固定系数，不会把它变成一次函数。类似地，$n+30\in\Theta(n)$。比较固定次幂时，次数较小的一方增长得更慢：
$$ \frac{n^a}{n^b}=\frac1{n^{b-a}}\to0\qquad(a<b) $$7.2 对数的固定次幂，慢于任何固定正幂
一个常用结论是，对固定常数 $k>0,\varepsilon>0$：
$$ \frac{(\log n)^k}{n^\varepsilon}\to0 $$为什么？令 $t=\log_2 n$，则分子变成 $t^k$，分母变成 $2^{\varepsilon t}$。这就变成“固定次数的多项式慢于固定底数大于1的指数函数”。
后一结论可以这样理解：对整数 t，取一个固定整数 $q>k$，二项式展开中 $(1+d)^t$ 至少包含 $\binom tq d^q$ 这一项，其中 $d=2^\varepsilon-1>0$。固定 q 时这一项的量级是 $t^q$，已经比 $t^k$ 快；对非整数 t 用相邻整数夹住即可。
例如，比较 $n(\log n)^2$ 与 $n^{3/2}$，先约去共同的 n，只需比较 $(\log n)^2$ 和 $n^{1/2}$。前者更慢。
如果还没学过极限运算，可以先掌握这个比较规则；需要形式化时，再把上述替换与不等式展开。
7.3 多项式与固定底数的指数
对固定 $a>0,b>1$，有 $n^a\in o(b^n)$。这里强调“固定”：$n^{\log n}$ 的指数随 n 变化，不能直接当成某个固定次数的多项式。
比较两个指数，例如 $3^n$ 和 $7^n$，可看比值 $(3/7)^n\to0$。它们虽然都叫指数函数，增长率仍不同。
7.4 把比较规则串成一个完整例子
把下面六个函数按严格增长率排列，可得到：
$$ \sqrt{5n}\ \prec\ n+30\ \prec\ n(\log n)^2\ \prec\ n^{3/2}\ \prec\ 3^n\ \prec\ 7^n $$这里 $u\prec v$ 表示 $u\in o(v)$。逐对解释，而不是只写一条顺序：
- 第一对化简为半次幂与一次幂。
- 第二对约去 n 后，比较常数量级与趋于无穷的对数平方。
- 第三对用“对数固定次幂慢于固定正幂”。
- 第四对用“固定次数多项式慢于固定底数指数”。
- 第五对看底数比值的 n 次幂。
如果只要求按相邻的 $O$ 关系排序，则允许出现同阶函数；同阶函数之间可以互相构成上界。
8. 指数里还有指数，应该怎样读
函数排序的困难往往来自括号读错，而不是比较方法不足。
8.1 同底指数，可以先比较指数
对最终为正的函数，若 $A(n)-B(n)\to-\infty$，那么：
$$ \frac{2^{A(n)}}{2^{B(n)}}=2^{A(n)-B(n)}\to0 $$因此比较很大的指数函数时，可以把问题转移到指数上。不要真的把天文数字算出来。
8.2 取对数是比较工具，不是替换 O 记号的规则
对正数，底数大于1的对数保持大小顺序，但不能随意声称“两个函数的对数同阶，所以原函数同阶”。
例如 $\log_2(2^n)=n$、$\log_2(4^n)=2n$，对数同阶；原函数的比值却是 $2^{-n}\to0$。取对数之后还应回到原比值，或比较指数差。
8.3 把复杂函数改写成统一的形式
以 $t=\log_2 n$ 为辅助变量，可以把几类常见表达式改写为更容易比较的形式：
| 表达式 | 正确读法或等价形式 | 接下来可以问自己 |
|---|---|---|
| $2^{\sqrt{\log_2 n}}$ | $2^{\sqrt t}$，不是 $2\sqrt{\log_2 n}$ | 与 $n^a=2^{at}$ 比，指数差如何变化？ |
| $n(\log n)^3$ | n 乘对数的三次幂 | 与另一个 n 的幂比较时，能否先约去 n？ |
| $n^{\log_2 n}$ | $(2^t)^t=2^{t^2}$ | 不同候选函数也写成同底指数后，比较哪两项？ |
| $2^{n^2}$ | 指数是 $n^2$ | 不要误读成 $(2^n)^2=2^{2n}$ |
| $2^{2^n}$ | 指数本身是 $2^n$ | 与上一行比较时，可否先比较两个指数？ |
图中 $n=3$ 的数值只用于区分表达式，不是渐进排序依据。
8.4 一份可重复使用的排序流程
- 写清对数底数与指数括号，先把根号变成分数幂。
- 去掉固定系数，找出明显的同阶项。
- 相邻两项能约去公共因子时，先约去。
- 指数复杂时，统一底数，或令 $t=\log_2 n$。
- 对最终顺序逐对给出比值、指数差或已证明的比较规则。
数值表和程序可以排查抄写错误，但有限范围内的大小关系不证明渐进关系；过大的指数还容易让浮点数溢出。
9. 从文字题变成一维覆盖模型
用一个基站覆盖问题，把问题建模、运行时间与最优性证明联系起来。它与上一篇的区间调度不同：区间调度是从已有任务中选一些，覆盖问题是决定基站放在哪里。
9.1 输入、输出和目标分别是什么
把道路看成数轴，房屋坐标为 $x_1,\ldots,x_n$；先排序，使 $x_1\le\cdots\le x_n$。允许基站放在道路的任意位置，不要求恰好在某栋房屋处。
若覆盖半径为 $r>0$，放在 b 的基站覆盖：
$$ [b-r,b+r] $$房屋 x 被覆盖，当且仅当 $|x-b|\le r$，也就是距离不超过 r。这里是闭区间，恰好距离 r 也算覆盖；不要直接沿用调度题的半开区间约定。
输出是一组基站位置，约束是每栋房屋至少被覆盖一次，目标是基站数量最少。半径 r 对应总覆盖长度 $2r$，不能混淆两者。
如果道路是有限区间 $[L,R]$，还应要求基站位置在道路内；覆盖区间超出道路的部分不影响房屋是否被覆盖。若题目改成“只能从给定候选站址中选择”，则已经改变了模型，不能直接照搬同一放置规则。
9.2 先做一个半径为2的小例子
设道路为 $[0,12]$，房屋坐标为：
$$ 1,\ 2,\ 4,\ 5,\ 9,\ 10 $$当前最左边未覆盖的房屋在1。为了覆盖它，基站位置必须在 $[-1,3]$ 与道路的交集中。把基站放在3，覆盖 $[1,5]$，前四栋房屋都被覆盖。
下一个未覆盖的房屋在9，把下一站放在11，覆盖 $[9,13]$，剩余房屋也被覆盖。虽然覆盖范围到13，基站本身在道路内的11，放置合法。
| 轮次 | 最左未覆盖房屋 | 本轮基站位置 | 本轮新覆盖房屋 |
|---|---|---|---|
| 1 | 1 | 3 | 1、2、4、5 |
| 2 | 9 | 11 | 9、10 |
本例确实至少需要两站：位置1和9相距8，大于一个基站能同时覆盖的最大两点距离4。因此两站不仅可行，也达到下界。
但这个下界只证明了当前例子最优。对任意房屋输入都正确，还需要下一节的一般论证。
10. 从局部选择到交换论证
10.1 每轮的贪心选择是什么
记 x 为当前最左未覆盖的房屋。任何覆盖 x 的基站 q，都必须满足：
$$ x-r\le q\le x+r $$暂时忽略道路右端限制，候选位置 $b=x+r$ 是仍能覆盖 x 的最右位置。它的覆盖范围为 $[x,x+2r]$。
直觉是：左侧房屋已经处理完，接下来希望尽量向右覆盖。注意这里说的是最左未覆盖，不是每轮重新从所有房屋里选最左一栋。
10.2 交换论证究竟要检查哪两条不等式
假设某个最优的剩余方案里，有一站 q 覆盖 x。尝试把 q 换成 b。
对于原来被 q 覆盖、目前尚未处理的房屋 y：
- 因为 x 最靠左，$y\ge x=b-r$。
- 因为 q 覆盖 y，且 $q\le b$，有 $y\le q+r\le b+r$。
合起来得到 $b-r\le y\le b+r$。也就是说，替换后不会丢掉任何原本由 q 覆盖的未处理房屋，站数也没有增加。
这一步真正证明的是：至少存在一个最优方案，包含我们这次的候选选择。 不要求所有最优方案都长这样，也不要求整份最优方案唯一。
这与上一篇区间调度的交换论证结构相同：替换最优方案的一部分，检查可行性不坏、目标值不差，然后处理剩余问题。两题具体替换方向不同，不能只背“都向右选”或“都选最早结束”。
10.3 为什么还要补上归纳或剩余问题论证
完成一次安全交换后，去掉新站已经覆盖的房屋，剩余的仍是同样的一维覆盖问题。
记当前房屋集合为 X，新站覆盖后剩下的集合为 $X'$，最少站数记为 $K(X)$。交换后得到一个包含 b 的最优方案，其余站覆盖了 $X'$，所以 $K(X')\le K(X)-1$。
另一方面，用 b 加上 $X'$ 的最优覆盖，就能覆盖 X，因此 $K(X)\le1+K(X')$。两个方向合起来：
$$ K(X)=1+K(X') $$没有房屋时，算法返回0站，显然最优。每轮至少覆盖当前的房屋 x，因此剩余房屋数量严格减少。按房屋数量归纳，后续选择得到 $K(X')$ 个站，本轮加1就得到 $K(X)$ 个站，整个算法最优。
10.4 道路端点与易错反例
若道路右端是 R，且 $x+r>R$，取 $b=\min(x+r,R)=R$。原方案的合法站址满足 $q\le R=b$，同时 $b-r\le x$，所以交换时仍有 $b-r\le x\le y\le q+r\le b+r$。端点截断后，证明依然成立。
训练例中，若每次直接把基站放在最左未覆盖房屋的位置，就会放在1、4、9，需要3站。它覆盖了全部房屋，却不如3、11的两站方案。这正是“可行”不等于“最优”的小反例。
11. 把算法、证明与复杂度连起来
对于任意固定覆盖半径 r，可以将覆盖算法整理成以下几个部分：
| 部分 | 你需要自己写清楚的内容 |
|---|---|
| 建模 | 房屋是数轴上的点，覆盖边界是否包含，基站允许放在哪里 |
| 算法 | 如何排序；当前处理哪栋房屋；新站位置如何确定；怎样跳过已覆盖房屋 |
| 终止性 | 每轮是否至少处理掉一栋未覆盖房屋 |
| 可行性 | 每次放站是否覆盖当前房屋；结束后是否有遗漏 |
| 安全选择 | 任意最优剩余方案中，覆盖当前房屋的站可否替换成候选站 |
| 全局最优性 | 如何把一次安全替换延续到所有轮次 |
| 复杂度 | 排序与扫描分别花多少时间，指针是否只向前移动 |
扫描时不需要反复删除数组元素或每轮从头查找。把房屋排序后，维护“下一个未覆盖房屋”的下标，覆盖一批就向前推进。每栋房屋只被推进越过一次，扫描本身是 $O(n)$；若输入无序且使用比较排序，总时间为 $O(n\log n)$。
这里的总上界包括排序，而不是“有个 while 循环所以复杂度就是线性”。额外空间还要看排序实现、是否复制输入，以及是否把输出站址数组计入；不能仅凭扫描只用一个下标，就说整个程序只占常数空间。
具体排序实现可回看排序文章。
Python实现
下面将道路端点作为参数传入，使用同一个向前移动的下标扫描房屋：
def cover_houses(houses, radius, left, right):
if radius <= 0 or left > right:
raise ValueError("Expected a positive radius and a valid road")
points = sorted(houses)
if any(x < left or x > right for x in points):
raise ValueError("Every house must be on the road")
stations = []
i = 0
while i < len(points):
station = min(points[i] + radius, right)
stations.append(station)
covered_until = station + radius
while i < len(points) and points[i] <= covered_until:
i += 1
return stations
assert cover_houses([1, 2, 4, 5, 9, 10], 2, 0, 12) == [3, 11]
assert cover_houses([9, 10], 2, 0, 10) == [10]
assert cover_houses([1, 5], 2, 0, 12) == [3]
assert cover_houses([], 2, 0, 12) == []
print(cover_houses([1, 2, 4, 5, 9, 10], 2, 0, 12))输出为 [3, 11]。循环里的 <= 对应闭区间覆盖，min 对应道路右端的限制。这里 sorted 创建了新列表，输出也保存了所有站址，因此这份实现使用 $O(n)$ 额外空间。
12. 练习与解析
用下面几个问题串联本文的计数、渐进分析与覆盖证明。
自测1：顺序与嵌套
一段代码先做 n 次操作，再做 $n^2$ 次操作；另一段代码外层 n 次、内层 $n^2$ 次。两者的总次数与紧确阶分别是什么？
自测2：自己选常数
证明 $7n+20\in O(n)$，明确给出一组 $c,n_0$。再说明为什么它属于 $\Omega(n)$。
自测3：函数成员与集合相等
已知 $n\in O(n^2)$，能否推出 $O(n)=O(n^2)$？怎样用一个函数否定集合相等？
自测4：逐对说明增长率
比较 $n(\log_2 n)^4$ 与 $n^{6/5}$。再比较 $2^{3n}$ 与 $2^{n^2}$。只写“后一个更快”不够，指出约分后比较什么。
自测5：覆盖端点
半径为2，基站在3，房屋在1、5、6。分别是否被覆盖？为什么不能用半开区间去掉5？
自测6：交换证明是否完整
有人写：“我的站比原最优方案的站更靠右，所以一定最优。”这句话还缺少哪些检查？若道路为 $[0,10]$、当前最左未覆盖房屋为9、半径为2，新站应放在哪里？
参考检查
- 顺序执行是 $n+n^2\in\Theta(n^2)$；完全嵌套是 $n^3\in\Theta(n^3)$。
- 例如 $n\ge1$ 时，$7n+20\le27n$，取 $c=27,n_0=1$；下界可取 $7n\le7n+20$，所以它实际上属于 $\Theta(n)$。
- 不能。$n^2$ 属于右侧集合，不属于左侧集合。
- 第一对比值化为 $(\log_2 n)^4/n^{1/5}\to0$；第二对比值是 $2^{3n-n^2}\to0$。
- 1和5被覆盖，6没有；题目说距离不超过半径，包含两个端点。
- 还要检查替换后站址合法、未处理房屋不会失去覆盖、站数不增加，以及后续剩余问题如何得到最优解。端点例中应考虑放在10，而不是道路外的11。
也可以让 AI 助手按这6类知识逐题提问：先给出自己的推导，再检查常数是否固定、集合证明的两个方向是否齐全，以及覆盖算法的可行性和最优性是否分别说明。
13. 后续学习与参考资料
在操作计数、渐进分析和贪心证明的基础上，可以继续学习：
- 先学习循环不变式，并用简单扫描算法练习初始化、保持与终止。
- 再读上一篇第4节的区间调度，比较它与覆盖问题的交换论证。
- 学习递归与分治，之后再读课件第41至55页的整数乘法、递归树与矩阵乘法。
- 理解“同一个子问题被反复计算”后，再读上一篇第5节的带权调度，进入动态规划。
- 在图算法与判定问题的基础上，学习多项式归约与 NP 完全性。
本文依据的材料是《Design and Analysis of Algorithms》第二讲 Basics of algorithm design & analysis，以及《第一次作业》。页码按 PDF 页序：
| 材料范围 | 本文取用的知识 |
|---|---|
| 02Analysis 第2至13页 | 输入规模、最坏情况、工作量增长、多项式与指数 |
| 第15至26页 | 渐进记号、集合含义、常用比较关系与集合等式证明 |
| 第30至38页 | 贪心策略、区间调度与交换论证 |
| 第41至83页 | 分治与动态规划等后续主题；本文仅标注学习顺序，不重复展开 |
| 第一次作业第1至2页 | 函数增长率比较与一维基站覆盖的练习主题 |
本文的循环计数、数值训练例、半径为2的覆盖例、图例和自测为补充讲解。已有文章中的完整区间调度、带权调度程序和图问题例子通过链接引用，不再重复书写。
