ランダム化されたクイックソート：低いパーティションサイズの確率1

Question

ランダム化されたクイックソートでは、サイズ1の低いパーティションを取得する確率は2/nになります。 私はこれについて私の頭を掴みようとしていますが、どのように把握できませんでした。

私が得る式は次のとおりです。

X = low partition size 
P(X=1) = 1/n + 1/n 
[Summation(i = 2 to n) 
{ 
    (n-i Comb i-1)/(n-1 Comb i-1) 
} 
] 

これはに削減：

= 1/n + 1/n[(n-2)/(n-1) + (n-3)(n-4)/(n-1)(n-2) + ...] 

さらに移動するにはどのように？ 私のアプローチと表現は正しいですか？サイズ1の低いパーティションを取得する

Answer 1

確率は2/N

であることが判明それはあなたが「サイズ1の低いパーティション」によって何を意味するかに依存します。あなたはworst case for quicksortを見れば：

ピボットは一様な選択、選択の確率で

リスト内の最小または最大の要素であることを起こる場合、ほとんどのアンバランスなパーティションが...起こります最も低い要素は1/nであり、最も高い要素を選択する可能性があります。これらは互いに独立した事象（要素がすべて同じでない場合）であるため、合計確率は合計である2/nです。

パーティションの左側が1である確率は、その半分です。1/n。