メディアンの中央値

Question

私は線形時間O（n）でサイズnの配列のk番目に小さい（または最大の）要素を見つけるために順序統計量を読みました。

メジアンの中央値を見つけるために必要なステップが1つあります。

1. アレイを[n/5]個の部分に分割します。各パーツには5つの要素があります。
2. 各部分の中央値を求めます。
3. 手順1と2を最後の番号まで繰り返します。 （すなわち再帰的）

T（n/5）+ O（n） T（n）= O（n）を得ることができる。

しかし、最終的に得られる数はメジアンの中央値ではなく、メジアンのメジアンの中央値の中央値です。

125個の要素を持つ配列を考えてください。

まず、25個の部分に分割され、25個の中央値が見つかります。 次に、これらの25の数値を5つの部分に分け、5つの中央値を見つけます。 最後に、中央値の中央値である数値を取得します。 （メディアンの中央値ではない）

私が気にしている理由は、メジアンの中央値よりも小さい（または大きい）[3/4] * n要素がほとんどであることが分かります。しかし、中央値の中央値ではなく中央値の中央値の中央値であればどうでしょうか？さらに悪い場合、ピボットよりも小さい（または大きい）要素が少なくなければなりません。ピボットが配列の境界に近いことを意味します。

我々は非常に大きな配列を持ち、メジアンの中央値の中央値は中央値の中央値であることがわかりました。最悪の場合、我々が見つけたピボットは依然として限界に非常に近づくことができ、この場合の時間の複雑さは何ですか？

私は125要素のデータセットを作成しました。結果は9ですか？

0.8 0.9 1 inf inf 
1.8 1.9 2 inf inf 
6.8 6.9 7 inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

2.8 2.9 3 inf inf 
3.8 3.9 4 inf inf 
7.8 7.9 8 inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

4.8 4.9 5 inf inf 
5.8 5.9 6 inf inf 
8.8 8.9 9 inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

ここで、infは数値が十分大きいことを示します。

Answer 1

[median of] * = Mのメジアンの中央値の中央値を示しましょう。

まず、メジアンアルゴリズムの中央値（良いピボットを選択する）は再帰的ではないと思います。アルゴリズムは次のようになります：

1. スプリット5
2. のグループ内の要素は、中央値の中央値を検索し、ピボットとしてそれを使用する各グループ
3. の中央値を検索します。

中央値の中央値は、3n/10要素より小さく、3n/4ではなく、3n/10要素より大きくなります。メジアンを選択した後にn/5の数字があります。中央値の中央値は、それらの半分よりも大きい/小さい。これはn/10である。それらの数字のそれぞれは中央値そのものなので、2つの数字より大きい/小さいので、別の2n/10の数字を与えます。合計で、n/10 + 2n/10 = 3n/10の数値が得られます。

1, 2, 7, inf, inf 
3, 4, 8, inf, inf 
5, 6, 9, inf, inf, 
inf, inf, inf, inf, inf, 
inf, inf, inf, inf, inf. 

だから、中央値の中央値は、実際に9

次のようになります。あなたの例のデータセットで5つの者のグループを収集し、その中央値を計算した後、我々は次のシーケンスを持つことになり、あなたの2番目の質問に対処するために

ご提案* [中央値の]アルゴリズムの実行時間は次のようになります。

T(n) = O(n * log(n)) 

今の私たちはより少ない/大きいを持っているどのように多くの数字を分析してみましょうM。

• 深1： 我々は、以下の群有するN/5の要素のすべての中央値を
• 深2：N/25の要素全てメジアン
• ...
• 深I：N /（5^I）の要素のすべてのメジアン

各グループように、前の深さの2つの要素よりも小さい/大きい、前深さ、の2つの要素よりも小さい/大きい：

合計で計算すると、Mが（n *（2^k）+ k * n）/（（2^k）*（5^k））より大きい/小さいことがわかります。深度= 1の場合、中央値は3n/10です。

5^k個の*（K + 2^k個）/（5^K * 2^k個：今、あなたの深さは[log_5（N）]、すなわち、n = 5^kの、我々取得であると仮定し

） - > 1