摊还分析

概念

• 核心观点：摊还分析计算的是在一个操作序列中，每个操作的平均成本。它保证了整个序列的总成本不会超过所有操作的瘫痪成本之和。关键在于，这个"摊还成本"通常是一个较小的、固定的值，即使序列中某些操作的实际成本可能非常高。
• 类比：可以想象一下上班通勤，大部分时候只需要约15分钟，但偶尔（如平均一个月一次）会遇到大堵车，此时要花费2个小时
  • 最坏情况分析会说：“你上班通勤最多要花费2小时。“这个结论没错，但不能准确反映日常的通勤体验
  • 摊还分析则会说：“我们把罕见的2小时堵车成本分摊到整个月的通勤中。可能每天的摊还成本就变成了20分钟。“这个结论更能代表通勤的时间成本

意义

• 当数据结构的操作成本波动很大时，摊还分析非常有用。一个典型的例子是C++的vector或Java的ArrayList（动态数组）
  • 大多数push_back操作：如果数组容量未满，这个操作非常快，时间复杂度是O(1)
  • 偶尔的push_back操作：如果数据容量满了，时间复杂度是O(n)
  • 如果我们只看最坏情况，会得出 push_back 的复杂度是 O(n) 的结论。但这显然忽略了 O(1) 操作占绝大多数的事实。摊还分析可以证明，push_back 的摊还成本其实是 O(1)。

摊还分析方法

聚合分析

计算方法

• 计算出一个包含n个操作的序列的总实际成本
• 用总成本T(n)除以操作次数n，得到每个操作的平均成本，即摊还成本
• 摊还成本$T = T(n)/n$

案例：动态数组的push_back

• 假设我们从一个空数组开始，连续执行n次push_back操作。数组容量从1开始，每次满了就翻倍
  • 常规插入（非扩容）：每次成本为1个单位
  • 扩容插入：当元素数量打到1,2,4,8,…，2^k^时，需要扩容，需要复制2^i-1^个元素
• 现在来看n次操作的总成本：
  • 常规插入（非扩容）总成本：每次1单位成本，故总成本为n
  • 扩容总成本：扩容发生在2^k^时，总扩容成本时2^k^-1，这个成本小于n
• 总实际成本： O(n)
• 摊还成本：O(1)

记账法/核算法

计算方法：

• 这份方法为每个操作分配一个“摊还成本”
  • 如果一个操作的摊还成本>实际成本，多出来的部分存入"账户"中
  • 如果一个操作的实际成本<摊还成本，那么不足的部分就从"银行账户"中取出"存款"来支付
• 关键原则：只要保证"银行账户"余额不为负，我们设定的摊还成本就是有效的

案例：动态数组的push_back

• 我们设定push_back的摊还成本为3个单位
• 情况1：数组未满（实际成本为1）
  • 我们支付3单位的摊还成本
  • 1单位用于本次插入
  • 剩下2单位存入银行
• 情况2：数组已满，需要扩容
  • 此时，数组中有m个元素。我们需要将它们全部复制到新数组（大小为2m），然后再插入新元素，实际成本为m+1
  • 足够支付，设定成立
• 时间复杂度为O(1)

摊还成本的选取

选取原则

• 原则是在满足不会出现负资产的前提下（在级数上）尽可能小

示例

• 仍然以push_back操作为例。从刚执行完一次扩容的状态开始，此时数组中有$m$个元素，设摊还分析代价为$x$，那么当执行到下一次扩容时，余额是$m(x-1)$下一次扩容时，数组大小为$2m$，要插入第$2m+1$个元素，成本为$2m+1$。需要取出的代价为$2m+1-x$
• 即x需要满足于$m(x-1) \geq 2m+1-x$，可以解得$x >= \frac{3m+1}{m+1}$，可知右式小于3且当$m$趋向于正无穷时收敛于3，那么可以解得$m \geq 3$。上面示例中的3就是这么得到的

势能法

计算方法

• 这是最灵活也最抽象的方法，结合了物理学中势能的概念
  • 定义一个势函数$\Phi$，将数据结构的某个状态D映射到一个非负数$\Phi(D)$，代表该状态下积累的"势能”。我们要求初始状态$D_0$的势能$\Phi(D_0) = 0 $
  • 第i个操作的摊还成本$\hat{a}_i$，有 $\hat{a}i = c_i + \Phi(D_i) - \Phi(D{i-1})$

案例：动态数组的push_back

• 定义势函数：
  • 首先给出两个参数
    • size：数组中元素的数量
    • capacity：数组的容量
  • 然后定义势函数$ Φ(D) = 2 * size - capacity $
    • 初始状态：$size = 0, capacity = 0, \Phi(D_0) = 0$
    • 我们必须保证任何时候有$\Phi(D) \geq 0$，因为capacity总是大于等于size，并且在扩容后capacity = 2*size，所以这个势函数总是非负的。
• 然后分析第i次push_back
  • $size_i = size_{i-1} + 1$
  • $c_i = $ 实际成本
    • 情况1：不扩容
      • 实际成本$c_i = 1$
      • 势能变化：$ΔΦ = Φ(D_i) - Φ(D_{i-1}) = (2size_i - capacity_i) - (2size_{i-1} - capacity_{i-1}) = 2(size_i - size_{i-1}) = 2$
      • 摊还成本：$â_i = c_i + ΔΦ = 1 + 2 = 3$
    • 情况2：扩容(size_{i-1} = capacity_{i-1})
      • 扩容前，$size = m，capacity = m$
      • 扩容后，$size = m+1，capacity = 2m$
      • 实际成本$c_i = m+1$
      • 势能变化：
        • $\Phi(D({i-1})) = m$
        • $\Phi(D_i) = 2(m+1) - 2m = 2$
        • $\Delta\Phi = 2-m$
      • 摊还成本$ â_i = c_i + ΔΦ = (m+1) + (2 - m) = 3$
  • 即两种抢矿下摊还成本都为3，时间复杂度为O(1)