什么是分期分析algorithm？
与渐近分析有什么不同？ 你什么时候使用它，为什么？
我读过一些似乎写得很好的文章，比如：
-
~cs320/2010W2/handouts/aa-nutshell.pdf
-
http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf
但是我还没有完全理解这些概念。
那么，任何人都可以为我简化它吗？
对于一次调用，摊销分析并不会天真地将调用次数与最坏情况相乘。
例如，对于需要的时候大小加倍的dynamic数组，正态渐近分析只能得出结论：向它添加一个项目花费O（n），因为它可能需要增长并将所有元素复制到新数组中。 摊销分析考虑到，为了必须增长，n / 2项目必须添加，而不会导致自上一次增长以来的增长，因此添加项目实际上只需要O（1）（O（n）的成本是摊还 n / 2行动）。
摊销分析与“平均业绩”并不相同 – 摊销分析为如果您执行如此多操作时的业绩将会做什么提供了坚实的保证 。
“什么”有很多答案，但没有答案是“为什么”。
正如其他人所说，渐近分析是关于给定操作的性能如何扩展到大数据集。 摊销分析是关于大型数据集上所有操作的平均性能如何衡量。 摊销分析永远不会比渐近式给出更坏的界限，有时会给出更好的界限。
如果你担心长时间工作的总时间，分期分析的好处可能就是你所关心的。 这就是为什么脚本语言（例如）经常乐意将数组和哈希表增长一些因素，尽pipe这是一个昂贵的操作。 （增长可以是O(n)操作，但分期偿还是O(1)因为你很less这样做）。
如果您正在进行实时编程（单个操作必须在可预测的时间内完成），那么从摊销分析中获得更好的界限并不重要。 如果平均手术速度很快，如果你没有及时完成回去调整带锯，然后切割得太远，这并不重要。
在你的情况下，哪一个很重要取决于你的编程问题。
渐近分析
这个术语是指algorithm性能的分析，假设algorithm运算的数据（ input ）是用外行人的术语“足够大，使其变大不会改变结论”。 虽然不需要指定input的确切大小（我们只需要一个上限），但是必须指定数据集本身。
注意，到目前为止，我们只谈到了分析的方法 ; 我们还没有具体说明我们正在分析哪个数量 （时间复杂度？空间复杂度？），也没有指定我们感兴趣的度量 （最坏情况？最好情况？平均值？）。
实际上，渐近分析一词通常是指algorithm的上界时间复杂度 ，也就是最大情况下的总运行时间所测得的性能，用big-oh表示（例如sortingalgorithm可能是O(nlogn) ）来表示。
摊销分析
这个术语是指基于针对最坏情况的特定操作序列对algorithm性能的分析 – 也就是说，摊销分析确实意味着该度量是最差情况下的性能（尽pipe它还没有说出正在测量的数量）。 为了执行这个分析，我们需要指定input的大小 ，但是我们不需要对它的forms做任何的假设。
按照外行的说法，分期分析是为inputselect一个任意大小，然后“穿过”algorithm。 每当必须做出依赖于input的决定时，就采取最差的path¹。 algorithm运行完成后，我们将计算的复杂度除以input的大小以产生最终结果。
注：准确地说， 理论上可能的最糟糕的path。 如果每次容量耗尽时，您的vector的大小都会dynamic地增加一倍，那么“最差情况”并不意味着假设每次插入时都需要加倍，因为插入按照顺序处理。 我们被允许（甚至必须）使用已知的状态 ，尽可能地在math上消除尽可能多的“甚至更糟”的情况，即使在input未知的情况下。
最重要的区别
渐近分析和摊销分析之间的关键区别在于前者依赖于input本身，而后者依赖于algorithm执行的操作顺序。
因此：
- 渐近分析使得我们可以断言， 当给定大小接近N的最佳/最差/平均情况input时，algorithm的复杂性由某个函数F（N） – 其中N为variables
- 摊销分析允许我们断言， 当给定未知特征的input但是已知大小N的algorithm的复杂度不差于函数F（N）的值时 – 其中N是已知值
这个答案由“algorithm导论”一书的“摊销分析”一章的第一句简洁地定义：
在分期分析中 ，执行一系列数据结构操作所需的时间在所有执行的操作中取平均值。
我们通过渐近分析来表示程序增长的复杂性 – 这是通过函数来限制程序的增长，并定义了最差，最好或平均的情况。
但是，如果只有一个程序复杂度达到高峰的情况，这可能会产生误导，但总的来说，程序不需要太多计算。
因此，即使单个操作可能是昂贵的，但是在一系列操作上平均成本是更有意义的。 这是摊销分析！
摊销分析是用于计算复杂性的渐近技术的替代方法。 它帮助我们在实用性方面计算更真实的复杂度，以便在两种或更多种algorithm之间进行比较和决定。
迄今为止，我已经发现了对algorithm分期分析的最好的参考，在“ algorithm导论”第三版第17章：“摊销分析”一书中。 这一切都在那里解释好得多，可以在堆栈溢出post中find。 你会在任何像样的大学的图书馆里find这本书。
规则渐近分析逐渐考虑个体操作的性能，作为问题大小的函数。 O（）符号是什么表明一个渐近分析。
摊销分析（这也是渐近分析）着眼于共享数据结构上多个操作的总体性能。
不同之处在于，摊销分析通常certificate，M操作所需的总计算量比单个操作的最差情况下的M倍有更好的性能保证。
例如，大小为N的张开树上的单独操作可能会花费O（N）时间。 然而，一个大小为N的树上的M个操作序列由O（M（1 + logN）+ NlogN）时间约束，每个操作大致为O（logN）。 但是，请注意，摊销分析比“平均情况”分析更严格：它certificate任何可能的操作顺序都将满足其渐近的最坏情况。
摊销分析处理例行程序的总运行成本，以及可以从中获得的收益。 例如，searchn个项目的未sorting数组以进行单个匹配可能需要n次比较，因此是复杂的。 但是，如果我们知道相同的数组将要被searchm个项目，则重复总任务将具有复杂度O（m * n）。 但是，如果事先对数组进行sorting，则成本为O（n log（n）），并且对于sorting后的数组，连续search只需要O（log（n））。 因此，采用此方法的m个元素的总摊销成本为O（n * log（n）+ m * log（n））。 如果m> = n，则相对于O（n ^ 2），通过预sorting，这相当于O（n log（n）），用于不sorting。 因此，摊销成本更便宜。
简而言之，通过多花一点时间，我们可以节省很多。
