通俗易懂的解释摊销复杂度是什么？

Question

请问有人能够用通俗易懂的语言解释摊销复杂度吗？我在网上找了很久也没有找到确切的定义，也不知道它与算法分析有什么关系。如果有任何有用的信息，即使是外部引用的，都将不胜感激。

- Bob John

---

http://en.wikipedia.org/wiki/Amortized_complexity - Oliver Charlesworth

https://dev59.com/_Ggu5IYBdhLWcg3wv5im https://dev59.com/jWnWa4cB1Zd3GeqPwQdj https://dev59.com/0mzXa4cB1Zd3GeqPTGnG http://programmers.stackexchange.com/questions/161404 - BlueRaja - Danny Pflughoeft

可能是算法的摊销分析是什么？的重复问题。 - underscore_d

Answer 1

摊销复杂度是指在一系列操作中，每个操作的平均花费。

其思想是保证整个序列的总花费，同时允许单个操作比摊销成本昂贵得多。

例如：C++中的std::vector<>。当push_back()将向量大小增加到超过其预分配值时，它会将分配的长度加倍。

因此，单个push_back()可能需要O(N)时间来执行（因为数组内容被复制到新的内存分配中）。

但是，由于分配的大小加倍了，接下来的N-1次调用push_back()将每次只需要O(1)的时间来执行。因此，N个操作的总时间仍然需要O(N)的时间；从而给push_back()一个每个操作的摊销成本为O(1)。

---

除非另有说明，摊销复杂度是对任何操作序列的渐近最坏情况保证。这意味着：

• 与非摊销复杂度一样，用于摊销复杂度的大O符号忽略了固定的初始开销和常数性能因素。因此，在评估大O摊销性能时，您通常可以假设任何一系列摊销操作都足够“长”，以便分摊固定的启动费用。具体而言，在std::vector<>示例中，这就是为什么您不需要担心是否实际遇到N个额外操作的原因：渐近分析的性质已经假定您会遇到。

• 除了任意长度，摊销分析不对您正在测量其成本的操作序列进行任何假设--它是对任何可能的操作序列的最坏情况保证。无论操作选择得多么糟糕（比如由恶意对手选择！），摊销分析必须保证一段足够长的操作序列的成本不会持续高于其摊销成本之和。这就是为什么（除非明确说明为限定条件）“概率”和“平均情况”与摊销分析无关--就像它们与普通的最坏情况大O分析一样！

- comingstorm

Answer 2

在摊销分析中，执行一系列数据结构操作所需的时间是对执行的所有操作进行平均的... 摊销分析与平均情况分析不同之处在于，它不涉及概率； 摊销分析保证了最坏情况下每个操作的平均性能。

（引自Cormen等人的“算法导论”）

这可能有点令人困惑，因为它既说时间被平均了，又说它不是平均情况分析。因此，让我用一个金融类比来解释一下（的确，“摊销”是一个与银行和会计学最常相关的词）。

假设你正在经营一场彩票活动。（不是购买彩票，我们待会再谈到那个问题，而是指运营彩票本身。）你打印了100,000张彩票，每张售价1货币单位。其中一张彩票将使购买者获得40,000货币单位。

假设你能卖出所有门票，你将赚取60,000货币单位：100,000货币单位的销售额减去40,000货币单位的奖金。对于你来说，每张门票的价值是0.60货币单位，分摊到所有门票上。这是一个可靠的价值；你可以依赖它。如果你厌倦了自己卖门票，有人提供每张门票0.30货币单位的价格，你就知道自己的立场。

对于购买彩票的人来说，情况则不同。购买者在购买彩票时预计会损失0.60货币单位。但这是概率性的：购买者可能每天购买十张彩票长达30年（超过100,000张彩票）而从未中奖。或者他们可能某一天突然购买一张彩票，并赢得39,999货币单位。

应用于数据结构分析，我们谈论的是第一种情况，在这种情况下，我们将某些数据结构操作的成本（比如插入）分摊到所有此类操作上。平均情况分析涉及到随机操作（比如搜索）的期望值，我们无法计算所有操作的总成本，但我们可以提供单个操作的预期成本的概率分析。

经常有人说摊销分析适用于高成本操作很少的情况，这通常是正确的。但并非总是如此。例如，考虑所谓的“银行家队列”，它是由两个栈组成的先进先出（FIFO）队列。（它是一种经典的函数式数据结构；你可以用不可变的单链节点构建廉价的LIFO栈，但便宜的FIFO则不那么明显）。操作的实现如下：

put(x):  Push x on the right-hand stack.
y=get(): If the left-hand stack is empty:
           Pop each element off the right-hand stack and
             push it onto the left-hand stack. This effectively
             reverses the right-hand stack onto the left-hand stack.
         Pop and return the top element of the left-hand stack.

现在，我声明假设我从一个空队列开始并以空队列结束，put和get的摊还成本为O(1)。分析很简单：我总是将put放在右手堆栈上，并从左手堆栈中获取get。因此，除了If子句之外，每个put都是一个push，每个get都是一个pop，两者都是O(1)。我不知道我会执行多少次If子句——它取决于put和get的模式——但我知道每个元素都恰好从右手堆栈移动到左手堆栈一次。因此，在n个put和n个get的整个序列中，总成本为：n个push，n个pop和n个move，其中move是pop后跟一个push：换句话说，2n个操作（n个put和n个get）导致2n个push和2n个pop。因此，单个put或get的摊销成本是一个push和一个pop。

请注意，银行家队列之所以被称为银行家队列，正是因为摊销复杂度分析（和“摊销”一词与金融的关联）。银行家队列是对曾经常见的面试问题的答案，尽管我认为它现在已经被认为是太过于众所周知：设计一个队列，使其可以在摊销O(1)时间内执行以下三个操作之一：

1）获取并删除队列中最老的元素，

2）将新元素放入队列，

3）查找当前最大元素的值。

- rici

Answer 3

"摊销复杂度"的原则是，尽管某些操作可能很复杂，但由于它们并不经常发生，因此被认为是"非复杂"的。例如，如果创建一个需要定期平衡的二叉树 - 比如每插入 2^n 次 - 因为平衡树相当复杂，但每 n 次插入只会发生一次（例如在第 256 次插入时，然后在第 512 次、1024 次等）。在所有其他插入中，复杂度为 O(1) - 是的，每 n 次插入需要 O(n)，但只有 1/n 的概率 - 所以我们将 O(n) 乘以 1/n，得到 O(1)。因此，这被称为"摊销复杂度为 O(1)" - 因为随着添加更多元素，重新平衡树所需的时间是最小的。"

- Mats Petersson

---

"大到什么程度"与此有何关联？这里存在多余的细节，而且乘以概率的关键概念也被忽略了。 - Potatoswatter

不合格的摊销性能保证与概率无关——它们是任何操作序列的绝对保证。当谈论概率性能时，应使用“期望”或“平均情况”性能这个专业术语。 - comingstorm

我稍微改了一下措辞，去掉了“足够大”的词汇（我的意思是一个小树可能需要经常重新平衡，但一个较大的树并不经常重新平衡-但我同意这不是一个很好的说法，因为随着它的增长，工作量也会增加）。 - Mats Petersson

摊销复杂度与平均情况复杂度不同，因此，正如@comingstorm所说，概率并不涉及其中。要将摊销分析应用于重新平衡二叉树，您必须证明（最坏情况下）重新平衡对每个插入都贡献了恒定的时间。 - rici

Answer 4

摊销的意思是将成本分摊到重复运行中。最坏情况的行为保证不会经常发生。例如，如果最慢的情况是O(N)，但其发生的几率只有O(1/N)，而且其他情况都是O(1)，那么该算法仍然具有摊销常数O(1)时间。只需将每个O(N)运行的工作分配给其他N次运行即可。

这个概念取决于有足够多的运行来分摊总时间。如果算法只运行一次，或者每次运行都必须满足截止日期，则最坏情况的复杂度更加相关。

- Potatoswatter

Answer 5

如果您想要查找未排序数组中第k小的元素，按照顺序对该数组进行排序的时间复杂度为O(n logn)。而查找第k小的数字只需要定位其索引位置，所以时间复杂度是O(1)。

由于数组已经排序，我们不必再次排序。我们永远不会超过最坏情况超过一次。

如果我们执行n个尝试定位第k小元素的查询，则时间复杂度仍为O(n logn)，因为它占主导地位而不是O(1)。如果平均每个操作的时间，那么结果将是：(n logn)/n或O(logn)，即时间复杂度/操作数。

这就是摊销复杂度。

我认为就是这样，我也在学习中。

- user2968401

Answer 6

它有点类似于将算法中不同分支的最坏情况复杂度与执行该分支的概率相乘，并将结果相加。因此，如果某个分支很少被执行，它对复杂度的贡献就会更少。

- perreal