9

M.MitzenmacherとE.Upfalによる「ProbabilityandComputing 」を読んでいます。2つの要素の比較の確率がどのように計算されるかを理解するのに問題があります。

入力：数値のソートされたリスト（y1、y2、...、yN）。ピボット要素を（ランダムに）探しています。質問：2つの要素yiとyj（j> i）が比較される確率はどれくらいですか？

回答（本から）：シーケンスからの最初の描画でyiまたはyjのいずれかがピボットとして選択される場合、yiとyjが比較されます（yi、yi + 1、...、yj-1、yj）。したがって、確率は2 /（j-i + 1）です。

私にとっての問題は最初の主張です。たとえば、リスト全体から最初の抽選でyiをピックアップすると、yjとの比較が発生し（その逆も同様）、確率は2/nになります。

したがって、むしろ「逆」の主張は真実です-yiまたはyjの前に（yi + 1、...、yj-1）要素のいずれも選択できませんが、「プール」サイズは固定されていません（最初の描画で）確かにNですが、2番目の方が小さいです）。

誰かが著者がそのような単純化された結論をどのように思いついたのか説明してもらえますか？

編集1：いくつかの良い魂が私の投稿を磨きました、ありがとう:-)。

Edit2：リストは最初にソートされます。

4

2 に答える 2

5

クイックソートは、各要素をピボットと比較することで機能します。ピボットよりも大きい要素はピボットの右側に配置され、大きくない要素は左側に配置されます（または、降順の並べ替えが必要な場合は、その逆です）。 。

各ステップで、ピボットはシーケンスから選択されます(yi, yi+1, ..., yj)。このシーケンスにはいくつの要素がありますか？j - i + 1（タイプミスがあったと思いますが、それはできませんy - i + 1）。

したがって、このリストから2つの特定の要素のいずれかを選択する確率は明らかに2 / (j - i + 1)です。

私にとっての問題は最初の主張です。たとえば、リスト全体から最初の抽選でyiをピックアップすると、yjとの比較が発生し（その逆も同様）、確率は2/nになります。

ピッキングすると、他の要素とのみyi比較されます。j - iどこnから来たの？yiリストはからにのみ移動することを忘れないでくださいyj！

編集：

もう一度質問を読んでみると、少しあいまいだと思います。再帰の最初のステップで2つの要素を比較する確率は2 / n、あなたが言うように、とはとでiあるためjです。未知の再帰ステップで2つの要素を比較する確率は、上記で説明したものです。1n

于 2010-05-01T16:48:47.833 に答える
4

著者の答えは正しいですが、彼らがどのようにして簡単かつ迅速に結論に達したのかはまだわかりません。

を L=j-i+1 とします。j と i の実際の値はここでは関係ありません。重要なのは L です。また、サイズ N の順序付けられた数列から yi 要素と yj 要素を比較する確率を P(N,L) で表すことにします。

事実:

  • P(N,2) = 1
  • P(N,L) = 2/N+1/N * ( P(N-1,L)+P(N-2,L)+P(N-3,L)+...+P(L 、L) )

この合計は見栄えが悪いですが、2 つのテストの結果、P(N,L) はおそらく 2/L に等しいことがわかりました。それをチェックしよう：

  • P(N,L=2) = 1 = 2/2 = 2/L
  • P(N,L) = 2/L としましょう
  • P(N+1,L) = 2/(N+1) + 1/(N+1) * ( P(N,L) + ... P(L,L) ) = 2/(N+1 ) + (N-L+1)*1/(N+1)*2/L = 2/L

L=j-i+1 なので、2/(j-i+1) となります。

于 2010-05-15T09:23:41.010 に答える