线性搜索的平均情况

我有一个元素A1，A2，...，An的数组。线性搜索的平均情况

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

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

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

听起来像一个家庭作业问题。你怎么看？ –

-1

没有，因为它需要O（1）时间在阵列访问一个元件，它不依赖于在此阵列元件的位置。所以arr[0]和arr[10000]应该花费相同的时间。

如果你有类似于链表或二叉树的东西，那么把以更高概率访问的元素放在更靠近开头的位置是有意义的。

2016-03-01 07:29:46

@polasairam我认为它正是OP所要求的答案。你能解释为什么它没有任何关系（谁知道可能是我误解了它） –

我似乎也找到了你的答案。我认为OP在询问线性搜索的平均性能：“当元素（有相应的搜索概率）被重新排序时它会改变吗？”。看到polasairam撤回他的回答和评论，我现在可能是误会。 –

问题不在于元素访问，而在于线性搜索 – Paul

预期的比较次数是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

2016-03-01 13:00:02

回答