順序搜索

對於順序搜索，在文件中查找記錄所需的平均比較次數是多少？順序搜索

來源

2010-03-06 neuromancer

A sequential search從文件的開頭開始逐個檢查每個元素，直到找到所需的元素。假設您正在搜索的記錄只存在於文件中一次，並且可能在文件中的任何位置具有相同的概率，則平均比較次數等於文件中記錄數量的一半。

但是，如果記錄不存在於文件中，則在發現該文件之前，必須檢查文件中的每個記錄。

來源

2010-03-06 17:24:27

而且當值不在文件中時，記錄所有記錄的最壞情況。 – 2010-03-06 17:25:47

我也將它看作（n + 1）/ 2。爲什麼n + 1？ – neuromancer 2010-03-06 18:23:41

@Phenom：這是因爲你可以從兩個不同的假設開始。如果您假設您知道該條目在文件中，並且您只需要查找索引，則最小比較次數爲1，最大次數爲（n-1），平均值爲（（n-1）+ 1）/ 2 = n/2。如果您假設您不知道條目在文件中的最小值爲1，則最大值爲n，因此在元素位於文件中時平均值爲（n + 1）/ 2，並且n如果不是。 – 2010-03-06 18:39:35

對於包含n個項目的列表，最好的情況是該值等於列表的第一個元素，在這種情況下只需要一個比較。最壞的情況是該值不在列表中（或僅在列表末尾出現一次），在這種情況下需要進行n次比較。

Asymptotically，因此，最壞情況下的成本和線性搜索的預期成本都爲O（n）

來源

2010-03-06 17:30:11

我想補充幾點，以前的答案未能指出：

另一方面，我們必須考慮文件是在一臺設備上可用還是分佈在多臺設備上。在T rams的情況下，複雜性將是O(T*N/(1+log(T)))。
一般來說，順序搜索需要O(N) time complexity。
與R-Tree等數據結構結合使用時，在文件記錄情況下，它可以給出O(N/(log(log(N))))的最佳時間複雜度。
它取決於文件的結構/格式，這樣如果數據字段在哈希映射中可用，順序搜索就是積壓。

來源

2017-06-15 05:22:12

回答

相關問題