散列表在鏈接中成功搜索的平均成本

我已經搜索了每個地方，但我無法理解爲什麼是O（1 + a/2）其中a是加載因子。有人可以一步一步解釋這一點。散列表在鏈接中成功搜索的平均成本

來源

2015-04-05 user4129542

讓散列表中元素的數量爲n。
這意味着有n/a散列表中的單元（/行）總數，每個單元都包含元素列表。這是載荷係數的定義。

因此，與每個這樣的單元相關聯的元件的預期數量是n/(n/a) = a。
未排序列表中的線性搜索需要遍歷一半元素，直到平均找到正確的元素（並且我們假設它是成功的搜索），因此它需要遍歷a/2元素。

1因素來自哈希表本身訪問正確的列表。

來源

2015-04-05 15:15:22 amit

未排序列表中的線性搜索需要遍歷一半元素。這是我不明白的。爲什麼？這可能是所需要的元素在列表的末尾，那麼爲什麼我們只需要遍歷一半呢？ – user4129542 2015-04-05 15:19:47

平均而言：有時它是第一個，有時是最後一個，平均它是元素數量的一半。 – 2015-04-05 15:20:45

@ user4129542我省略了「平均」一詞，這在這裏很重要。直觀地說，它有50％的機率成爲最後的元素，50％成爲第一。（更詳盡的證明可以在證明中找到[均勻分佈的期望值]（http://en.wikipedia.org/wiki/Expected_value#Univariate_discrete_random_variable.2C_finite_case）爲0，...，U是U/2 – amit 2015-04-05 15:21:28

散列表在鏈接中成功搜索的平均成本

回答

相關問題