我正在阅读一篇有关算法摊销分析的文章，以下是其中一段文字。
摊销分析类似于平均情况分析，因为它关注的是操作序列的平均成本。 然而，平均情况分析依赖于关于数据结构和操作的概率假设， 以便计算算法的预期运行时间。因此，它的适用性取决于有关算法输入的概率分布的某些假设。
平均情况下的上限并不能排除即使输入概率分布的假设是正确的， 也可能出现需要比预期更长时间的输入的“不幸”情况。
关于上述文本片段，我的问题如下:
在第一段中，平均情况分析如何“依赖于关于数据结构和操作的概率假设？” 我知道平均情况分析取决于输入的概率，但这句话是什么意思？
在第二段中，作者指的平均情况下无效即使输入分布是有效的是什么意思？
谢谢!
平均情况分析对输入做出了一些可能在某些情况下不被满足的假设，因此，如果您的输入不是随机的，算法的实际性能在最坏情况下可能比平均情况慢得多。
摊销分析不做这样的假设，而是考虑一系列操作的总体表现，而不仅仅是一个操作。
动态数组插入提供了一个简单的摊销分析例子。一种算法是分配一个固定大小的数组，在需要时分配一个大小为旧长度两倍的固定大小的数组以插入新元素。在最坏情况下，插入可能需要与整个列表长度成比例的时间，因此在最坏情况下插入是O(n)操作。但是，可以保证这种最坏情况很少发生，因此使用摊销分析，插入是一个O(1)操作。无论输入如何，摊销分析都是成立的。
要计算平均情况下的时间复杂度，你需要对“平均情况”做出一些假设。如果输入是字符串，那么“平均字符串”是什么？仅长度是否重要？如果是，那么我将得到的字符串的平均长度是多少？如果不是，那么这些字符串中的平均字符是什么？如果字符串是姓氏等名称，回答这些问题确实变得比较困难。那么平均姓氏是什么？
在大多数有趣的统计样本中，最大值大于平均值。这意味着平均情况分析有时会低估某些输入（这些输入是有问题的）所需的时间/资源。如果你仔细想一下，对于一个对称的概率密度函数，平均情况分析应该低估和高估一样多。另一方面，最坏情况分析只考虑最有问题的情况，因此肯定会高估。
考虑在未排序的数组中计算最小值。也许您知道它具有O（n）运行时间，但如果我们想更精确，平均情况下会进行n/2次比较。为什么会这样？因为我们对数据做了一个假设;我们假设最小值可能以相同的概率出现在每个位置。
如果我们改变这个假设，并且说例如i位置的概率随着i的增加而增加，我们可以证明不同的比较数，甚至是不同的渐近界限。
在第二段中，作者说通过平均情况分析，我们可能会非常不幸，测得的平均情况大于理论情况；回想一下之前的例子，如果我们在m个大小为n的不同数组中不幸地每次都将最小值放在最后一个位置，那么我们将测量出n的平均情况，而不是n/2。当证明摊销界限时，这种情况不会发生。
