一系列操作的总成本

均摊分析

拥有房贷的读者可能对“摊销”这一概念比较熟悉。“摊销”（amortize）指的是逐步核销某项资产的初始成本。在进行均摊分析时，我们会对数据结构上一系列操作的总成本求平均值，即使其中个别操作的实际开销可能很高。这种方法不同于“平均情况”分析，因为它不涉及概率因素，且能保证平均时间性能。

进行均摊分析有三种常见方法：

• 聚合分析法
• 记账法
• 势能法

接下来我们将先简要介绍这三种方法，然后通过具体示例加以说明。

聚合分析法

在聚合分析法中，我们首先确定执行 n 次操作的总成本的上界。假设该上界为 T(n)，则每次操作的均摊成本可表示为：

$均摊成本 = \frac{T(n)}{n}$

在下一节中，我们将使用聚合分析来计算动态数组插入操作的均摊成本。

记账法

在记账法中，我们为每种操作分配一个“费用”。关键在于，某些操作被收取高于其实际成本的费用，从而积累“信用额度”，这些多余的信用可用于支付那些实际成本较高但被少收费的操作。需要注意的是，在任何时刻，累积的信用额度都不能低于零。

势能法

势能法与记账法类似，不同之处在于，它将“信用”整体地存储在整个数据结构上，而不是分配给各个单独的操作。

在不同编程语言提供的数据结构中，可以找到一些以均摊成本描述操作性能的例子。例如，在 Java 语言中，ArrayList 就是一种可动态扩容的数据结构，其插入操作具有常数级别的均摊时间复杂度。

本章旨在帮助读者理解均摊分析的基本思想并掌握其基本应用方法，因此我们仅重点介绍聚合分析法和记账法的具体实例。