什么是算法平摊分析？ [关闭] 什么是算法平摊分析？ [关闭](What is amortiz

它是如何从渐近分析有什么不同？ 当你使用它，为什么？

我读过一些文章，似乎已经写好了，像这样的：

• http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf

• http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

但我还没有完全理解这些概念。

所以，任何人都可以请简化一下吗？

Answer 1:

平摊分析并不天真地乘调用的数量与一个调用的最坏情况。

例如，在需要的时候大小加倍动态数组，正常的渐进分析只能得出结论，将项目添加到它的成本为O（n），因为它可能需要的所有元素成长，复制到新的数组。 平摊分析考虑到为了有增长，正而不引起自上次崛起的发展必须已经加入/ 2项，因此增加一个项目真的只需要O（1）（将O的成本（n）是分摊在N / 2的操作）。

平摊分析是不一样的“平均表现” -摊销分析给出了什么，如果你做了这么多的动作性能将一个很难保证 。

Answer 2:

有很多的答案为“是什么”，但没有到“为什么”。

正如其他人所说的，渐进分析是有关给定操作的性能如何扩展到大型数据集。 平摊分析是关于所有操作的性能在大数据的平均值如何设定尺度。 平摊分析从来没有给出比渐近糟糕的界限，有时会好很多的。

如果你所关心的一个较长的作业的总运行时间，平摊分析的更好的界限可能是你关心什么。 这就是为什么脚本语言（例如）常乐用，即使是昂贵的操作一些因素增长数组和哈希表。 （成长可以是O(n)操作，但摊销是O(1)因为你做的很少。）

如果你正在做实时编程（个体经营必须完成在可预见的时间），然后平摊分析更好的界限并不重要。 这不要紧，如果平均运行很快，如果你没能完成它的时候回归，调整带锯才切得远......

哪一个问题，你的情况取决于您的编程到底是什么问题。

Answer 3:

渐近分析

这个术语指的是算法的性能，该数据的算法上进行操作（ 输入 ）的假设下的分析是，通俗地说，“足够大，使得它更大的不会改变的结论”。 虽然输入的确切大小并不需要指定（我们只需要一个上限），该数据集本身必须指定。

需要注意的是，到目前为止，我们只谈到了分析的方法 ; 我们没有指定，我们正在分析（时间复杂度？空间复杂度？）到底是哪数量 ，也没有我们指定的度 ，我们感兴趣的是（最坏的情况下？最好的情况？平均？）。

在实践中，术语渐近分析通常指的是算法的上限时间复杂度 ，即由总运行时间，这是由大哦符号表示测量的最坏情况的性能（例如一个排序算法可能是O(nlogn)

平摊分析

这个术语指的是算法的性能基础上为目标的最坏的情况下操作的特定序列的分析-也就是说，平摊分析并不意味着该指标是最坏情况下的性能（尽管它仍然不说正在测量其数量）。 进行这种分析，我们需要指定输入的大小 ，但我们并不需要就其形式做任何假设。

通俗地说，摊销分析挑选任意大小的输入，则算法“通过玩”。 每当这取决于输入一个必须作出决策，最差的路径taken¹。 该算法已经运行完毕后，我们通过将输入到产生最终结果的大小划分计算的复杂性。

¹note：为了精确， 即在理论上是可能的最差路径。 如果你有一个动态的双打每个容量用尽时大小的矢量，“最坏的情况”并不意味着假定它需要在每次插入翻一番，因为插入操作的顺序处理。 我们被允许（实际上必须）使用已知的状态 ，以数学消除许多“更糟糕”的情况下，我们可以，即使在输入仍是未知。

最重要的区别

渐近和平摊分析之间的关键区别在于，前者是依赖于输入本身，而后者则是依赖于操作的算法将执行的序列。

因此：

• 渐近分析使我们能够断言， 当它被赋予一个最高/最低/平均尺寸的情况下接近N中的输入算法的复杂度是通过一些函数F（N）为界-其中N是可变的
• 摊销分析使我们能够断言， 当它被赋予的未知特性的输入，但已知的大小N为不超过一个的函数F（N）的值更差的算法的复杂性-其中N是一个已知值

Answer 4:

这个问题的答案是简明扼要地在书的平摊分析章节的第一句话定义 - 算法导论：

在一个平摊分析 ，所需的时间来执行平均分布执行的所有操作数据结构的操作序列。

我们代表通过渐近分析程序的增长的复杂性 - 这是边界由函数程序的增长和定义的最坏，最好还是平均情况。

但是，在只有一个且该计划的复杂性达到峰值，但在一般情况下，程序并不需要太多的计算情况下，这可能是在案件误导。

因此，更有意义的平均值的一系列操作的成本，即使单一的操作可能是昂贵的。 这是平摊分析！

平摊分析是一种替代品用于计算复杂性渐近技术。 它可以帮助我们计算一个更真实的复杂性在实用性方面，以比较两个或多个算法之间做出选择。

Answer 5:

最好的参考迄今了解的算法平摊分析，我发现，在这本书算法导论 ，第三版，第17章：“平摊分析”。 这一切都没有解释什么比能在堆栈溢出后找到更好的。 你会发现这本书在任何像样的大学图书馆。

Answer 6:

定期渐近分析看个人操作渐近的性能，因为问题的大小的功能。 在O（）符号是什么指示渐近分析。

摊销分析（这也是一个渐近分析）着眼于多个操作的一个共享的数据结构 的整体性能。

不同的是，摊销分析通常证明，对于M操作所需的总计算具有更好的性能保证比M次为个体经营的最坏情况。

例如，在一个单独的操作伸展树的大小为N的可能需要多达O（N）时间。 然而，男操作对大小为N的树的序列被O为界（M（1 +日志N）+ N日志N）的时间，这是大约为O（log N）每操作。 但是请注意，摊销分析比“平均情况”分析更为严格：它证明了操作的任何可能的顺序将满足其渐近最坏的情况。

Answer 7:

平摊分析涉及了一些常规的运行总成本，而其中能够获得的好处。 例如搜索的n个项目未排序阵列用于单个匹配可能需要多达N个的比较，因此是O（N）的复杂性。 然而，如果我们知道同样的阵列将被搜索m个，重复的总任务，然后将有复杂度为O（m * n个）。 但是，如果我们事先对数组进行排序，成本是O（n的log（n）），并且连续的搜索只需要O（日志（N））的排序的数组。 因此，对于采用这种方法m个元素的总摊销成本为O（n *的log（n）+ M *的log（n））。 如果M> = N，这相当于为O（n的log（n）），由相对于为O（n ^ 2）为未分选预分类。 因此，摊余成本比较便宜。

简单地说，通过早期花一点额外的，我们以后可以节省很多。

文章来源: What is amortized analysis of algorithms? [closed]