摊还分析

概述

摊还分析（Amortized Analysis）是分析一个操作序列中每个操作的平均代价的方法，它不假设输入的概率分布，而是在最坏情况下保证操作序列的总代价。摊还分析的核心思想是：某些操作的代价较高，但其”多余”的代价可以被后续低代价操作”分摊”。三种具体方法：聚合分析、记账方法、势能方法。

定义

摊还分析（Amortized Analysis）

摊还分析分析一个数据结构上执行的操作序列 $\sigma ={\sigma }_1,{\sigma }_2,\dots ,{\sigma }_n$ 的总代价，将总代价均摊到每个操作上，得到每个操作的摊还代价（amortized cost）。

关键性质：即使单个操作的最坏代价很高，摊还代价可以很低，因为高代价操作不频繁发生。

与概率分析的区别：摊还分析不使用概率，它给出的是最坏情况下的平均保证。

三种分析方法

聚合分析（Aggregate Analysis）

直接计算 $n$ 个操作的总代价 $T(n)$，则每个操作的摊还代价为 $T(n)/n$。

记账方法（Accounting Method）

为每种操作赋予一个摊还代价（可能高于或低于实际代价）。将”多付”的代价存为信用（credit），用于支付后续”亏欠”的操作。要求总信用始终非负。

势能方法（Potential Method）

定义势能函数 $\Phi$，第 $i$ 个操作的摊还代价为：

${\hat{c}}_i=c_i+\Phi (D_i)-\Phi (D_{i-1})$

其中 $c_i$ 为实际代价，$D_i$ 为第 $i$ 个操作后的数据结构状态。详见势能方法。

核心性质

性质	描述	备注
不依赖概率	不假设输入分布，给出最坏情况保证	区别于概率分析
序列分析	分析操作序列而非单个操作	单个操作的最坏代价可能很高
三种方法等价	聚合、记账、势能方法给出相同的摊还代价	选择最方便的方法即可
信用/势能非负	记账法的总信用和势能法的势能始终非负	保证摊还代价是实际代价的上界

应用场景

• 动态表扩容：

  • 策略：表满时容量加倍
  • 插入的摊还代价：$O(1)$（尽管单次扩容代价为 $\Theta (n)$）
  • 势能分析：$\Phi (T)=2T.\text{num}-T.\text{size}$

• 栈操作：PUSH、POP、MULTIPOP（一次弹出多个元素）

  • MULTIPOP 的摊还代价：$O(1)$

• 二叉计数器：$n$ 次 INCREMENT 操作的总代价为 $O(n)$，每次摊还 $O(1)$

参见

• 势能方法 — 摊还分析中最灵活的方法
• 概率分析 — 使用概率的另一种平均分析技术
• 散列表 — 动态表扩容的摊还分析