ランダム化された選択

Question

ランダム化選択アルゴリズムは次のとおりです。

入力：$ n $の配列$ a $（個別、単純さの場合）数と$ k in [n] $

出力：$ a $の「ランク$ k $要素」（すなわち、$ a $がソートされた場合の位置$ k $にあります）

方法：

• $ a $に1つの要素がある場合は、返品してください
• 要素$ p $（「ピボット」）をランダムに均一に選択します
• セットを計算します$ l = {a in：a <p } $および$ r = {a in：a> p } $
• $ | l |の場合 ge k $、$ l $のランク$ k $要素を返します。
• それ以外の場合は、ランク$ k - | l | $ $ r $を返します

私は次の質問をされました：

$ k = n/2 $であるため、中央値を探していると仮定し、$ alpha in（1/2,1）$を定数とします。最初の再帰呼び出しで、中央値を含むセットが最大$ alpha n $でサイズを持っている確率はどのくらいですか？

答えは$ 2 alpha -1 $であり、「選択されたピボットは$ 1 - alpha $と$ alpha $の間にあるはずです」と正当化されたと言われました。

なんで？ $ alpha in（0.5、1）$として、ピボットが元の要素の半分以上が大きいか小さいので、どの要素が選択されますか。分割されたサブアレイの要素は常にピボットよりも少ないため、中央値は常に大きなサブアレイにあります。

ピボットが元の配列の前半（それらの半分未満）にある場合、中央値が見つかった後、アレイの中央位置にある必要があり、そして、中央値は確実に2番目の半分になります。上記のように、ピボットの前のすべてが小さくなります。

ピボットが元の配列の後半（要素の半分以上）にある場合、中央値は確実に最初の半分になります。

例：

3 4 5 8 7 9 2 1 6 10

中央値は5です。

選ばれたピボットは2であると想定されています。したがって、最初の反復の後、それは次のようになります。

1 2 ....大きな部分....

それだけ 1 と 2 最初の反復後に交換されます。ナンバー5（中央値）はまだ最初のハーフ（ピボット2に蓄積）にあります。ポイントは、中央値が常により大きな半分にあるということです。どうして小さなサブアレイにとどまるチャンスがあるのでしょうか？

Answer 1

配列に$ n $要素があるとします。ご存知のように、中央値は常に最初のパーティションの後、常に大きな部分にあります。大きい部分のサイズは、少なくとも$（1- alpha）n $のサイズがある場合、最大$ alpha n $を持っています。これは、最小または最大の$（1- alpha）n $要素の1つではないピボットを選ぶときに起こります。 $ alpha> 1/2 $であるため、これらはばらばらセットであることがわかっているため、悪いピボットの1つを打つ確率は$ 2-2 alpha $、$ 1- 2 + 2 alpha = 2 alpha -1です。 $。