ソートアルゴリズム正確な確率分析

Question

私は学校の割り当てのためにこの問題を見ています。私はこれをよく説明する資料をオンラインで見つけることができないので、私はこのような問題に対する一般的なアプローチを探しています。答えを出したくない場合は、私に説明をしたり、いくつかのリソースを教えてください。

それぞれがサイズmの2つのソートリストをマージしているとします。これは最悪の場合（正確には1つのリストが空になり、他のリストが一致しないため）正確に2m - 1の比較を使用します。 以下の意味でリストがランダムであると仮定します。ランダム配列（より正確にはランダム置換）でマージソートを実行していて、マージを実行しようとしています。

（a）アルゴリズムが正確に2m - 1の比較を行う確率はいくらですか？正当化する。簡略化する。

（b）アルゴリズムが正確に2m - 2の比較を行う確率はいくらですか？正当化する。簡略化する。

（c）アルゴリズムが正確に比較する確率はどれくらいですか。正当化する。簡略化する。

私はこのような確率の問題に近づくことを正確には知らない。私はアレンジメントの正確な数を列挙しようとしましたが、有効であることが証明されています。私がパートa）で得た答えはm！/（m^m）で、これは私には分かりませんが、私は第2パートを理解できません。

Answer 1

AとBをマージしている2つのリストを呼び出してみましょう。ソート順が昇順であり、一般性を失うことなく、マージされた配列に数字1,2が含まれているとしましょう、3、...、2m。そして、正確に言うと、「ランダム置換」は「すべての置換が同等に可能性がある」ことを意味します。

Aが使い尽くされたときにリストの1つ（B、say）にk要素が残っている場合、B [mk]はAのすべてよりも大きくなければなりません。Bがソートされているので、 1、2、...、2mのk個の数値。そして、（k + 1）番目の最大の数でなければ、BはAが使い果たされたときに少なくともk + 1個の要素で残されます。

どのくらいの可能性がありますか？まあ、Aには、2m-kと、最も低い2m-k-1数のサイズm-1の任意の（ソートされた）サブセットが含まれていなければなりません。それは（2m-k-1）（m-1）を選ぶことです。

一般にAとBの可能性は2mありますので、マージ後にBに残っているk要素が全体的に（2m-k-1を選択m-1）/（2m mを選択） 。

AまたはBのいずれかにk> 0の要素が残っている可能性は、その2倍です。

AまたはBにk個の要素が残っている場合、比較の合計数は2m-kになります。

• （a）2m-1比較：k = 1、確率は2（2m-2選択m-1）/（2m選択m）です。 = m /（2m-1）となる。 （2m-3選択m）=（2m-mを選択する）= m /（4m-2）であるので、確率は2である。
• （c）m比較：k = mであるので、確率は2（m-1選択m-1）/（2m m選択）= 2 /（2m mを選択）。

それとも一般的なケースを経由しないいくつかの簡単な推論：

• 2メートルと2メートル-1は、異なるアレイに表示されたときに（a）は2メートル-1の比較が行われます。 2mが1つの配列に現れるので、m /（2m - 1）の確率で他の配列に現れます。他に
• 2メートルと2M-1は、同じアレイ内に現れるときに（b）の2M-2比較が発生し、2M-2。確率（m-1）（2m-1）* m /（2m-2）= m/2（2m-1）で起こります。
• （c）m個の最大値が同じ配列内に現れた場合、m個の比較が行われます。 2つの可能性があります（AまたはBのいずれかにm + 1、...、2mの数字が含まれていなければなりません）。AとBを選ぶ方法は一般的に2mありますので、確率は2 /（2m mを選択してください）。