01先把问题说具体
程序做 3n+2 次操作,为什么写 O(n)?又为什么 O(n²) 也没错,却通常不是好答案?
02一步步得到方法
把符号读成一句完整的话
f(n)=O(g(n)) 表示存在常数 c>0 和阈值 n₀,使所有 n≥n₀ 都满足 f(n)≤c·g(n)。它表达最终的上界,既不表示精确次数,也不自动表示最坏情况。
对 f(n)=3n+2,n≥1 时有 3n+2≤5n,因此可取 c=5、n₀=1。与此同时 f(n)≥3n,所以也有 Ω(n),上下同阶合起来就是 Θ(n)。
为什么先写输入条件
线性搜索的最好情况是第一个位置命中,最坏情况是不存在目标。二者分别是 Θ(1) 与 Θ(n),但算法名称没有改变。平均情况必须说明目标和输入如何分布。
两个独立循环分别扫描 n 和 m 个元素,成本为 Θ(n+m),不能无理由只留 n。两层循环若内层每次执行 m 次,则是 Θ(nm)。当 m 固定为 10,才可简化为 Θ(n)。
渐近结论如何用于选择
1000n 与 n² 在小规模下可能由后者更快,渐近分析只说明增长趋势。实际比较还要看常数、内存访问、输入分布和实现;先排除明显不可承受的增长,再对真实工作负载测量。
03把一个小例子完全算清楚
比较 n=1、10、100 时 f(n)=3n+2,与线性上界 5n。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| n=1 | f=5,5n=5 | 上界恰好相等 |
| n=10 | f=32,5n=50 | 仍落在线性上界以内 |
| n=100 | f=302,5n=500 | 比例趋近 3,不会无限增大 |
窄屏可左右滑动表格,阅读完整计算与理由。
这里给出了一个适用于所有 n≥1 的不等式证明;几个样本只能辅助理解,不能代替证明。
04为什么这个方法成立
- 对 n≥1,常数 2≤2n,因此 3n+2≤5n。
- 对 n≥1,3n+2≥3n,因此存在同阶下界。
- 上下界同时成立得到 Θ(n);也属于 O(n²),只是上界不够紧。
05把推导翻译成代码
Python · 可独立运行的教学实现
def operation_count(n):
assert n >= 0
return 3 * n + 2
def pair_count(n):
count = 0
for i in range(n):
for j in range(i + 1, n):
count += 1
return count逐个理解关键决定
range(i + 1, n)- 内层次数依次为 n−1、n−2、…、0;不能把每轮都当作 n 次来求精确总数。
count += 1- 这里数的是配对次数,不是墙钟时间。总计 n(n−1)/2,n≥2 时为 Θ(n²)。
06时间、空间与实现范围
求一个闭式表达式在固定宽度算术模型中是 O(1);被表达式描述的另一个程序仍可能耗时 O(n)。
pair_count 枚举所有无序位置对,时间 Θ(n²),计数器额外空间 O(1)。
07改变条件,检查哪里会出错
看到 O 就说最坏情况
先定义被分析的函数,例如 T_worst(n),再给它的渐近上界。
两个嵌套循环必为 O(n²)
若内层每次折半或总指针只前进 n 次,必须按实际执行次数求和。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
5n²+7n+3 的紧界是什么?
需要一点提示
找增长最快的一项,并给上下界。
查看解析与答案
Θ(n²)。n≥1 时 n²≤5n²+7n+3≤15n²。
一个循环将 i 从 1 每次乘 2,直到 i≥n,执行几次?
需要一点提示
写出 1、2、4、8。
查看解析与答案
约 ceil(log₂n) 次,因此 Θ(log n),不是 Θ(n)。
输入有 n 个字符串,每个长 m,逐个完整比较需要什么成本?
需要一点提示
一次字符串比较并不总是常数。
查看解析与答案
最坏要检查 nm 个字符,时间 O(nm)。若找到失配可提前停,最好情况不同。