Gro*_*Man 79 algorithm analysis amortized-analysis
它与渐近分析有什么不同？你什么时候使用它,为什么？
我读过一些似乎写得很好的文章,比如:
http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf
http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf
但我还是没有充分理解这些概念.
所以,有人可以为我简化吗？
har*_*old 81
对于一次调用,摊销分析不会天真地将调用次数与最坏情况相乘.
例如,对于需要时大小翻倍的动态数组,正态渐近分析只会得出结论,向其中添加项目需要花费O(n),因为它可能需要增长并将所有元素复制到新数组.摊销分析考虑到为了必须增长,必须添加n/2项而不会导致自上一次增长以来增长,因此添加项目实际上只需要O(1)(O(n)的成本是在n/2个行动中摊销).
摊销分析与"平均绩效"不同 - 摊销分析可以很好地保证如果您采取这么多措施,绩效将会如何.
bti*_*lly 42
"什么"有很多答案,但没有"为什么".
正如其他人所说的那样,渐近分析是关于给定操作的性能如何扩展到大型数据集.摊销分析是关于大型数据集上所有操作的平均性能如何扩展.摊销分析从来没有给出比渐近更差的边界,有时会给出更好的分析.
如果您担心较长工作的总运行时间,那么摊销分析的更好界限可能就是您关心的问题.这就是为什么脚本语言(例如)通常很乐意通过某种因素来增长数组和哈希表,即使这是一项昂贵的操作.(增长可能是一项O(n)操作,但摊销是O(1)因为你很少这样做.)
如果您正在进行实时编程(个别操作必须在可预测的时间内完成),那么摊销分析的更好界限无关紧要.无论平均操作是否很快,如果你没能及时完成它并且在切割太远之前调整带锯,这并不重要......
在您的情况下哪一个重要取决于您的编程问题究竟是什么.
Jon*_*Jon 24
这个术语指的是算法性能的分析,假设算法运算的数据(输入)是外行的术语,"足够大,使其变大不会改变结论".虽然输入的确切大小并不需要指定(我们只需要一个上限),该数据集本身具有被指定.
请注意,到目前为止,我们只讨论了分析方法 ; 我们没有准确指出我们正在分析的数量(时间复杂度？空间复杂度？),我们也没有指定我们感兴趣的指标(最坏情况？最佳情况？平均值？).
在实践中,术语渐近分析通常是指算法的上限时间复杂度,即由总运行时间测量的最坏情况性能,其由大哦符号表示(例如,排序算法可能是O(nlogn)).
该术语指的是基于针对最坏情况的特定操作序列的算法性能分析- 即,摊销分析确实意味着该度量是最差情况下的性能(尽管它仍然没有说明正在测量哪个数量) ).要执行此分析,我们需要指定输入的大小,但我们不需要对其形式做任何假设.
通俗地说,摊销分析是为输入选择任意大小,然后"通过"算法.每当必须作出取决于输入的决定时,最坏的路径是¹.在算法运行完成后,我们将计算的复杂度除以输入的大小以产生最终结果.
¹note:确切地说,是理论上可能的最差路径.如果每次容量耗尽时都有一个动态加倍的向量,"最坏情况"并不意味着假设每次插入都需要加倍,因为插入是作为序列处理的.我们被允许(并且确实必须)使用已知状态来数学地消除尽可能多的"甚至更糟"的情况,即使输入仍然未知.
渐近和摊销分析之间的关键区别在于前者依赖于输入本身,而后者依赖于算法将执行的操作序列.
因此:
Kun*_*yas 13
对此的答案由"算法导论"一书中的"摊销分析"一章的第一句简洁定义:
在摊销分析中,执行一系列数据结构操作所需的时间对所执行的所有操作进行平均.
我们通过渐近分析来表示程序增长的复杂性 - 这是通过函数限制程序的增长并定义最差,最佳或平均情况.
但是,如果只有一种情况下程序的复杂性达到峰值,那么这可能会产生误导,但总的来说,程序并不需要太多的计算.
因此,即使单个操作可能很昂贵,在一系列操作中平均成本也更有意义.这是摊销分析!
摊销分析是用于计算复杂性的渐近技术的替代方法.它有助于我们在实用性方面计算更真实的复杂性,以便在两个或更多算法之间进行比较和决定.