摊销分析：基于财务模型的记账法

摘要: 记账法的摊销分析

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在文章 可清空表的摊销分析 中，我们提到在数据结构中，不同操作的时间复杂度有差异，以及一串操作序列中不同操作会互相影响的情况，会使得常规的最坏情况分析不准确。

以此为动机我们引出了摊销分析，然后通过一个可清空表的简单例子，了解了摊销分析到底是怎么解决问题的。本文我们在此基础上，进一步讨论摊销分析的思想。为了便于对比不同的思路，我们还是用可清空表的例子。

案例回顾

考虑一个在数组上维护的线性表，其中元素可用通过下标访问。在这样的线性表上，我们实现一个可清空表，支持以下两个操作：

• add(x)，将元素 x 添加到表的末尾。
• clear()，移除所有的元素，使其变成空表。

通过摊销分析我们有以下结论，推导过程参考文章 可清空表的摊销分析。

定理

假设一个可清空表 $S$ 用数组实现，那么在空的可清空表上的 n 个操作需要 $O(n)$ 的时间复杂度。

---

上面的例子虽然简单，但很好地体现了摊销分析的动机。这是一种最坏情况下的平均情况分析，平均体现在一个操作在一系列操作中的摊销运行时间，具体讲就是一系列操作的最坏情况运行时间除以操作序列的长度。因此对于上述定理，我们也可以说可清空表的每个操作在最坏情况下的摊销时间复杂度为 $O(1)$。

摊销分析的方法有很多种，最直接的方法是直接计算完成一系列操作的运行时间的上界，这也是前面的文章中对上述定理的证明过程中使用的方法。这种直接计算的方法在算法导论中称为聚合分析，适用于比较简单的一系列操作，

如果数据结构和操作序列很复杂，则需要一些额外的技术。在实践中比较流行的方法有基于财务模型的记账法，以及基于能量模型的势函数法。

记账法

记账法通过使用贷方和借方跟踪一系列操作中不同操作的运行时间。假设算力是需要付费使用的资源，支付1元可以购买 $O(1)$ 时间的算力，而操作序列中的每个操作，都视为由若干个基本操作组成，每个基本操作都是 $O(1)$ 时间的，也就是每个基本操作都需要支付 1 元。

还是以可清空表为例，add 操作本身可以视为一个需要支付 1 元基本操作，它是 $O(1)$ 的；clear 操作要清空表，需要一个一个地将元素清除，清除一个元素的时间是 $O(1)$ 的，这可以视为一个需要支付 1 元的基本操作，而 clear 整体就是由若干个这样的基本操作组成，需要支付多少钱就要看若干个具体是多少个。

记账法的摊销分析过程中，记账时不用考虑收费的公平性，也就是说可以对一些包含的基本操作少的操作多收费，将多收的费用存在银行，用于后续可能会出现的包含更多基本操作的操作。再这样的机制下，我们就可以对操作序列中的 $n$ 个操作每个都收取 $a$ 元，并且不会导致不够支付操作序列的所需的总算力。如果真能建立这样一个摊销方案，就可以说操作序列中的每个操作都有摊销 $O(a)$ 的时间复杂度。

现在我们重新考虑可清空表的例子，支付一元的算力可以完成一个 add 操作（其本身就是基本操作），或者 clear 操作中清除一个元素的基本操作。现在我们多操作序列的每个操作收费 2 元，这意味着每个 add 操作都多 1 元，同时也对某些 clear 操作少收了。将每个 add 操作获利的 1 元存进银行，当一个 clear 操作执行时，将银行中的钱取出来支付清除所有元素的算力所需费用即可。不论需要清除多少元素，每个元素在它插入时都会存 1 块钱支付其清除的费用，而一个元素最多只能删除一次，因此银行中的钱肯定是够的。所以这是一个有效的摊销方案，即每个操作收取 2 元，即可在最坏情况下也能支付整个操作序列所需算力的所有费用，

事实上，$n$ 个操作的序列所需的费用可能在 $n$ 到 $2n$ 之间，我们对每个操作收费 2 元是按照最坏情况来收的。因此可以说操作序列的一个操作在最坏情况下就有摊销 $O(2)$（也就是 $O(1)$）的时间复杂度。

总结

记账法的关键是分析清楚对于数据结构来说，什么是需要支付 1 元的基本操作，以及每种操作都是如何由基本操作构成的。在此基础上去看在最坏情况下，每个操作收费多少才能使得不会出现收上来的钱不足以支付所有所需算力的情况。

---