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

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

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

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

2013-03-01 Arch1tect

你真的是指隨機搜索？ http://en.wikipedia.org/wiki/Random_search或者你的意思是對隨機排列的數組進行線性搜索，或者你是指隨機選擇索引到數組中（並允許重複索引）？從上下文我會假設後者，但你可能想澄清。 – 2013-05-29 17:22:34

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

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

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

2013-03-01 04:55:45 Brian

最糟糕的情況是怎麼回事？爲什麼這被接受:-P – 2013-05-29 17:30:37

回答