naoya_t@hatenablog

いわゆるチラシノウラであります

中央値の中央値 (median of medians)

Algorithms

ABC100の解説で触れられていた「中央値の中央値 (median of medians)」のことを調べたメモ。
〜
厳密なmedian値でなくていいのでそれっぽい値をO(n)で求める方法。少なくとも上下に\frac{3}{10}n個ずつ、それより小さい（or 大きい）値が存在することが示せる。

真のmedianの近似として、適当なpivotの選択に使える。
（配列の中でk番目に小さい値を選ぶときに使える。k=n/2とすれば当然真のmedianも求まる。quicksortのpivotにも使えるけど乱数でやったほうが速いとか。最悪計算量は減らせるけど）

原理は割と簡単

・[Round 1] 5個ずつのブロックに分けて、それぞれのmedianを代表として選ぶ
・[Round 2] 代表（n/5個）のmedianを1個選ぶ（この値をMとしよう）
n/5個の代表の半数（即ちn/10個）はM以下の値である。そして、それらを代表として選出したブロックにはその代表より小さい値が2つずつ存在するので、少なくとも全体の(1+2)\frac{n}{10}=\frac{3}{10}n個の値はM以下である。上についても同様に、少なくとも全体の\frac{3}{10}n個の値はM以上である。

配列の中でk番目に小さい値を選ぶ方法 (quickselect)

quickselectは、quicksortと同様に適当なpivotを選んで、partitionして、k番目に小さいの要素があるはずの区間に潜って（ないほうの区間については放置しつつ）k番目に小さい要素を得るアルゴリズムである。
（詳しくは作図の得意なフレンズのブログの図解を見ていただこう）

ここでmedian of mediansを利用することでmedianに近いpivotを高速に選び、最悪計算量）を減らすことができる。

  • 配列からmedian of mediansでpivotを選ぶ。(O(n))
  • そのpivotでpartitionし、pivotの位置を得る。(O(n))
    • その位置より前にはpivot以下の値しかなく、後ろにはpivot以上の値しかない
  • （二分探索の要領で）pivotの位置がkより大きければ前側の区間、kより小さければ後ろ側の区間に絞り込んで引き続き調べる。(合計するとO(n))
    • pivotの位置がkジャストならそのpivotの値が求める値

実装

Wikipediaに書かれているアルゴリズムはそのままだと相互参照の終了条件がなくて止まらない

この辺りを見ながら実装。

partitionの所はquicksortの時の要領で。（苦手なので上記実装ではstd::partition()でお茶を濁しているがそれくらい自分でさくっと書きたいところ）

実験

0〜N-1の値をシャッフルした配列で適当なkについてk番目の値を選ばせてみた

N=100: 0.008msec
N=1000: 0.064msec
N=10000: 0.579msec
N=100000: 5.781msec
N=1000000: 57.816msec

線形っぽい