CS61B 课程笔记（Lecture 17 Asymptotics I）

8.2 渐进分析 I · Hug61B

1. 运行时间最小化

• 重要性：程序执行的时间是一个重要属性，程序员的目标之一是最小化程序完成所需的时间（以秒为单位）。

2. 运行时间测量

• 方法：
  • 使用秒表：通过物理或软件秒表测量程序的实际运行时间。优点：实际时间；缺点：依赖于机器和输入。
  • 操作计数：计算特定输入大小所需的操作次数。这是机器独立的分析，但仍然依赖于输入，并不反映代码的实际运行时间。
  • 代数表达式：推导出操作次数与输入大小之间的关系。这能反映算法的扩展性，但不直接告诉你运行时间。

3. 算法扩展性

• 概念：虽然最终关心的是算法的实际运行时间，但通常我们会通过扩展性来比较算法。

• 示例：在旧计算机上向 ArrayList 开头插入的时间可能是 \(R(N) = 0.0001N\) ，其中 N 是列表大小。

• 比较算法：如果有两个算法的运行时间 $ R_1(N) = N^2 $ 和 \(R_2(N) = 5000 + N\) ，我们会认为算法 2 更好，尽管在小 $N $ 时 \(R_1\) 更快。这是因为在性能关键的情况下， \(N\) 较大时更为重要。

4. 简化代数运行时间

• 简化方法：
  1. 选择成本模型：选择一个特定的选项作为成本模型，例如数组访问次数。
  2. 专注最坏情况：如果操作次数在 \(1\) 和 \(2N + 1\) 之间，只考虑 \(2N + 1\) 。
  3. 忽略小输入：将 \(2N + 1\) 视作 \(2N\) 。
  4. 忽略常数缩放因子：将 \(2N\) 视作 \(N\) 。
• 示例：假设一个算法的增量操作在 $ N $ 和 \(2N + 1\) 之间，比较操作在 \(N\) 和 \(4N^2 + 2N + 6\) 之间，则可以认为该算法的运行时间与 $N^2 $ 成正比。

5. 增长阶

• 定义：应用最后三种简化后的结果可以得出一个函数的增长阶。

• 示例：如果 \(R(N) = 4N^2 + 3N + 6\) ，那么 R(N) 的增长阶是 \(N^2\) 。

• 术语：

  • “常数”对应增长阶 $1 $
  • “线性”对应增长阶 \(N\)
  • “二次”对应增长阶 \(N^2\)

6. 简化分析

• 方法：可以提前应用简化，而不是计算所有操作的数量。
• 选择成本模型：一旦选择成本模型，可以：
  • 精确计算：计算操作数量的确切表达式。
  • 直观判断：使用直觉和观察来确定操作数量的增长阶。
• 几何直觉：例如，嵌套的 for 循环中，$ i $ 从 $0 $ 到 $ N \(，\) j $ 从 $ i + 1$ 到 $ N $，形成的图形为一个边长为 $ N$ 的直角三角形，因此运行时间的增长阶为二次。

7. 大 Θ 记号

• 定义：我们说 \(R(N) \in Θ(f(N))\) ，如果存在正的常数 $k_1 $ 和 $ k_2$ ，使得 \(k_1 f(N) \leq R(N) \leq k_2 f(N)\) 。

• 记法：许多作者将其写为 \(R(N) = Θ(f(N))\) 。两者可互换使用。

• 非标准定义：另一个定义是 $R(N) Θ(f(N)) $ 当且仅当 \(\lim_{N \to \infty} \frac{R(N)}{f(N)} = k\) ，其中 k 是某个正常数。这个定义在课堂上不使用。

• 简化 Θ 表达式：在使用 Θ 捕捉函数的渐进扩展时，我们避免不必要的项。例如，虽然 \(4N^2 + 3N + 6 \in Θ(4N^2 + 3N\)) ，我们通常更简单地表示为 \(4N^2 + 3N + 6 \in Θ(N^2)\) 。

• 等价性：大 Θ 与增长阶完全相同。如果 $ R(N)$ 的增长阶为 \(N^2\) ，那么 $R(N) Θ(f(N)) $。