按照外行的说法来摊销复杂性？
有人可以用外行人的话来解释摊销的复杂性吗？ 我一直很难在网上find一个精确的定义，我不知道它是如何与algorithm分析完全相关的。 任何有用的，即使外部引用，将不胜感激。
摊销的复杂性是每个操作的总费用，通过一系列操作进行评估。
这个想法是保证整个过程的总费用，同时允许单个操作比分摊成本昂贵得多。
例：
C ++ std::vector<>的行为。 当push_back()将vector大小增加到其预分配值以上时，它将分配的长度加倍。
因此，单个push_back()可能需要O(N)次执行（因为数组的内容被复制到新的内存分配）。
但是，由于分配的大小增加了一倍，接下来的N-1 push_back()调用每次都需要O(1)次执行。 所以， N操作的总数仍然需要O(N)时间; 从而赋予push_back() O(1)每个操作O(1)的摊销成本。
除非另有说明，否则分期付款的复杂性是任何操作顺序的渐近最坏情况保证。 意即：
-
与非摊销复杂性一样，用于摊销复杂性的大O符号忽略固定的初始开销和恒定的性能因素。 所以，为了评估大O的摊销performance，通常可以假定任何一个分期付款操作的顺序将“足够长”，以分摊固定的启动费用。 具体来说，对于
std::vector<>例子来说，这就是为什么你不必担心是否会遇到N额外的操作：分析的渐近性已经假定你会这样做。 -
除了任意长度之外，摊销分析不会对您正在测量成本的操作顺序做出假设 – 这是对任何可能的操作顺序的最坏情况保证。 无论操作select多么糟糕（比如恶意对手！），摊销分析必须保证一个足够长的操作顺序可能不会超过其摊销成本的总和。 这就是为什么（除非特别提到是一个限定词）“概率”和“平均情况”与摊销分析无关 – 不仅仅是对一个普通的最坏情况的大O分析！
在一个摊销分析中，执行一系列数据结构操作所需的时间在所有执行的操作上取平均值。摊销分析不同于平均情况分析，因为不涉及概率。 摊销分析保证了每个操作在最坏情况下的平均性能。
（来自Cormen等人的“Introduction to Algorithms”）
这可能有点令人困惑，因为它既说时间是平均的，也不是平均情况分析。 所以让我试着用一个财务的比喻来解释这个事实（实际上，“摊销”是与银行和会计最相关的一个词）。
假设您正在操作彩票。 （不要购买彩票，我们稍后会获得，但是也可以操作彩票本身。）您可以打印100,000张门票，每门门票售价为1个货币单位。 其中一张门票将使购买者有权使用4万个货币单位。
现在，假设你可以出售所有的票，你可以赚取6万货币单位：销售10万货币单位，减去4万货币单位奖。 对于你来说，每张票的价值是0.60个货币单位，在所有票上摊销。 这是一个可靠的价值; 你可以在它上面存钱。 如果你厌倦了自己出售门票，并且有人来，并提供出售他们每个0.30个货币单位，你知道你的立场。
对于彩票购买者来说，情况是不同的。 购买者在购买彩票时预期损失0.60个货币单位。 但这是可能的：购买者可能每天都会购买10张彩票30年（有点超过10万张彩票）而没有获胜。 或者他们可能会自发地购买一张单一的票，赢得39,999个货币单位。
应用于数据结构分析，我们讨论的是第一种情况，我们在这种情况下摊分了一些数据结构操作（比如插入）的成本。 平均案例分析处理的是随机操作（比如说search）的期望值，我们无法计算所有操作的总成本，但是我们可以提供一个单一预期成本的概率分析。
经常指出，摊销分析适用于高成本操作罕见的情况，情况往往如此。 但不总是。 例如，考虑所谓的“银行员队列”，它是由两个堆栈构成的先进先出（FIFO）队列。 （这是一个经典的function数据结构，你可以用不变的单链节点构build廉价的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右边的堆栈上，从左边的堆栈中取出。 所以除了If子句外，每个put都是一个push ，每个get都是一个pop ，两者都是O(1) 。 我不知道有多less次我会执行If子句 – 它取决于put的模式并get s – 但是我知道每个元素都从右边的堆栈移动到左边的堆栈。 因此，在n的整个序列中的总成本和n get s：n push es，n pop s，n move s，其中一个move是一个pop然后是一个push ：换句话说，2n put s和get 2n push和2n pop s的结果。 所以单一put （或get ）的摊销成本是一push一单。
请注意，正是由于分期付款的复杂性分析（以及“摊销”与金融的关联），银行家队列才被称为。 银行家的排队是过去常见的面试问题的答案，虽然我认为现在被认为是太熟悉了：提出一个队列实现以下三个操作，分期O（1）时间：
1）获取并删除队列中最旧的元素，
2）把一个新元素放到队列中，
3）找出当前最大元素的值。
“分期付款复杂性”的原则是，虽然这样做可能相当复杂，但由于不是很经常，所以被认为“不复杂”。 例如，如果你创build一个需要时时刻平衡的二叉树 – 比如每2^n插入一次 – 因为虽然平衡树是非常复杂的，但是每n次插入只发生一次（例如一次插入256次，然后再在第512，第1024等）。 在所有其他插入中，复杂度为O（1） – 是的，每插入一次需要O（n），但它只有1/n概率 – 所以我们将O（n）乘以1 / n得到O ）。 所以这被认为是“O（1）的摊销复杂性” – 因为当你添加更多元素时，重新平衡树所消耗的时间是最小的。
摊销手段分为重复运行。 最坏的情况下保证不会发生太多频率。 例如，如果最慢的情况是O（N），但是发生这种情况的机会只是O（1 / N），否则过程是O（1），那么algorithm将仍然具有摊销常数O（1） 。 只要考虑将每个O（N）运行的工作分成N个其他运行。
这个概念取决于有足够的运行时间来划分总时间。 如果algorithm只运行一次，或者每次运行都必须满足最后期限，那么最坏情况下的复杂性就更加相关。
将algorithm中不同分支的最坏情况复杂度与执行该分支的概率相乘并加上结果有点相似。 所以如果某个分支不太可能被采用，那么对复杂性的贡献就会小一些。
假设您正在尝试查找未sorting数组的第k个最小元素。 sorting数组将是O（n logn）。 那么find第k个最小的数字就是find索引，所以O（1）。
由于数组已经sorting，所以我们再也不必sorting了。 我们永远不会遇到最糟糕的情况。
如果我们执行n次试图找出第k个最小的查询，它将仍然是O（n logn），因为它在O（1）上占优势。 如果我们平均每次操作的时间将是：
（n logn）/ n或O（logn）。 所以，时间复杂度/运营数量。
这是摊销的复杂性。
我想这是怎么回事，我只是在学习它..
