algorithm - 线性搜索的平均案例复杂度

Question

所有教程和维基百科都说平均情况的线性搜索的复杂度是n/2。我知道准确的答案是(n+1)/2，它来自公式(1+2+...+n)/n。

我的问题是，为什么消息来源说 n/2 而不是 (n+1)/2？他们没有错吗？

标签： algorithmtime-complexitylinear-search

Answer 1

由@PaulHankin 回答

维基百科说“如果每个元素被搜索的可能性相同，那么线性搜索的平均情况为 (n+1)/2 比较，但如果每个元素的搜索概率不同，则平均情况可能会受到影响。” 尽管在侧框中它说平均性能是 O(n/2)。因为 (n+1)/2 = O(n/2) = O(n)

由@Stef 回答

n/2 和 (n+1)/2 不仅仅是彼此的大哦。它们是渐近等价的。