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

为了获得平均情况下的时间复杂度，您需要对“平均情况”进行假设。如果输入是字符串，那么“平均字符串”是什么？只有长度重要吗？如果是这样，我得到的平均字符串长度是多少？如果不是，那么这些字符串中的平均字符是多少？如果字符串是例如姓氏，则很难确定地回答这些问题。平均姓氏是什么？

在大多数有趣的统计样本中，最大值大于平均值。这意味着您的平均案例分析有时会低估某些输入（有问题的）所需的时间/资源。如果考虑一下，对于对称的PDF，平均案例分析应该低估或高估它。最糟糕的案例分析OTOH仅考虑问题最多的案例，因此可以肯定会高估。