異なるマシンの数値の中央値を見つけるのに最も速いアルゴリズムは何ですか？

私はmのマシンを持ち、各マシンに同じ数字のnを持っていれば、これらすべての数字の中央値、つまりm*nの数字の中で最も速いのは何ですか？見たい2つのケースがあります：それぞれnの数字がソートされているかソートされていません。異なるマシンの数値の中央値を見つけるのに最も速いアルゴリズムは何ですか？

誰かに参考文献やアイデアがありますか？ありがとうございました！

出典

2011-07-27 Qiang Li

中央値の中央値は、複数のマシンに適用できます。特に、すべての要素が同じ場合は、

マイケルの解決策は、quickselectの適応です。どちらもうまくいきますが、O（nlogn）が中央値のO（n）の中央値と比較しても、quickselectは通常より高速です。

出典

2011-07-27 00:10:34 bdares

正確にはquickselectの複雑さを意味しますか？ IIRCの平均複雑度はO（n）です。 – maxim1000

@maxim Big-oh表記はワーストケースを意味します。そして、私は誤って忘れてしまった：quickselectは実際にはO（n^2）であるが、O（n）で終わり、メジアンの中央値よりずっと小さな定数で終わる。 – bdares

@bdares： "メディアンの中央値"と言うとき、実際に複数のマシンでそれをどうやってやるのですか？あなたはいくつかの詳細を提供することはできますか？ –

異なるマシンの数値の中央値を見つけるのに最も速いアルゴリズムは何ですか？

答えて

関連する問題