http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf
http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf
但我仍然没有完全理解这些概念。
所以，有人可以为我简化一下吗？
摊销分析不是简单地将调用次数乘以一个调用的最坏情况。
例如，对于动态数组在需要时会翻倍大小，常规的渐近分析只会得出添加一个项的成本为O(n)，因为它可能需要增长并复制所有元素到新数组。摊销分析考虑到为了增长，必须添加n/2个项而不引起增长自上次增长以来，因此添加一个项实际上只需要O(1)（O(n)的成本摊销在n/2个操作上）。
摊销分析与“平均性能”不同-摊销分析提供了一个硬性保证，即如果执行了这么多操作，性能将做什么。
有很多关于“什么”的答案，但是没有关于“为什么”的答案。
正如其他人所说，渐近分析是关于给定操作在大数据集上的性能缩放的方式。摊销分析是关于所有大数据集上操作的性能平均值如何缩放的方式。摊销分析从不给出比渐近分析更差的界限，有时会给出更好的界限。
如果您关心较长作业的总运行时间，那么摊销分析的更好界限可能是您关心的问题。这就是为什么脚本语言（例如）经常愿意通过某个因素来增加数组和哈希表，即使这是一项昂贵的操作。（增长可以是 O(n)操作，但摊销是 O(1)，因为它不经常执行。）
如果您正在进行实时编程（单个操作必须在可预测时间内完成），那么摊销分析的更好边界就无关紧要了。如果您没有及时完成操作，不能及时返回并调整链锯，那么平均速度是否快就不重要了...
哪一个对您的情况最重要取决于您的编程问题究竟是什么。
这个术语指的是在算法操作的数据（即输入）“足够大，使得进一步增加其大小不会改变结论”的假设下进行的算法性能分析。虽然不需要指定输入的确切大小（我们只需要上限），但必须指定数据集本身。
需要注意的是，到目前为止，我们只谈到了分析的方法；我们还没有具体说明我们正在分析哪些量（时间复杂度？空间复杂度？），也没有说明我们感兴趣的是哪个指标（最坏情况？最好情况？平均情况？）。
实际上，渐近分析通常指的是算法的上界时间复杂度，即总运行时间的最坏情况性能，用大O符号表示（例如，排序算法可能是 O(nlogn) ）。
这个术语指的是基于针对最坏情况场景的特定操作序列来分析算法性能，尽管摊销分析并不指明被测量的是哪个量（仍然没有说明是时间复杂度还是空间复杂度），但它确实表明了度量指标是最坏情况性能。为了执行这种分析，我们需要指定输入的大小，但不需要做出任何关于其形式的假设。
用通俗易懂的话来说，摊销分析是选择一个任意的输入大小，然后“播放”算法。每当必须做出依赖于输入的决策时，都采取最坏的路径¹。算法完成后，将计算出的复杂度除以输入的大小即可得出最终结果。
¹注：精确来说，这是理论上最差的情况。如果您有一个向量，在其容量用尽时每次动态扩大两倍，“最坏情况”并不意味着假定它将在每次插入时都需要扩大，因为插入是按序列处理的。我们可以（实际上必须）使用已知的状态在数学上消除尽可能多的“更糟糕”的情况，即使输入仍然未知。
渐进分析与分摊分析的关键区别在于前者取决于输入本身，而后者取决于算法执行的操作序列。
因此：
这个问题的简洁定义来自于《算法导论》中的分摊分析章节的第一句话：
在分摊分析中，执行数据结构操作所需的时间是对进行的所有操作进行平均。
我们通过渐进分析来表示程序增长的复杂度——也就是通过一个函数限制程序的增长，并定义该函数的最坏、最好或平均情况。
但是，在只有一个情况会导致程序复杂度达到峰值的情况下，使用渐进分析可能会误导人们，而实际上程序并不需要太多计算。
因此，即使单个操作可能很昂贵，在一系列操作中平均成本更有意义。 这就是分摊分析！
分摊分析是用于计算复杂度的另一种方法，它是渐进技术的替代品。它可以帮助我们以实用性为基础计算出更真实的复杂度，以便比较和决定两个或多个算法之间的差异。
