Amortized Analysis

阅读与排查导航

  • 前置知识
    • 复杂度分析 — 先掌握复杂度分析，补齐本文默认使用的定义与基本操作。
  • 本文主线
    1. 关键要点 · 聚合分析 — 概括“聚合分析”的核心内容及其与上下文的关系。
    2. 重点难点 · 记账分析 — 每次追加预收 3 单位：1 单位支付本次写入，2 单位留在公共账户中用于将来的搬移。容量从 m/2 增长到 m 后，要等数组再次装满，至少经历……
  • 逐级章节树（按层定位与排查）
    • 引入 — 均摊分析研究任意合法操作序列的总成本，再把总成本分配到各次操作。它不需要输入的概率分布：某一次操作仍可能很贵，但对长度为 q 的整个序列若能证明……
    • 内容 — 涵盖聚合分析、记账分析、势能分析子章节，可按当前层级继续向下定位
      • 聚合分析 — 概括“聚合分析”的核心内容及其与上下文的关系。
      • 记账分析 — 每次追加预收 3 单位：1 单位支付本次写入，2 单位留在公共账户中用于将来的搬移。容量从 m/2 增长到 m 后，要等数组再次装满，至少经历……
      • 势能分析 — 涵盖原理、示例：动态数组的扩容分析子章节，可按当前层级继续向下定位
    • 扩展示例：堆栈操作 — 设栈支持 push(x)、非空时的 pop()、以及从栈顶至多弹出 k 个元素的 multi-pop(k)。为把空栈上的批量调用也计入成本，约定……
      • 聚合分析法 — 概括“聚合分析法”的核心内容及其与上下文的关系。
      • 记账分析法 — 每次 push 收费 2：1 支付入栈，另 1 附在该元素上，留待它被弹出。每次 pop 的成本由被弹出元素的余额支付，收费 0；每次 mult……
      • 势能分析法 — 概括“势能分析法”的核心内容及其与上下文的关系。
    • 参考资料 — 汇总“参考资料”相关的来源、补充材料与延伸入口。
    • 参考链接 — 汇总“参考链接”相关的来源、补充材料与延伸入口。
    • 题目应用：动态数组操作总成本 — 若操作序列同时包含末尾追加和末尾删除，且删除不主动缩容，上述数组的容量仍只会增长。设序列有 q 次操作，其中追加 P 次：所有追加引起的搬移总数……
      • 四分之一阈值的扩缩容 — 将缩容阈值设在四分之一，可让缩容后的数组保持半满，在再次扩容或缩容前积累足够多的普通操作
      • 验证与练习 — 短序列穷举用于排查阈值及小容量边界；一般上界依赖上面的逐步证明

内容状态：下文仅追加与堆栈部分给出模型内证明；末尾扩缩容部分补齐势能证明和有限序列核验。阈值选择参考 MIT 6.046J 讲义与 MIT 6.006 习题课；这些结论针对文中明确的抽象单位成本模型，并非对某个标准库实现的实测结论。

引入

均摊分析研究任意合法操作序列的总成本，再把总成本分配到各次操作。它不需要输入的概率分布：某一次操作仍可能很贵，但对长度为 $q$ 的整个序列若能证明总成本为 $O(q)$，就称这些操作有 $O(1)$ 均摊成本。这个结论不能保证单次操作的最坏延迟也是常数。

常用方法是聚合分析、记账分析和势能分析。三者估计的是同一总成本，只是分别从求和、预存费用、状态函数的角度给出证明。

内容

先定义一个抽象动态数组：初始长度 $n=0$、容量 $m=0$；追加一个整数时，若 $n=m$，先分配容量 $\max(1,2m)$ 的新数组并搬移原有 $n$ 个元素，然后在末尾写入新元素。每次写入和每次搬移各计 $1$ 单位成本，分配本身按常数成本处理。因此一次追加的成本是 $1$，或在扩容时是 $n+1$。这个模型明确规定了翻倍策略；C++ 标准的顺序容器要求保证 std::vector 的尾部插入具有均摊常数复杂度，但不要求其容量按此处的具体倍数增长，且复杂元素的搬移成本也须另计。

聚合分析

连续追加 $N$ 个元素，写入成本恰为 $N$。扩容时搬移的元素数依次为 $1,2,4,\ldots$，且每次被搬移的数量都小于 $N$，所以搬移总数是一个小于 $2N$ 的等比和。总成本小于 $3N$，从而均摊每次追加 $O(1)$。例如前五次追加成本为 $1,2,3,1,5$：第五次虽要搬移四个元素，五次总成本仍只有 $12$。

记账分析

每次追加预收 $3$ 单位：$1$ 单位支付本次写入，$2$ 单位留在公共账户中用于将来的搬移。容量从 $m/2$ 增长到 $m$ 后，要等数组再次装满，至少经历 $m/2$ 次追加；这些追加存下至少 $m$ 单位，足以支付下一次从容量 $m$ 扩到 $2m$ 时搬移的 $m$ 个旧元素。最初从容量 $0$ 扩到 $1$ 不搬移元素；容量 $1$ 到 $2$ 的搬移也可由首次追加存下的费用支付。账户余额始终不为负，故前 $N$ 次追加的实际总成本不超过收取的 $3N$。

预收费用只是证明工具，并不是程序实际执行了额外工作。关键是每笔未来成本已有资金来源；只说“把贵操作分摊到便宜操作上”还不足以证明上界。

势能分析

原理

设第 $i$ 次操作前后状态分别为 $S_{i-1},S_i$，实际成本为 $c_i$，选取势能函数 $\Phi$，定义均摊成本

\[\widehat c_i=c_i+\Phi(S_i)-\Phi(S_{i-1}).\]

将前 $q$ 次求和，势能变化相消：

\[\sum_{i=1}^q c_i =\sum_{i=1}^q\widehat c_i+\Phi(S_0)-\Phi(S_q).\]

只要所有可达状态满足 $\Phi(S_q)\ge\Phi(S_0)$，均摊成本总和便是实际成本的上界。通常取 $\Phi(S_0)=0$ 且 $\Phi\ge0$；若某个势能函数在初始状态为负，必须重新设定初始模型或证明相应的下界，不能直接套用非负势能的结论。单次均摊成本可以为负，证明只要求总和的关系成立。

示例：动态数组的扩容分析

对上述仅追加、容量翻倍的数组，令 $\Phi(n,m)=2n-m$。初始状态 $(0,0)$ 的势能为 $0$；每次扩容后 $n>m/2$，在两次扩容之间 $n$ 只增加，因此所有可达状态的势能均非负。

  • 首次追加：从 $(0,0)$ 到 $(1,1)$，成本 $1$，势能变化 $1$，均摊成本为 $2$。
  • 不扩容的追加：成本 $1$，势能增加 $2$，均摊成本为 $3$。
  • 原容量 $m=n\ge1$ 时扩容：状态变为 $(n+1,2n)$，成本 $n+1$，势能变化 $2-n$，均摊成本为 $(n+1)+(2-n)=3$。

因此每次追加的均摊成本至多 $3$，任意 $N$ 次追加的实际总成本至多 $3N$。这个势能函数表达的是已完成追加为未来搬移积累的费用；它不是“剩余空位数”。

扩展示例：堆栈操作

设栈支持 push(x)、非空时的 pop()、以及从栈顶至多弹出 $k$ 个元素的 multi-pop(k)。为把空栈上的批量调用也计入成本，约定 push 和 pop 各耗 $1$，multi-pop(k) 若实际弹出 $r=\min(k, S )$ 个元素则耗 $1+r$：其中 $1$ 是调用开销。以下只讨论初始为空、$k\ge0$ 的合法操作序列。

聚合分析法

设共有 $q$ 次操作，其中 push 有 $P$ 次。每个入栈元素至多被弹出一次，所以所有 pop 和 multi-pop 弹出的元素总数 $R\le P$。各次调用的基本成本合计至多 $q$，额外的批量弹出成本至多 $R$，故总成本至多 $q+P\le2q$。这里不需要也通常没有 $q\le2P$：可以在空栈上调用任意多次 multi-pop(0)，它们仍各有一次调用成本。

记账分析法

每次 push 收费 $2$：$1$ 支付入栈，另 $1$ 附在该元素上，留待它被弹出。每次 pop 的成本由被弹出元素的余额支付，收费 $0$；每次 multi-pop 收费 $1$ 支付调用开销，实际弹出的 $r$ 个元素各用自身余额支付删除。任一元素只出栈一次，账户不会透支，因此每次操作收费至多 $2$。

势能分析法

取 $\Phi(S)= S $，初始为 $0$，且始终非负。一次 push 的均摊成本为 $1+1=2$；一次有效 pop 为 $1-1=0$；一次弹出 $r$ 个元素的 multi-pop 为 $(1+r)-r=1$。于是任意 $q$ 次操作总成本为 $O(q)$。三种证明都依赖“元素只会被弹出一次”，而不是假定每次批量弹出本身很便宜。

参考资料

参考链接

题目应用：动态数组操作总成本

若操作序列同时包含末尾追加和末尾删除，且删除不主动缩容，上述数组的容量仍只会增长。设序列有 $q$ 次操作，其中追加 $P$ 次：所有追加引起的搬移总数小于 $2P$，每次追加或删除另有常数成本，因此总成本为 $O(q)$。这里沿用的是聚合求和证明；前面仅追加时的势能函数 $2n-m$ 在任意删除后可能变负，不能原样使用。若对 std::vector 主动调用 shrink_to_fit，还应把它可能造成的重新分配另行计入；标准规定它只是一个非强制的缩容请求。

缩容策略若设置不当，均摊结论也会改变。例如容量为 $m$、长度为 $m/2$ 时立即缩到 $m/2$，下一次追加又因满载扩到 $m$；之后一次删除再缩回 $m/2$。反复追加、删除会反复搬移 $\Theta(m)$ 个元素，使每次操作不再是常数均摊。证明必须覆盖实际采用的扩容与缩容规则。

四分之一阈值的扩缩容

将缩容阈值设在四分之一，可让缩容后的数组保持半满，在再次扩容或缩容前积累足够多的普通操作。

具体规则是：初始 $(n,m)=(0,0)$；满载追加时将容量改成 $\max(1,2m)$，然后写入；非空数组末尾删除后，若 $m>1$ 且新长度 $n\le m/4$，将容量减半并搬移剩余 $n$ 个元素。每次追加或删除的基本成本为 $1$，扩缩容另按搬移元素数收费。首次追加后容量始终为 $2$ 的幂；缩容后占用率回到 $1/2$（最小容量时除外），与下一次扩容的满载条件留出间隔。这是 MIT 讲义采用的四分之一阈值思想；此处把零容量和单位成本边界也纳入模型。

可以用同一个非负势能覆盖任意合法的追加、删除交错序列：初态令 $\Phi(0,0)=0$，其余状态令

\[\Phi(n,m)= \begin{cases} 2n-m, & 2n\ge m,\\ m/2-n, & 2n<m. \end{cases}\]

满载扩容前势能为 $m$；扩容并写入后为 $2$，实际成本 $m+1$，故均摊成本为 $3$。不扩容的追加均摊成本至多 $3$；不缩容的删除至多 $2$。若 $m\ge4$ 时删除触发缩容，删除前长度为 $m/4+1$，删除后长度为 $m/4$、容量为 $m/2$；势能从 $m/4-1$ 降为 $0$，实际成本 $1+m/4$，均摊成本恰为 $2$。$m=2$ 时从一个元素删到零并缩到容量 $1$，均摊成本为 $3/2$；首次追加为 $2$。因此每步均摊成本至多 $3$，初始势能为零且可达状态势能非负，任意 $q$ 次合法操作的总成本至多 $3q$。这里单次触发搬移的操作仍可花费 $\Theta(n)$。

空间边界也来自阈值：只要 $n>0$，每步结束后都有 $n>m/4$，故 $m<4n$；删空后容量至多为 $1$。若允许任意位置插入或删除，移位成本不在上述证明内；若元素搬移、析构或分配不符合单位成本假设，也须另算。尤其不能据此推断 std::vector::pop_back() 会按四分之一阈值自动缩容。

验证与练习

短序列穷举用于排查阈值及小容量边界；一般上界依赖上面的逐步证明。

验证方法：检查 + 只在满载时扩容、- 只在非空时使用，并在每步记录 $(n,m)$、实际成本和 $c+\Delta\Phi$。从空态枚举长度不超过 $16$ 的全部合法 +/- 序列，应始终满足 $\Phi\ge0$、$c+\Delta\Phi\le3$ 和累计实际成本 $\le3q$；2026-10-20 用 Python 3 穷举了 $26{,}364$ 个转移，均满足判据。另检查容量 $8$ 满载后追加、紧接着删除：状态依次为 $(8,8)\to(9,16)\to(8,16)$，不会立即缩容；若改成半满即缩容，此序列可反复触发搬移。

题目应用卡片（由 MIT 6.006 动态数组习题课的扩缩容场景派生的本页练习）：

  • 抽象题意：维护末尾可增删的序列，同时证明任意合法操作串的总搬移量为线性级、容量与非空长度同阶。
  • 输入：一串 +（追加）与 -（删除最后一个元素），每个 - 前序列非空。
  • 输出：按上述规则得到的末态长度、容量、单位成本总和，以及适用于任意输入串的上界。
  • 建模：用 $(n,m)$ 记录元素数和容量，区分基本操作成本与扩缩容搬移成本。
  • 算法用法：满载翻倍、删至四分之一时减半；用分段势能逐步界定总成本，用占用率界定空间。
  • 算法是否改造：相对仅追加的模型，增加删除、滞后缩容和低占用率分支势能；不复用仅追加时的 $2n-m$ 势能。
  • 链接：MIT 6.006 官方习题课讲义提供末尾增删的动态数组实现与适用边界；本卡片的精确单位成本和零容量约定以上述正文为准。