実績解除: パソコンを叩いて直す

中央値探索の線形アルゴリズム。ピボットを選択して、それ未満のグループとそれ以上のグループに分ける。条件に従ってその2つのうちどちらかにのみ同じアルゴリズムを再帰的に適用する。ピボット選択がランダムの場合最悪O(n^2)、平均O(n)。ピボット選択を頑張れば最悪O(n)にできるが、実用上はランダムで十分速い
My Favorite Algorithm: Linear Time Median Finding https://rcoh.me/posts/linear-time-median-finding/