sorting - ランダム検索の最悪のケースは何ですか

Question

ランダム検索の最悪のケースは何ですか？N個の要素があるとしましょう。次に、特定の要素を1つ検索します。

答えは無限ですか？最悪の場合、要素が見つからないので、それは私には理にかなっています。

では、ベストケースは1つだけですよね？では、平均はどうですか？

Answer 1

事実上、セットの単純なランダムサンプルを実行しています。N 個の要素から n 個のサンプルが選択された後に任意の要素が選択される可能性は、次の式で与えられます。

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

Simple Random Sampleに関するウィキペディアの記事。