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

Question

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

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

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

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

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

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

谢谢！

Answer 1

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

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

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

Answer 2

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

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

Answer 3

1. 考虑未排序数组中最小值的计算。也许您知道它有

   O(n)

   运行时间，但如果我们想要更精确，它会在平均情况下进行

   n/2

   比较。为什么这个？因为我们正在对数据做假设；我们假设最小值可以以相同的概率出现在每个位置。 如果我们改变这个假设，并且我们说处于第 i 个位置的概率随着 i 的增加而增加，我们可以证明不同的比较数，甚至是不同的渐近界限。

2. 在第二段中，作者说，通过平均案例分析，我们可能会非常不幸，测量到的平均案例大于理论案例；回想一下前面的例子，如果我们不幸在 m 个大小为 n 的不同数组上，并且最小值每次都在最后一个位置，那么我们将测量

   n

   平均情况，而不是

   n/2

   。当摊销界限得到证明时，这不可能发生。

Answer 4

简单来说， 平均案例分析适用于单个操作，而摊销分析适用于一系列操作的平均性能。

例如，对于动态数组插入：

平均时间复杂度为

O(1) AND occasional O(n)

摊余时间复杂度在哪里

O(3n) - log(n) - 2 which is O(n)