什麼是隨機搜索的最壞情況

Question

隨機搜索的最壞情況是什麼？假設我有N個元素，然後搜索一個特定元素。

答案是無限的嗎？這對我來說很有意義，因爲在最壞的情況下我從未發現過這個元素。

那麼最好的情況只是一個權利？那麼平均值呢？

Answer 1

您實際上是在做一組簡單的隨機樣本。

P(n) = 1 - (1 - 1/N)^n 

維基百科文章上Simple Random Sample：任何給定的元件之後，從N個元素中選擇n個樣本中選擇的機會由下式給出。