3

n 要素の配列で、n/2 要素が繰り返され、残りが異なる場合、ラスベガス アルゴリズムを使用して、繰り返し要素を o(logn) 時間で取得できます。

この別の質問があります: このアルゴを o(logn) にするために必要な繰り返しの最小数は何ですか (k=?)、繰り返し要素が root(n) の場合の実行時間は?

私の結果は、繰り返される要素が root(n) の場合は o(logn) ではないことを示していますが、ラスベガスのアルゴリズムを使用してこの問題の緩やかな境界を見つけることができません。助けていただければ幸いです。

4

1 に答える 1

2

「ラスベガス」はアルゴリズムではありません。アルゴリズムの一種です。明らかなアルゴリズムは、要素のペアが一致するまで一様に無作為にサンプリングすることです。配列に n/2 回繰り返される要素がある場合、各ペアの成功確率は ((n/2)/n)((n/2-1)/(n-1)) = 1/4 - O (1/n) であるため、予想される実行時間は 1/(1/4 - O(1/n)) = 4 + O(1/n) = O(1) のサンプル ペアです。

これはおそらく宿題なので、さまざまな繰り返し回数に合わせて分析を調整する方法を理解する必要があります。

于 2012-04-25T15:24:07.010 に答える