1

126ページのセクション12.2：

アルゴリズムは整数0、1、2、...、n-1を順番に考慮し、適切なランダムテストによってそれぞれを選択します。整数に順番にアクセスすることで、出力がソートされることを保証します。

選択基準を理解するために、m=2およびn=5の例を考えてみましょう。確率2/5で最初の整数0を選択する必要があります。プログラムは、次のようなステートメントによってそれを実装します

if (bigrand() % 5) < 2

私の質問は、最初の整数を選択する確率が1/5ではなく2/5である理由です。5つの数字からランダムに1つの数字を選ぶ確率は1/5ではないでしょうか。

ここで本当に当惑しました。うまくいけば、誰かがここでいくつかの説明を提供することができます。

ありがとう！

4

2 に答える 2

1

順序対を選択しているとします。次に、最初の番号がペアの最初の番号である確率は1/5であり、同様に、最初の番号がペアの2番目の番号である確率は1/5です。（ペアの最初と2番目の番号の両方になることはありません。）

したがって、5つのうち2つは、順序対のどこかにある可能性があります。

ランダムな順序付けされていないペアを選択することは、順序付けられたペアを選択してから順序を忘れることと同じです。したがって、5つのうち2つが順序付けられていないペアになる可能性もあります。

于 2012-06-19T04:37:00.087 に答える
1

5つの数字からランダムに1つの数字を選ぶ確率は1/5ではないでしょうか。

これはサンプリングアルゴリズムを設計する1つの方法ですが、これは動作が異なります。各要素を順番に検討し、その要素がサンプルの一部であるかどうかを判断します。これがm=2およびn=4の決定木です（決定論的決定は抑制されています）。

                            take 0?
               _____yes_____       _____no_____
              /                                \
             /                                take 1?
          take 1?                         yes/       \no
        yes/   \no                          /         \
          /     \                        take 2?     {2,3}
       {0,1}   take 2?                 yes/   \no
             yes/   \no                  /     \
               /     \                {1,2}   {1,3}
            {0,2}   {0,3}

ルートでは、3/6の子孫の結果には0が含まれ、0は確率2/4=1/2で取得されます。0を取る場合、1/3の結果のみに1が含まれます。0を取らない場合、2/3の結果には1が含まれます。各ステップで、各決定の確率は、対応するサブツリーの結果の数に比例します。 、サイズmの均一なランダムサブセットを保証します。

于 2012-06-19T04:32:46.033 に答える