ソートされていないリストでおおよその中央値を見つけたい、2つのアルゴリズムを知っている
アルゴリズム 1 - クイックセレクト
アルゴリズム 2 - 中央値の中央値
私のプロジェクトでは、最悪の場合 O(n^2) かかるため、クイック選択を使用できません。中央値の中央値について聞いたことがありますが、私の同僚は、一定の係数を持つ O(n) が必要であることを示唆しています。中央値の中央値に関連付けられている定数要因は何ですか?また、中央値の中央値が9要素の疑似中央値を使用しないのはなぜですか?
または、線形時間 O(n) でおおよその中央値を見つけるための他のアルゴリズムですか?