algorithm - 中央値の中央値は真の中央値ではありません。正しい？

Question

個人的には、中央値の中央値は本当の中央値ではないと思います。正しい？
したがって、上記のステートメントが当てはまる場合、中央値の中央値をピボットとして使用して配列を分割し、K 番目の最小要素の時間計算量の最悪のケースが O(n) になるのはなぜですか? 「n」は要素の数です。

Answer 1

中央値の中央値は、実際の中央値とは限りません。

これは最適化として使用され、Quicksort や Quickselect などのアルゴリズムで配列のパーティションのピボットを計算して、最悪の場合の複雑さO(n^2)が回避されるようにします。

それについてのウィキペディアの記事では、次のように述べています。

このアプローチは非常によく最適化されますが、代わりにランダム ピボットを選択することにより、実際には通常よりも優れたパフォーマンスを発揮します。これは、選択に平均線形時間、並べ替えに平均線形時間を使用し、ピボットの計算のオーバーヘッドを回避します。