91

它与渐近分析有何不同？你什么时候使用它，为什么？

我读过一些似乎写得很好的文章，比如：

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

那么，任何人都可以为我简化它吗？

4

7 回答 7

92

摊销分析不会天真地将调用次数乘以一次调用的最坏情况。

例如，对于一个在需要时大小翻倍的动态数组，正常的渐近分析只会得出结论，向其中添加一个项目的成本为 O(n)，因为它可能需要增长并将所有元素复制到新数组中。摊销分析考虑到，为了必须增长，必须添加 n/2 个项目而不会导致自上次增长以来的增长，因此添加一个项目实际上只需要 O(1)（O(n) 的成本是按n/2 次行动摊销）。

摊销分析与“平均绩效”不同 - 摊销分析对执行如此多操作时的绩效提供了硬性保证。

于 2012-06-19T14:13:44.477 回答
47

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

正如其他人所说，渐近分析是关于给定操作的性能如何扩展到大型数据集。摊销分析是关于大型数据集上所有操作的平均性能如何扩展。摊销分析从未给出比渐近的界限更差的界限，有时会给出更好的界限。

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

如果您正在进行实时编程（单个操作必须在可预测的时间内完成），那么摊销分析的更好界限并不重要。平均而言，操作是否快速并不重要，如果您未能及时完成操作以在带锯切得太远之前返回并调整带锯......

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

于 2012-06-19T17:37:29.610 回答
27

渐近分析

该术语是指在假设算法操作的数据（输入）是“足够大，使其变大不会改变结论”的假设下对算法性能的分析。虽然不需要指定输入的确切大小（我们只需要一个上限），但必须指定数据集本身。

请注意，到目前为止，我们只讨论了分析方法；我们没有具体说明我们正在分析哪个量（时间复杂度？空间复杂度？），也没有指定我们感兴趣的指标（最坏情况？最好情况？平均？）。

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

摊销分析

该术语是指基于针对最坏情况的特定操作序列对算法性能的分析——也就是说，摊销分析确实意味着该指标是最坏情况的性能（尽管它仍然没有说明正在测量的量）。要执行此分析，我们需要指定输入的大小，但我们不需要对其形式做出任何假设。

用外行的话来说，摊销分析是为输入选择任意大小，然后“玩转”算法。每当必须做出取决于输入的决定时，都会采取最坏的路径¹。在算法运行完成后，我们将计算的复杂度除以输入的大小以产生最终结果。

¹注意：准确地说，是理论上可能的最坏路径。如果您有一个向量在每次容量耗尽时动态加倍，“最坏情况”并不意味着假设它在每次插入时都需要加倍，因为插入是作为序列处理的。我们被允许（并且确实必须）使用已知状态在数学上尽可能多地消除“更糟糕”的情况，即使输入仍然未知。

最重要的区别

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

所以：

  • 渐近分析允许我们断言，当给定大小接近 N 的最佳/最差/平均情况输入时，算法的复杂性受某个函数 F(N) 的限制——其中 N 是一个变量
  • 摊销分析允许我们断言，当给定一个未知特征但已知大小 N 的输入时，算法的复杂性并不比函数 F(N) 的值差——其中 N 是一个已知值
于 2012-06-19T14:38:42.813 回答
16

本书“摊销分析”一章的第一句话简洁地定义了这个问题的答案——算法简介：

在摊销分析中，执行一系列数据结构操作所需的时间是所有执行操作的平均时间。

我们通过渐近分析来表示程序增长的复杂性——它通过一个函数来限制程序的增长，并定义最坏、最好或平均的情况。

但是，在只有一种情况下程序的复杂性达到峰值的情况下，这可能会产生误导，但一般来说，程序不需要太多的计算。

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

摊销分析是用于计算复杂性的渐近技术的替代方法。它帮助我们在实用性方面计算出更真实的复杂度，以便在两种或多种算法之间进行比较和决定。

于 2015-02-28T08:09:54.850 回答
5

到目前为止，我找到的关于算法摊销分析的最佳参考资料，在《算法简介》，第三版，第 17 章：“摊销分析”一书中。一切都在那里，解释得比 Stack Overflow 帖子中的内容要好得多。你会在任何像样的大学的图书馆里找到这本书。

于 2012-06-19T14:14:20.703 回答
2

常规渐近分析渐近地查看单个操作的性能，作为问题大小的函数。O() 符号表示渐近分析。

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

不同之处在于，摊销分析通常证明，M 次操作所需的总计算量比单个操作的最坏情况的 M 倍具有更好的性能保证。

例如，对大小为 N 的展开树的单个操作可能需要 O(N) 时间。然而，在大小为 N 的树上的一系列 M 操作的边界为 O( M(1+log N) + N log N ) 时间，每个操作大约是 O(log N)。但是，请注意，摊销分析比“平均情况”分析严格得多：它证明任何可能的操作序列都将满足其渐近最坏情况。

于 2012-06-19T17:02:25.910 回答
1

摊销分析处理例行程序多次运行的总成本，以及从中可以获得的收益。例如，在一个未排序的 n 项数组中搜索单个匹配项可能需要进行 n 次比较，因此复杂度为 o(n)。但是，如果我们知道要在同一个数组中搜索 m 个项目，那么重复整个任务将具有 O(m*n) 的复杂度。但是，如果我们提前对数组进行排序，则成本为 O(n log(n))，并且连续搜索对排序后的数组只需 O(log(n))。因此，采用这种方法的 m 个元素的总摊销成本为 O(n*log(n) + m*log(n))。如果 m >= n，这相当于 O(n log(n)) 通过预排序与 O(n^2) 相比不排序。因此，摊销成本更便宜。

简而言之，通过在早期多花一点，我们可以在以后节省很多。

于 2012-06-19T14:19:24.403 回答