奇数要素の配列から中央値を見つけるアルゴリズム

Question

奇数長の配列の中央値を見つけるアルゴリズムが存在するかどうかを知りたいと思います。明らかに、配列をソートして中間を取ることができますが、理想的には中央値に興味があるだけで、アルゴリズムの時間的複雑さの面で利益を得ることができます。

このようなアルゴリズムが存在しない場合、そのようなアルゴリズムを開発する方法に関する提案はすばらしいものです。

おかげ

Answer 1

これはselection algorithmによって解決され、かつO(n)時間で行うことができます。 Quickselect、またはその洗練されたintroselectは、一般的な方法です。

quickselectの簡単な概要はquicksortを実行することですが、各ステップで両方の半分をソートするのではなく、探している要素を含む半分だけをソートします。各パーティション内にあります。

例えば、C++は実際に標準ライブラリ関数としてnth_elementを持っています。

Answer 2

Selection algorithmを使用すると、配列のk番目の最小要素を見つけることができます.kは配列のサイズの半分です。

非構造化データの場合は、O(n)です。

しかし、理論上の複雑さはすべてではありません。

また、this questionも読んでください。

Answer 3

はい、アルゴリズムが存在します。あなたが話している問題は、kが配列の長さの半分+ 1の値であるk番目に大きい要素を見つけることです。ここにO（n）時間に行う方法へのリンク、Median of mediansがあります。