均摊复杂度

一、为何需要 均摊复杂度？

在信息竞赛中，我们通常用最坏时间复杂度来衡量算法的效率。但对于某些数据结构和算法，最坏情况发生的频率极低，或者连续多次操作的总时间远小于单次最坏时间乘以操作次数。

举个最常见的例子：C++ STL 中的 vector 的 push_back 操作

• 当数组还有剩余空间时，push_back 只需要 $O(1)$ 时间
• 当数组已满时，需要重新分配一块更大的内存（通常是原来的 $2$ 倍），并将所有元素复制过去，这需要 $O(n)$ 时间

如果只看最坏情况，我们会认为 push_back 是 $O(n)$ 的操作，$n$ 次 push_back 的总时间是 $O(n^2)$。但实际上，我们知道 $n$ 次 push_back 的总时间只有 $O(n)$.

这就是均摊复杂度要解决的问题：它分析的是一系列操作的平均时间，而不是单个操作的最坏时间。

均摊分析（Amortized Analysis）是一种用于分析算法和动态数据结构性能的技术．它不仅仅关注单次操作的成本，还通过评估一系列操作的平均成本，为整体性能提供更加准确的评估．均摊分析不涉及概率，且只能确保最坏情况性能的每次操作耗费的平均时间，并不能确认系统的平均性能．在最坏情况下，均摊分析通过将高成本操作的开销分摊到低成本操作上，确保整体操作的平均成本保持在合理范围内．

二、均摊复杂度的基本概念

定义：对于一个数据结构的 $n$ 个操作，设第 $i$ 个操作的实际时间为 $c_i$，那么这 $n$ 个操作的均摊时间就是总时间除以 $n$.

$$均摊时间=\frac{\sum_{i=1}^{n}{c_i}}{n}$$

核心思想：允许某些操作花费较多时间，但保证在足够多的操作中，这些昂贵操作的成本会被其他廉价操作 "分摊" 掉。

重要性质：如果一个操作的均摊时间是 $O (f (n))$，那么任意 $k$ 个这样的操作的总时间一定是 $O (k・f (n))$。

均摊分析通常采用三种主要分析方法：聚合分析、记账分析和势能分析．

三、三种常用的均摊分析方法

方法一：聚合分析（Aggregate Analysis）

思路：直接计算 $n$ 个操作的总时间 $T(n)$，然后每个操作的均摊时间就是 $\frac{T(n)}{n}$。

经典例子：动态数组的 push_back

假设我们从空数组开始，每次扩容时容量翻倍。我们来计算 $n$ 次 push_back 的总时间：

• 第 $1$ 次 p_b：数组大小从 $0→1$，复制 $0$ 个元素，时间 $1$
• 第 $2$ 次 p_b：数组大小从 $1→2$，复制 $1$ 个元素，时间 $2$
• 第 $3$ 次 p_b：数组已有空间，时间 $1$
• 第 $4$ 次 p_b：数组大小从 $2→4$，复制 $2$ 个元素，时间 $3$
• 第 $5-7$ 次 p_b：各 $1$ 次时间
• 第 $8$ 次 p_b：数组大小从 $4→8$，复制 $4$ 个元素，时间 $5$

$\dots$

总时间 $T (n) = n + (1 + 2 + 4 + 8 + ... + 2^k)$，其中 $2^k \le n < 2^{(k+1)}$

即：$2^{(k+1)} \le 2n$ , 等价于 $2^{(k+1)}-1 < 2n$

等比数列求和：$1+2+4+...+2^k = 2^{(k+1)} - 1 < 2n$ 所以 $T (n) < n + 2n = 3n = O (n)$

结论：$n$ 次 push_back 的总时间是 $O(n)$，因此每个 push_back 的均摊时间复杂度是 $O (1)$。

方法二：记账法（Accounting Method）

思路：给每个操作分配一个 "虚拟费用"（即均摊时间）。当某个操作的实际时间小于虚拟费用时，我们将差额存入 "银行"；当某个操作的实际时间大于虚拟费用时，我们从银行中取出存款来支付超出的部分。

关键：只要银行的余额始终非负，那么总虚拟费用就≥总实际费用，因此均摊时间就是一个有效的上界。 还是用动态数组的例子： 我们给每个 push_back 操作分配 $3$ 个单位的虚拟费用。

• 当数组未满时：实际时间 $1$，存入银行 $2$ 个单位

• 当数组已满需要扩容时：假设当前数组大小为 $m$，实际时间 $m+1$（复制 $m$ 个元素 + 插入 $1$ 个新元素）

  • 这 $m$ 个元素每个都在之前存入了 $2$ 个单位，总存款 $2m$
  • 新操作的虚拟费用 $3$
  • 总可用资金：$2m + 3$
  • 实际花费：$m + 1$
  • 剩余存款：$(2m + 3) - (m + 1) = m + 2 > 0$ 银行余额始终为正！因此每个 push_back 的均摊时间确实是 $O (1)$。

下面的例子来源于 oiwiki

初始状态：
arr    = [1, 2, 3, 4]  // 初始数组
amount = [2, 2, 2, 2]  // 每个元素预存的费用

// 第一轮扩容：数组已满，需要扩容
arr    = [1, 2, 3, 4, null, null, null, null]  // 扩容后数组
amount = [2, 2, 0, 0, 0, 0, 0, 0]  // 3, 4的费用用于支付扩容

// 继续插入新元素，直至再次满载
arr    = [1, 2, 3, 4, 5, 6, 7, 8]  // 继续填充数组
amount = [2, 2, 0, 0, 2, 2, 2, 2]  // 新插入的元素同样预存费用

// 第二轮扩容：数组再次满载，需要更大的空间
arr    = [1, 2, 3, 4, 5, 6, 7, 8, null, null, null, null, null, null, null, null]  // 扩容后数组
amount = [2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]  // 5, 6, 7, 8的费用用于支付扩容

以上过程表明，每次插入操作所存储的均摊成本足够支付未来的扩容操作，从而确保了每次操作的均摊成本维持在 $𝑂(1)$．

方法三：势能法（Potential Method）

一个势能函数 $Φ$，它将数据结构的状态映射到一个非负实数。势能表示数据结构中 "积累的可用于支付未来昂贵操作的能量"。

首先，定义 状态 $S$ 为某一时刻数据结构的状态，该状态可能包含元素数量、容量、指针等信息，其中定义初始状态为 $S_0$，即未进行任何操作时的状态．

其次，定义势能函数 $\Phi(S)$ 用于度量数据结构状态 $S$ 的势能，其满足以下两个性质：

• 初始势能：在数据结构的初始状态 $S_0$ 下，势能 $\Phi(S_0) = 0$．
• 非负性：在任意状态 $S$ 下，势能 $\Phi(S) \geq 0$．

设 $S_1, S_2, \dots, S_m$ 为从初始状态 $S_0$ 开始，经过 $m$ 次操作后产生的状态序列，$c_i$ 为第 $i$ 次操作的实际开销，那么第 $i$ 次操作的均摊成本 $a_i$ 为：

$$a_i = c_i + \Phi(S_i) - \Phi(S_{i-1})$$

因此，$m$ 次操作的总时间花销为：

$$\sum_{i=1}^m c_i = \sum_{i=1}^m a_i + \Phi(S_0) - \Phi(S_m)$$

由于 $\Phi(S) \geq \Phi(S_0)$，总时间花销的上界为：

$$\sum_{i=1}^m a_i \geq \sum_{i=1}^m c_i$$

因此，若 $a_i = O(T(n))$，则 $O(T(n))$ 是均摊复杂度的一个上界．

对 vector 进行势能法分析：

定义势能函数 $Φ = 2 × (数组中元素个数 - 数组容量 / 2)$

• 当数组未满时：元素个数从 $k→k+1$
  • 势能变化 $ΔΦ = 2×(k+1 - m/2) - 2×(k - m/2) = 2$
  • 实际时间 $c_i = 1$
  • 均摊时间 $p_i = 1 + 2 = 3$
• 当数组已满需要扩容时：元素个数从 $m→m+1$
  • 数组容量从 $m→2m$
  • 势能变化 $ΔΦ = 2×(m+1 - 2m/2) - 2×(m - m/2) = 2×1 - 2×(m/2) = 2 - m$
  • 实际时间 $c_i = m + 1$
  • 均摊时间 $p_i = (m + 1) + (2 - m) = 3$

完美！ 无论是否扩容，每个 push_back 的均摊时间都是 $3$，即 $O (1)$。

注意事项

均摊复杂度是最坏情况下的平均：它保证的是任意操作序列的总时间，而不是平均情况。

不同的分析方法可能得到不同的均摊时间：但只要分析正确，它们都是有效的上界。

势能法是最强大的方法：对于复杂的数据结构（如 Splay 树、Link-Cut Tree），势能法是最常用的分析工具。

---

参考文献

OIWIKI 均摊复杂度

---

学习完毕

{{ select(1) }}

• YES
• NO