CS61B 课程笔记（Lecture 19 Asymptotics III）

8.4 Ω（Omega）、摊销分析 · Hug61B

1. 大O滥用

  • 定义与误用：
    • 大O符号用来描述算法的上界时间复杂度，通常用于表达最坏情况，但并不完全等同于“最坏情况”。
    • 在讨论算法时，常常看到人们误用大O来表示复杂度的最坏情况，这可能导致误解。
  • 大O的用途总结：
    • 允许在输入不同情况下进行简化声明，不需要具体分析所有情况。
    • 对于某些复杂问题，计算机科学家可能无法提供精确的运行时间，只能给出一个上限。
  • 示例：
    • 在归并排序的时间复杂度分析中，通常我们使用大O来表示其在最坏情况下的复杂度 \(O(n \log n)\)。

2. 摊销分析（直观解释）

  • Grigometh的 urn：
    • Grigometh 是一只恶魔狗，要求你定期献上干草。提供干草的方式有两种：
      • 选择1：每天提供固定的3箱干草。
      • 选择2：随着时间推移，干草需求增加：
        • 第1天：1箱干草（总计1）。
        • 第2天：2箱干草（总计3）。
        • 第4天：4箱干草（总计7）。
        • 第8天：8箱干草（总计15）。
  • 成本比较：
    • 第一个选择需要每天固定的3箱干草，总体成本较高。
    • 第二个选择，虽然初始需求小，但随着时间的推移，平均成本降低。通过计算每天的需求总量可以验证这一点。

3. AList 调整大小与摊销

  • 添加元素的实现：

    • 当调用满的AList的add方法时，需要调整数组的大小，以下是两种实现方式：

    • 实现1（固定增加）：

      1
      2
      3
      4
      5
      6
      7
      public void addLast(int x) {
          if (size == items.length) {
              resize(size + RFACTOR);
          }
          items[size] = x;
          size += 1;
      }

    • 实现2（几何增加）：

      1
      2
      3
      4
      5
      6
      7
      public void addLast(int x) {
          if (size == items.length) {
              resize(size * RFACTOR);
          }
          items[size] = x;
          size += 1;
      }

  • 效率比较：

    • 实现1效率低下，因为每次添加新元素时都需要复制整个数组。
    • 实现2通过几何扩展有效减少了复制次数，性能更好。

4. 运行时间分析

  • 实现2的时间复杂度：
    • 假设 $ RFACTOR = 2$ ，当数组满时，调整大小加倍。
    • 大多数添加操作的时间复杂度为 \(Θ(1)\) ，但调整大小的操作耗时与当前数组大小成线性关系。
  • 摊销分析：
    • 如果将高成本的调整大小操作与低成本的添加操作进行平均，结果发现整体平均添加操作的运行时间为 $ Θ(1)$ 。

5. 摊销分析（严谨解释）

  • 步骤概述：

    1. 选择成本模型：确定分析基础，例如每次操作的运行时间。
    2. 计算第 i 次操作的平均成本。
    3. 证明平均（摊销）成本是有限的。

  • 示例分析：

    • 假设最初ArrayList的长度为1，进行摊销分析。对每次操作进行记录，分析调整大小的成本。
    插入 # 实际成本 \(c_i\) 调整成本 总成本
    0 1 0 1
    1 3 2 4
    2 5 4 9
    3 1 0 10
    ... ... ... ...

  • 结果计算：

    • 对于13次添加，整体成本为44，平均成本为 $ $ 。

6. 潜力概念

  • 潜力函数定义：
    • 每个操作 $ i$ 的实际成本为 \(c_i\) ，摊销成本为 \(a_i\) ，潜力 \(Φ_i\) 表示摊销成本与实际成本之间的差值： \(Φ_i = Φ_{i-1} + a_i - c_i\)
  • 选择摊销成本：
    • 选择合适的 $a_i $ 使得潜力不会变为负值。如果选择常数摊销成本，可以确保算法的长期平均成本控制在合理范围。

7. Grigometh的干草示例

  • 实际成本计算：
    • 实际成本 $ c_i $ 为 Grigometh 每天吃的干草，假设摊销成本固定为3。
天数 (\(i\)) 实际成本 $ c_i$ 摊销成本 $a_i $ 潜力变化 潜力 $Φ_i $
1 1 3 +2 2
2 2 3 +1 3
3 0 3 0 3
4 4 3 -1 5
... ... ... ... ...
  • 潜力管理：
    • 每天放入3箱的摊销成本确保潜力不会为负，从长远来看能够保持干草的盈余。

8. 回到ArrayList调整大小

  • 实际成本分析：
    • 在添加新元素时，实际成本 $ c_i $ 取决于是否需要调整大小，当 $i $ 为2的幂时，成本较高；否则较低。
插入 # 实际成本 \(c_i\) 调整成本 总成本 累计成本
0 1 0 1 1
1 3 2 4 4
2 5 4 9 9
3 1 0 10 10
... ... ... ... ...
  • 平均成本分析：
    • 通过引入潜力的概念，确保随着元素数量增加，平均运行时间保持在 $ Θ(1) $。