摊还是否真的令人满意？

Question

例如,假设我有一个算法是O(n),算法是一个摊销的O(n).可以公平地说,在严格意义上说,非摊销算法总是会比摊销算法快或快吗？或者是否有任何理由更喜欢分期付款的版本(忽略代码简单或易于实现)？

Answer 1

1. Big O表示法仅告诉您代码如何缩放,而不是有限N的速度.
2. 如果您关心最坏情况的性能或延迟(例如实时或交互式系统),则摊销和非摊销之间的差异非常重要.但是,如果你只关心平均吞吐量,它们的实际用途是相同的.即使在科学计算和大规模数据挖掘等一些非常关键的性能情况下,摊销分析也足够好.

Answer 2

或者是否有任何理由更喜欢摊销版本

较小的常数.

Answer 3

O(n)算法和摊销的O(n)算法之间的主要区别在于您对摊销的O(n)算法的最坏情况行为一无所知.在实践中,这并不常见:如果您的算法运行多次,那么您可以依靠平均律来平衡一些不良情况,如果您的算法没有运行很多次,那么你根本不可能遇到最糟糕的情况.

"摊销"一词应该重要的唯一情况是,由于某种原因你不能接受偶尔的不良表现.例如,在GUI应用程序中,您可以愉快地放弃一些平均情况下的性能,以换取保证,当用户坐在那里并感到无聊时,您永远不会陷入困境并停止响应.在这些应用程序中,您希望确保即使是最坏情况的行为也适用于任何可能导致GUI停止响应的代码.

尽管如此,大多数时候,你不需要担心摊销的O(n)与O(n),而你可以担心常数因素是什么(正如其他人已经说过的那样).