我正在阅读一篇有关算法的摊销分析的文章。以下是文本片段。
摊销分析与平均案例分析相似，因为它涉及一系列操作的平均成本。但是，平均用例分析依赖于有关数据结构和操作的概率假设，以便计算算法的预期运行时间。因此，它的适用性取决于关于算法输入的概率分布的某些假设。 平均情况下的情况并不排除以下可能性：即使输入概率分布的假设是正确的，也可能会遇到“不幸”的情况，并且遇到需要比预期多的时间的输入。
摊销分析与平均案例分析相似，因为它涉及一系列操作的平均成本。但是，平均用例分析依赖于有关数据结构和操作的概率假设，以便计算算法的预期运行时间。因此，它的适用性取决于关于算法输入的概率分布的某些假设。
平均情况下的情况并不排除以下可能性：即使输入概率分布的假设是正确的，也可能会遇到“不幸”的情况，并且遇到需要比预期多的时间的输入。
我对上述文本片段的疑问是：
在第一段中，平均案例分析如何“依赖于有关数据结构和操作的概率假设？” 我知道平均情况分析取决于输入的概率，但是以上陈述是什么意思？
在第二段中，作者认为即使输入分布有效，平均大小写也不成立？
谢谢！
为了获得平均情况下的时间复杂度，您需要对“平均情况”进行假设。如果输入是字符串，那么“平均字符串”是什么？只有长度重要吗？如果是这样，我得到的平均字符串长度是多少？如果不是，那么这些字符串中的平均字符是多少？如果字符串是例如姓氏，则很难确定地回答这些问题。平均姓氏是什么？
在大多数有趣的统计样本中，最大值大于平均值。这意味着您的平均案例分析有时会低估某些输入（有问题的）所需的时间/资源。如果考虑一下，对于对称的PDF，平均案例分析应该低估或高估它。最糟糕的案例分析OTOH仅考虑问题最多的案例，因此可以肯定会高估。
