平均情况与摊销分析之间的差异

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

摊销分析与平均情况分析类似，因为它是 关注一系列操作的平均成本。 然而，平均情况分析依赖于概率假设 关于数据结构和操作，以便计算 算法的预期运行时间。因此它的适用范围是 取决于关于概率分布的某些假设 算法输入。

平均情况下的界​​限并不排除人们将 “不幸”并遇到需要超出预期的输入 即使输入概率分布的假设是 有效的。

我对上述文本片段的疑问是：

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

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

Thanks!

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

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

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