まず移動平均について
時系列データの傾向を知るために使われるものに移動平均というのがあります。例えば8,9,7,9,8,9,11,8,...というデータ系列があった時、それをそのまま見るのではなく最初の5つ「8,9,7,9,8」の平均8、次の5つ「9,7,9,8,9」の平均8.4、……と平均したものを見ていったほうが上昇・下降傾向がわかりやすくなります。
このグラフでは青い線が元のデータ、赤い線が移動平均になってます。
「移動中央値」
さて、これを平均ではなく中央値でやりたい場合があると思います。中央値というのは「データを順番に並べた時真ん中に来る数」のことで、平均よりも外れ値の影響を受けにくいという性質があります。例えば「8,9,7,9,8」に「1000」が加わったら要素が一つ加わっただけなのに平均は跳ね上がりますが、中央値はほとんど変化しません。そこで「移動平均」ではなく「移動中央値」の計算を考えます。
移動平均の計算
移動平均を計算する場合毎回平均を1から計算する必要はありません。1回平均を計算すれば後は出て行く数と新しく入ってくる数による平均の変化さえ計算すれば大丈夫です。具体的には以下の様な式になります。
mean(i+1) = mean(i)+(new-old)/n
new,oldはそれぞれ新しく入ってくる数、出て行く数を表しています。
「移動中央値」の計算
奇数個の系列データの「移動中央値」
「移動中央値」の場合やや複雑になりますが同じように考えて計算していけます。まず最初に新しく入った数と出て行く数（以下new,oldと表記します）がともに元の中央値より大きい場合を考えます。この場合元の中央値の順番は変わらないので値はそのままです。new,oldが共に元の中央値より小さい場合も同様です。
ではnewが元の中央値より大きくoldが小さい場合はどうか。この場合中央値より大きい数が一つ増え中央値より小さい数が一つ減るわけですから元の中央値の順番は一つ下がります。そのため、元の中央値より大きい数の中で最小のものが新しい中央値になります。newが元の中央値より小さくoldが大きい場合は逆になります。
なお、正確には中央値と等しい数が半数以上含まれてる場合上記と関係なく新しい中央値は元の中央値と同じになります。
偶数個の系列データの「移動中央値」
上では奇数個のデータの中央値の計算の話をしましたが、偶数個だと中央値が「真ん中の2つの数の平均」になるのでさらに複雑になります。しかし基本の考え方は同じです。newとoldが真ん中の2つの数より共に大きい場合、小さい場合、一方だけ大きい場合……など場合分けして考えていけば出すことができます。
#ソースコード
以上のアルゴリズムを実装したqueueをGithubにあげているので使ってみたい方、詳しいアルゴリズムを知りたい方は見てください
https://github.com/lamrongol/QueueWithMovingStat
#計算量
最後に計算量について。newとoldが共に中央値より大きい場合など中央値に変化がない場合は定数回の比較のみなので計算量はO(1)、それ以外の場合はすべての要素を走査する必要があるのでO(n)になります。