例如，假设我有一个 O(n) 的算法和一个摊销 O(n) 的算法。公平地说，严格来说，非摊销算法总是与摊销算法一样快或更快吗？或者是否有任何理由更喜欢摊销版本(忽略诸如代码简单性或易于实现之类的东西)？
最佳答案
O(n) 算法和摊销 O(n) 算法之间的主要区别在于，您对摊销 O(n) 算法的最坏情况行为一无所知。在实践中，这并不重要:如果您的算法运行了很多次，那么您可以依靠平均法则来平衡一些不好的情况，如果您的算法没有运行很多次，那么你根本不可能遇到最坏的情况。
“摊销”一词唯一重要的情况是您无法接受出于某种原因偶尔出现的糟糕表现的情况。例如，在 GUI 应用程序中，您很乐意放弃一些一般情况下的性能，以换取保证您永远不会在用户坐在那里感到无聊时陷入困境并停止响应。在此类应用程序中，您希望确保即使是最坏情况的行为也适用于可能导致 GUI 停止响应的任何代码。
尽管如此，在大多数情况下，您不需要担心摊销 O(n) 与 O(n)，而您可以担心常数因子是什么(正如其他人已经说过的那样)。
关于algorithm - 摊销真的是可取的吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2308310/