algorithm - 查找算法的平均案例复杂度？

Question

我在寻找平均案例复杂性方面非常迷茫，只是拉出一个随机问题......比如。

对于哨兵顺序搜索，如果概率为 0 <= p <= 1，则找到平均情况。

我得到的最坏情况是 O(n+1)，因为数组中将有 n 个元素加上您在末尾添加的键的额外元素。如果您立即找到它，最好的情况就是 O(1)。

我并不是真的想要答案……但更多的是……如果我只是想要答案，我想我只会看一本解决方案手册。

Answer 1

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

搜索线性整数列表所需的比较次数就是一个例子。

如果输入的搜索关键字可以是任意整数，那么平均的结果是整个列表都会被搜索(需要n+1次比较才能找到sentinel)，因为整数有无限多而元素只有有限多大批。只有有限数量的输入需要少于 n+​​1 次比较，但无限多会导致 n+1。

另一方面，如果分析是从数组中的元素(均匀地)随机选择搜索键(并且这些元素不包含重复项)时的平均比较次数，则可能结果的平均值将是搜索项在列表中排在第一位时的比较次数加上它在列表中排在第二位时的次数，等等，直到第 n 项，再除以结果数，即 n。换句话说，

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

这里是完整性检查:设 n=1。然后公式表示在 1 元素列表中查找元素的平均比较次数为 1。这显然是正确的。

最后要注意的是，您提出问题的方式表明您应该研究大 O 的定义。 O(n) 与 O(n+1) 相同。大 O 始终表示所测量的上限。表示平均值的上限通常是不合适的，因为平均案例分析通常也会提供下限。上面的 (n+1)/2 比较在平均情况下最好表示为\Theta(n)。