13. Asymptotics I

至此，CS61B 中关于 Java 语法的部分就全部结束了，下面正式进入数据结构与算法的部分，也是这门课的核心内容。

一、简化模型以获得 Order of Growth

1. 考虑最坏情况

对程序中某个操作进行计数，并将其表示为关于 $N$ 的运行时间函数。
通常只考虑最坏情况（最大执行次数），保留主导项：

2. 选择代表性操作（Cost Model）

Cost Model：选取一个操作，其执行次数用于近似整体运行时间。

• 该选择通常依赖经验和直觉
• 保留该操作，忽略其他操作

例如，仅保留 increment：

3. 忽略低阶项

仅保留增长最快的项：

4. 忽略常数因子

去除乘法常数：

最终得到 $N^2$，这就是 order of growth：描述当 $N \to \infty$ 时，运行时间随 $N$ 的增长速度。

例 1

说明：

• $\frac{1}{N} \to 0$，仅保留常数项
• 常数被忽略后记为 1
• 其他表达式同理

二、简化分析（图像法）

通过图像或结构直接分析操作次数（如 ==）：

设 $C$ 为操作次数，可通过等差数列求得，再简化得到：

• Order of Growth： $N^2$

或者可以使用更快速的“图像法”，上面图中蓝色三角形的面积是 $\frac{1}{2} N^2$，化简后即可得到答案。

三、Big-Theta（Θ）

设：

• $R(N)$：运行时间函数
• $f(N)$：order of growth

则：

$R(N) \in \Theta(f(N))$

即存在常数 $k_1, k_2$，使得：

$k_1 \cdot f(N) \le R(N) \le k_2 \cdot f(N)$

本质：

• Θ 用于精确描述增长级别（同阶）

四、Big-O Notation（O）

Big-O 表示上界（≤）：

满足：

$R(N) \le k_2 \cdot f(N)$

总结

给定程序运行时间函数 $R(N)$，通常关注其增长趋势而非精确值。

分析步骤：

1. 选取一个代表性操作，记其的执行次数记为 $C(N)$
2. 求 $C(N)$ 的 order of growth $f(N)$，即 $C(N) \in \Theta(f(N))$
3. 通常考虑最坏情况
4. 若该操作耗时为常数，则 $R(N) \in \Theta(f(N))$
5. 可用 $O$ 表示上界（代替或补充 Θ）

常见的三个符号总结：

• $R(N)$ 即运行时间函数，表示在输入规模为 $N$ 时的总运行时间
  • 例如 $R(N) = 3N^2 + 2N + 5$
• $C(N)$ 即某个具有代表性的操作（选定的 Cast model）的执行次数
  • 例如 $C(N) = 3N^2 + 2N + 5$
• $f(N)$ 即 order of growth，表示主要增长趋势，经过简化程序忽略低阶项和常数
  • 例如当 $C(N) = 3N^2 + 2N + 5$ 时， $f(N) = N^2$，并且可以表示为 $C(N) \in \Theta(f(N))$