摊还分析

摊还分析（Amortized analysis）通过对一系列最坏情况操作的平均每次操作成本进行界定，表明当成本分摊到许多廉价操作中时，偶尔昂贵的操作也可以变得廉价。

Definition

摊还分析是一种用于界定数据结构上一系列操作的总成本，并将其除以操作次数的方法，从而得出每次操作的摊还成本。即使单个操作的成本差异很大，这种摊还成本在整个序列的最坏情况下也成立。

Scope

本主题涵盖了摊还分析的三种标准技术——聚合分析法（aggregate method）、核算法（accounting (banker's) method）和势能法（potential method）——以及它们在操作成本各异的数据结构中的应用，例如动态数组、二进制计数器、伸展树（splay trees）和不相交集（union-find）结构。它区分了摊还成本与平均情况成本以及每次操作的最坏情况成本。

Core questions

• 摊还成本与每次操作的最坏情况成本和平均情况成本有何不同？
• 聚合分析法如何界定操作序列的总成本？
• 核算法如何分配信用点（credits）以支付后续昂贵操作的费用？
• 势能法如何利用势函数（potential function）来平滑成本？
• 哪些数据结构依赖于摊还保证而非每次操作的界限？

Key concepts

• 摊还成本
• 聚合分析法
• 核算法（银行家法）
• 势能法
• 势函数
• 动态数组加倍
• 二进制计数器增量
• 带路径压缩的并查集

Key theories

势能法

势能法为数据结构的状态分配一个非负势能；操作的摊还成本是其实际成本加上势能的变化，因此廉价操作会积累势能，用于支付后续昂贵操作的费用。

核算法（银行家法）

核算法对某些操作收取高于其实际成本的费用，将盈余作为信用点存储在数据结构元素上，以支付未来昂贵操作的费用，确保信用点永不为负。

Clinical relevance

摊还分析解释了为什么许多广泛使用的数据结构在实践中是高效的，尽管偶尔会有昂贵的操作：动态数组（可变大小列表）、进行再散列的哈希表、用于连通性和最小生成树算法的并查集（union-find），以及伸展树（splay trees）等自调整结构都依赖于摊还保证而非每次操作的保证。

History

摊还分析的术语和系统框架由Robert Tarjan于1985年提出，借鉴了早期的特设论证。该技术对于分析Tarjan和Sleator在1980年代开发的自调整数据结构（伸展树、斐波那契堆）至关重要。

Key figures

• Robert Tarjan
• Daniel Sleator

Seminal works

• tarjan1985amortized
• cormen2009

Frequently asked questions

摊还成本与平均情况成本相同吗？

不。平均情况成本是基于输入概率分布的期望值，可能因不走运的输入而失效。摊还成本是对一系列操作的最坏情况保证，不假设随机性：任何此类序列的总成本都是有界的，因此每次操作的平均值始终成立。

为什么动态数组的追加操作在调整大小时是O(n)的情况下，摊还成本却是O(1)？

因为数组通常会将其容量加倍，所以相对于追加操作，调整大小的操作很少发生，并且在一系列n次追加操作中，总的复制工作量与n成比例。将这些工作量分摊到所有追加操作中，即使单次调整大小是线性的，也能得到常数级的摊还成本。