線性搜索的平均情況

我有一個元素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

回答