順序搜索作業問題

2010-03-09 75 views 0 likes

考慮包含100條記錄的磁盤文件 a。如果記錄已知在文件中，那麼平均需要多少次比較來查找使用順序搜索的記錄？順序搜索作業問題

我發現這是100/2 = 50.

b。如果記錄在文件中的概率爲68％，平均需要多少次比較？

這是我遇到麻煩的部分。起初，我認爲這是68％* 50，但後來意識到這是錯誤的考慮後。然後我認爲這是（100％ - 68％）* 50，但我仍然認爲這是錯誤的。任何提示？

把它在兩種情況下：當記錄在該文件中，當它不是。分別計數。 – 2010-03-09 03:35:58

回答

我想把它分解成加權平均數。

它存在於文件中的概率爲68％在這種情況下，從第一部分的結果中需要平均50次比較。

記錄不在文件中的概率爲32％在這種情況下，您需要查看每條記錄，即100個比較。

平均0.68 * 50 + 0.32 * 100 = 66比較。

但因爲我承擔了概率當然，已經有一段時間...

2010-03-09 03:37:06 Peter

是不是0.32 * 99，因爲對於100個記錄進行99次比較，而不是100次。 – neuromancer 2010-03-09 03:54:15

您將如何進行99次比較？如果有100條記錄，並且您不確定您正在搜索的記錄是否存在，您是否不必使用順序搜索來查看每條記錄？ – Peter 2010-03-09 04:19:08

我想我對「比較」一詞感到困惑，認爲你是在比較數字。 – neuromancer 2010-03-09 04:28:44

相關問題