问用外行的话说就是分期的复杂性？

EN

摊销复杂度是指在一系列操作上评估的每个操作的总费用。

这个想法是为了保证整个序列的总费用，同时允许单个操作的成本比摊销成本高得多。

示例：

C++ std::vector<>的行为。当push_back()将向量大小增加到其预先分配的值以上时，它会使分配的长度加倍。

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

但是，因为分配的大小增加了一倍，所以下一次对push_back()的N-1调用都将占用O(1)时间来执行。因此，N操作的总数仍将占用O(N)时间；从而为push_back()提供了每个操作的O(1)的摊销成本。

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

• 与非摊销复杂性一样，用于摊销复杂性的big-O符号忽略了固定的初始开销和恒定的性能因素。因此，为了评估big-O的摊销性能，您通常可以假设任何摊销操作序列都将“足够长”来摊销固定的启动费用。具体地说，对于std::vector<>示例，这就是为什么您不需要担心是否真的会遇到额外的操作:分析的渐近性质已经假设您将任意长度，分期分析不会对您正在测量其成本的操作序列做出假设--这是对任何可能的操作序列的最坏情况的保证。无论操作选择得多么糟糕(例如，被恶意的对手选择！)，摊销分析必须保证足够长的操作序列的成本不会始终高于其摊销成本的总和。这就是为什么(除非作为限定词特别提到)“概率”和“平均情况”与摊销分析无关--就像它们与普通的最坏情况下的大O分析一样！

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

(摘自科尔曼等人的“算法导论”)

这可能有点令人困惑，因为它既说时间是平均的，又说它不是平均案例分析。因此，让我试着用一个金融类比来解释这一点(实际上，“摊销”是最常与银行和会计联系在一起的一个词)。

假设你正在操作彩票。(不是购买彩票，我们将在稍后讨论，而是操作彩票本身。)您打印了100,000张票，每张票价为1个货币单位。其中一张彩票将使购买者有权获得40,000个货币单位。

现在，假设你可以卖出所有的门票，你将获得60,000个货币单位: 100,000个货币单位的销售额，减去40,000个货币单位的奖金。对于您来说，每张门票的价值是0.60个货币单位，在所有门票上摊销。这是一个可靠的值；您可以信赖它。如果你厌倦了自己卖票，有人来了，并提出以每张0.30货币单位的价格出售，你很清楚自己的立场。

对于彩票购买者来说，情况就不同了。购买者在购买彩票时预计会损失0.60个货币单位。但这是概率的:购买者可能在30年内每天购买10张彩票(略高于10万张)，但从未中奖。或者，他们可能会自发地购买一张彩票，赢得39,999个货币单位。

应用于数据结构分析，我们讨论的是第一种情况，在这种情况下，我们将某些数据结构操作(比如insert)的成本分摊到所有这类操作上。平均案例分析处理随机操作(例如搜索)的期望值，其中我们无法计算所有操作的总成本，但我们可以提供单个操作的预期成本的概率分析。

人们经常说，摊销分析适用于很少有高成本运营的情况，这种情况经常发生。但并不总是这样。例如，考虑所谓的“银行家队列”，它是由两个堆栈组成的先进先出(FIFO)队列。(它是一种经典的函数式数据结构；您可以用不变的单链接节点构建廉价的LIFO堆栈，但廉价的LIFO并不那么明显)。操作的实现方式如下：

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子句多少次--这取决于puts和gets的模式--但我知道每个元素都恰好从右侧堆栈移动到左侧堆栈一次。因此，n个puts和n个gets的整个序列的总成本为:n pushes，n pops和n moves，其中move是一个pop，后跟一个push：换句话说，2n个操作(n个puts和n个d26s)产生2n个d27es和2n个d28s。因此，单个d29或d30的摊销成本是一个d31和d32。

请注意，银行家的队列之所以被称为银行家队列，正是因为分期复杂性分析(以及将“分期偿还”一词与金融联系在一起)。银行家队列是过去常见面试问题的答案，尽管我认为它现在被认为太广为人知了:想出一个队列，它在分期O(1)时间内实现以下三个操作：

1)获取并移除队列中最老的元素，

2)将新元素放入队列，

3)找出当前最大元素的值。

“摊余复杂性”的原则是，尽管当你做某件事时可能会很复杂，但因为它不经常做，所以它被认为是“不复杂的”。例如，如果您创建了一个时不时需要平衡的二叉树-比方说每2^n插入一次-因为虽然平衡树相当复杂，但它在每n次插入中只发生一次(例如，在第256次插入时发生一次，然后在第512、1024次插入时再次发生，等等)。对于所有其他插入，复杂度为O(1) -是的，每n次插入需要O(n)一次，但这只是1/n概率-所以我们将O(n)乘以1/n得到O(1)。因此，这被称为“O(1)的分期复杂性”--因为当您添加更多元素时，重新平衡树所消耗的时间是最少的。