algorithm - 平均案例与摊销分析之间的差异

Question

我正在阅读一篇关于算法的摊销分析的文章。以下是文本片段。

Amortized analysis is similar to average-case analysis in that it is concerned with the cost averaged over a sequence of operations. However, average case analysis relies on probabilistic assumptions about the data structures and operations in order to compute an expected running time of an algorithm. Its applicability is therefore dependent on certain assumptions about the probability distribution of algorithm inputs.

An average case bound does not preclude the possibility that one will get “unlucky” and encounter an input that requires more-than-expected time even if the assumptions for probability distribution of inputs are valid.

我对以上文本片段的问题是:

1. 在第一段中，平均案例分析如何“依赖于关于数据结构和操作的概率假设？”我知道平均案例分析取决于输入的概率，但上面的说法是什么意思？

2. 即使输入分布有效，作者在第二段中的平均情况无效是什么意思？

谢谢!

Answer 1

平均案例分析对某些情况下可能无法满足的输入做出假设。因此，如果您的输入不是随机的，那么在最坏的情况下，算法的实际性能可能比平均情况慢得多。

摊销分析没有做出这样的假设，但它考虑了一系列操作的总体性能，而不是仅考虑一个操作。

动态数组插入提供了一个简单的摊销分析示例。一种算法是分配一个固定大小的数组，并在插入新元素时，在必要时分配一个两倍于旧长度的固定大小数组。在最坏的情况下，插入所需的时间可能与整个列表的长度成正比，因此在最坏的情况下，插入是一个 O(n) 操作。但是，您可以保证这种最坏的情况很少见，因此插入是一个使用摊销分析的 O(1) 操作。无论输入是什么，均摊分析都成立。