寻找算法的平均情况复杂度？

Question

我对查找平均复杂度很困惑，以随机问题为例...

假设有一个哨兵顺序查找问题，如果概率是0 <= p <= 1，请找出平均情况下的结果。

最坏情况下，当数组中有n个元素时，加上末尾添加的关键字元素，时间复杂度为O(n+1)。最好情况下，如果您立即找到它，则时间复杂度为O(1)。

我并不是只想要答案...而是更想知道如何计算，如果只想要答案，我想我会去找解答手册。

- Carson Wood

---

你的问题是什么？ - SegFault

关于概率的部分几乎是无关紧要的。它只意味着“不知道搜索是否成功”。因此，答案是O(n+1)，或者如果计算结尾三元运算符中的比较，则可能为O(n+2)。不管怎样，重要的部分是哨兵搜索的性能是“线性时间”，也就是说，它随元素数量成线性比例增长。相对于二次/指数等时间而言。 - Aaron Brager

什么是“概率为0 <= p <= 1”的意思？ - Paul Hankin

Answer 1

你说得对，“平均情况复杂度”需要仔细定义算法和可能的输入集。

搜索整数线性列表所需的比较次数提供了一个例子。

如果输入的搜索键可以是任意整数，则平均结果是整个列表将被搜索（需要n+1次比较才能找到哨兵），因为有无限多个整数，而数组中只有有限数量的元素。只有有限数量的输入将需要少于n+1次比较，但无限多个将导致n+1。

另一方面，如果分析的是在数组中（均匀）随机选择搜索键时的平均比较次数（并且这些元素不包含重复项），则可能结果的平均值将是搜寻项目在列表中第一项时的比较次数加上当它是第二项时的比较次数，以此类推，直到第n项，所有这些再除以结果数，即n。换句话说，

(1 + 2 + ... n) / n = n(n+1)/(2n) = (n + 1) / 2

这里有一个健全性检查：让n=1。那么这个公式表明，在一个只有一个元素的列表中找到元素的平均比较次数是一。这显然是正确的。

最后需要注意的是，你提出问题的方式表明你应该学习大O符号的定义。O(n)与O(n+1)相同。而大O符号总是对所测量的任何东西的上限表达式。通常不适合在平均情况分析中表达上限，因为平均情况分析通常也提供了下限。上面的（n+1）/2次比较最好在平均情况下表示为\Theta(n)。

- Gene

---

"And big-O is always an expression of "worst" case behavior in that it states only an upper bound." - 我们可以用大O表示平均情况的运行时间。坚持认为大O总是表示最坏情况有时会误导新手。 - Aravind

谢谢，现在更加清晰了！ - Carson Wood

如果有重复怎么办？如果搜索键的取值范围在大小为d的有限域中，平均复杂度似乎是恒定的，但我很难形式化这一点。 - scand1sk