algorithm - 线性搜索的平均情况

Question

我有一个元素数组 A1,A2,...,An。

用户搜索每个元素的概率为 P1,P2,...,Pn。

如果元素重新排列，算法的平均情况会改变吗？

编辑：我已经发布了这个问题，它出现在我的考试中。

Answer 1

预期的比较次数为 sum_{i=1...n}(i * p_i)。

以降序对元素重新排序会降低期望值。这很直观，因为首先查看最可能的选择会平均减少在找到特定选择之前查看的元素数量。

例如，假设有三个项目 k1、k2、k3，匹配概率分别为 10%、30% 和 60%。

那么按照k1、k2、k3的顺序，期望的比较次数是1*0.1 + 2*0.3 + 3*0.6 = 2.5

最可能的第一个：k3、k2、k1，预期比较次数为 1*0.6 + 2*0.3 + 3*0.1 = 1.5

Answer 2

不，因为访问数组中的元素需要 O(1) 时间，并且它不依赖于该元素在数组中的位置。因此arr[0]，arr[10000]应该花费相同的时间。

如果您将拥有诸如链表或二叉树之类的东西，那么将访问概率较高的元素放在更靠近开头的位置是有意义的。