複数選択問題を解決するアルゴリズムを実装する必要があります。複数選択の問題は次のとおりです。
線形順序集合から抽出された n 個の要素の集合 S と、1 から n までの正の整数の集合 K = {k1, k2,...,kr} が与えられた場合、複数選択問題は、ki 番目に小さい要素を選択することです。 i のすべての値について、1 <= i <= r
Θ(n log r) の平均的なケースを解決する必要があります。必要なソリューションを実装する論文を見つけましたが、集合 S に繰り返し数がないことを前提としています。問題は、想定できないことです。それと、その論文のアルゴリズムを適応させて繰り返し数をサポートする方法がわかりません。論文はhttp://www.ccse.kfupm.edu.sa/~suwaiyel/publications/multiselection_parCom.pdf で、アルゴリズムは 2 ページ目にあります。どんなヒントでも大歓迎です！
後世のために: Ivan が参照しているアルゴリズムは、K を並べ替えてから、次のように再帰的に問題を解決することです。QuickSelect を使用して、i が ceil(r/2) である ki 番目に小さい要素 x を見つけてから、K と S の小さい方の半分と、K と S の大きい方の半分を再帰的に処理し、i について K を分割し、x について S を分割します。
縮退 (ここでは、等しい要素) の存在下で機能するアルゴリズムを見つけることは、一般的なケースの提示をより困難にし、計算を決定する役割を果たさないことが多いため、理論的研究の著者にとって優先度が高くないことがよくあります。問題の複雑さ。これは本質的に 1 次元の問題であり、ブラック ボックス ソリューションは簡単です。入力 yi の i 番目の要素を (yi, i) で置き換え、2 番目のコンポーネントを使用して比較の同点を解消します。
実際には、もっとうまくやることができます。{y : y in S, y < x} および {y : y in S, y > x} を再帰する代わりに、x に関する 3 分割アルゴリズムを使用します (たとえば、QuickSort の十分に完全なすべての処理を参照)。次に、配列 S を値ではなくインデックスで除算します。