CLRSの質問です。質問は、CLRS ブックの第 3 版: 5-2-b からのものです。
ランダム検索は、要素をランダムに選択し、それを検索された要素と比較する必要があるアルゴリズムです。等しい場合は、停止する必要があります。ここで、A[i]=x (x は配列内の検索要素) となるインデックス i を持つ要素が 1 つだけあるとします。x を見つける前に選択しなければならない A のインデックスの予想数は? また、x に等しいインデックス値が複数ある場合、どのようにしてインデックスの期待数を見つけることができますか?
確率変数 X = ターゲット要素を選択するまでの反復回数を定義できます。「反復」を「試行」と呼び、「ターゲット要素の選択」を「成功」と呼ぶように用語を一般化すると、X = 成功までの試行回数になります。
この確率変数には、よく知られた分布があります。これは、成功確率パラメーター p が与えられた幾何分布です。幾何分布の期待値は E(X) = 1/p です。
幾何分布を問題に適用するには、成功確率 p を決定する必要があります。ターゲット値を含むインデックスが 1 つだけの場合、p = 1/n で、n は検索されるコレクションのサイズです。したがって、この場合、E(X) = n です。
任意の数のインデックスがターゲット値にマップされる一般的なケースでは、p = m / n で、m はターゲット値にマップされるインデックスの数です。したがって、この場合、E(X) = n / m.
要素 x が見つかるまでに k 回の失敗があると仮定します。したがって、Pr{k 失敗}=k/(n-1) です。ここで、E(X)=k=1 から n の Pr{k 失敗} の合計です。したがって、E(X)=n(n+1)/2(n-1) です。