sorting - 随机搜索的最坏情况是什么

Question

随机搜索的最坏情况是什么？假设我有 N 个元素，然后搜索一个特定元素。

答案是无限的吗？这对我来说很有意义，因为我从来没有在最坏的情况下找到元素。

那么最好的情况只是1对吗？那么平均呢？

Answer 1

您实际上是在做一个简单的随机样本。在从 N 个元素中选择 n 个样本后，选择任何给定元素的机会由下式给出：

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

维基百科关于简单随机样本的文章。