問題タブ [median-of-medians]

中央値の中央値アルゴリズムとは別に、最悪の場合のO（n）時間でk選択を行う他の方法はありますか？中央値の中央値を実装することは理にかなっていますか。つまり、パフォーマンス上の利点は実用的な目的には十分ですか？

私はウェブを検索し、中央値の中央値アルゴリズムのwikiページにアクセスしました。しかし、私の質問に対する明確な声明を見つけることができないようです：

整数の非常に大きなリスト（サイズがTB）があり、このリストの中央値を分散して見つけたい場合は、リストをさまざまなサイズのサブリストに分割します（または等しいことは実際には重要ではありません）。次に、それらの小さいサブリストの中央値の計算に進み、次にそれらの中央値の中央値を計算して、元の大きいリストの中央値にしますか？

さらに、このステートメントは、k番目の統計のいずれにも正しいですか？この分野の研究等へのリンクに興味があります。

次の例で「中央値の中央値」アルゴリズムを理解したい:

それぞれ 5 つの要素を持つ 9 つのグループに分割された 45 の異なる数があります。

1. 最初のステップは、すべてのグループを並べ替えることです (この場合、それらは既に並べ替えられています)

2. 2 番目のステップでは、中央値の「真の」中央値 ( ) を再帰的に見つけます。50 45 40 35 30 25 20 15 10つまり、セットは 2 つのグループに分割されます。

   これらの 2 つのグループを並べ替える

   /li>

中央値は 40 と 15 です (数値が偶数の場合、左中央値を取ります)。したがって、返される値は 15 ですが、中央値の「真の」中央値 ( 50 45 40 35 30 25 20 15 10) は 30 です。ウィキペディアで言及されている 45 の %

そしてT(n) <= T(n/5) + T(7n/10) + O(n)失敗します。

ちなみに、ウィキペディアの例では、再帰の結果は 36 になります。ただし、真の中央値は 47 です。

したがって、場合によっては、この再帰が真の中央値の中央値を返さない可能性があると思います。私の間違いがどこにあるかを理解したいです。

このアルゴリズムを本から直接コピーしていますが、「ERROR HERE !!!!」で ArrayIndexOutOfBoundsException が発生し続けます。一部... T[i] = ...

それは私を狂わせており、これを成し遂げる必要があります...誰かがこれを修正する方法を提案できますか? また、本からアルゴリズムを翻訳したために発生する可能性のある他のエラーについてもコメントしました...

仕事に向かいます。しばらくしてから戻ってきてください。助けていただければ幸いです..

配列を5つのグループに分割して中央値を実装するための擬似コードを次に示します。

2つの質問があります：

1. 最初のものはパーティションコードに関連しています。ここでは配列とその境界のみが示され、ピボット要素は示されていません。このパーティションコードはどのように表示されますか？ピボットインデックスとピボット要素を次のように選択する必要があります。

   またはそれはランダムな選択でなければなりませんか？

2. 選択した中央値を出力する方法は？

一般的に言語は重要ではありませんが、例がC++で表示されると便利です。

私は最近、最初に重複のケースなしで、k 番目に最小の要素アルゴリズムを分析した後、プログラムを作成しました。

jただし、正確に重複がある場合に、配列の中央値などを見つけるために、予想される漸近的なランタイムを分析したいと思います。jそのようなコードを変更していないため、重複のためにパフォーマンスが少し低下します。

どうやって始めればいいのかわからない？誰かが私にそのような再発関係を指摘できますか?

n は入力配列のサイズです。

しかし、関連する重複キーをどのように処理するかは非常に不明です。

ありがとう

このMedian of mediansアプローチは、型分割アルゴリズムで非常に人気がありquicksort、配列を均一に分割するなど、かなり優れたピボットを生成します。その論理はウィキペディアで次のように示されています。

選択されたピボットは、中央値のリストにある要素の半分未満と半分より大きい両方です。これは、各半分で約n / 10要素（1/2 *（n / 5））です。これらの各要素は中央値5であり、他の2つの要素より少なく、ブロックの外側にある他の2つの要素より大きくなります。したがって、ピボットは、ブロックの外側の3（n / 10）要素未満であり、ブロックの外側の別の3（n / 10）要素よりも大きくなります。したがって、選択された中央値は、要素を30％/ 70％から70％/ 30％の間のどこかに分割します。これにより、アルゴリズムの最悪の場合の線形動作が保証されます。

誰かが私のためにそれを少し明快に説明できますか？論理を理解するのが難しいと感じています。

ardendertatmedian-of-mediansのアルゴリズムを使用して、配列内でk番目に高い要素を見つける方法に関する記事を読んでいました。複雑さを説明する部分では、作成者は1つの要素、つまり各パーティションのを再帰的に見つけるコストを割り引いたようです。確かに、最初のピボットですべてのサブアレイを分割することはできませんよね？それで、これは複雑さを増しませんか？median-of-medians

私はおそらく信じられないほど愚かなことをしているのですが、このリダクションを機能させることができないようです (おそらくこれを行うライブラリが既にありますが、これは自己学習用ですので、ご容赦ください)。以下にコーディングした中央値アプローチの中央値を使用して、整数エントリの配列の中央値を見つけようとしています。

このカーネル関数を次のように呼び出します。

次に、d_med の値を med にコピーし、その値を出力します。残念ながら、この値は入力に関係なく常に 0 です。私は何を間違っていますか？

編集:言及するのを忘れていましたが、swapGpu(a, b) は次のように定義されています。

Edit2: 以下に示すように、ここにコード全体があります。

私は現在、中央値 alg の中央値を研究しています。

ウィキから勉強した後、質問があります: 入力サイズが 5 で割り切れない場合はどうなりますか? 中央値アルゴリズムの中央値を使用して中央値を見つける方法は?