平均値・中央値
平均値は、総和を個数で割ったもの。
中央値は、要素をソートしたときちょうど真ん中の値。
平均値の定義
総和を個数で割ると平均値になる。
$ \frac{1}{N} \sum_i A_i
差の二乗和
平均は差の二乗和を最小化する。
$ \argmin_x \sum_i (A_i - x)^2
平均が$ x以上か判定する
$ \sum_i (A_i - x) \ge 0なら$ A_iの平均は$ x以上。
中央値の定義
定義にはすこし揺れがある。
個数が奇数のとき: 真ん中の値
個数が偶数のとき: 真ん中の値が二つあるとき
二つの平均: よく使われる定義
小さい方、もしくは大きい方: 競プロでよくある。二分探索と相性がいい
中央値が$ x以上か判定する
$ x以下の値が$ \frac{N}{2}個くらいあれば$ xが中央値
中央の小さい方を中央値とするときの判定方法
$ B_i = \begin{cases} 1 & A_i \ge x \\ -1 & A_i < x \end{cases}とする。
$ \sum_i B_i > 0なら中央値は$ x以上。
中央の大きい方を中央値とするときの判定方法
$ B_i = \begin{cases} 1 & A_i \ge x \\ -1 & A_i < x \end{cases}とする。
$ \sum_i B_i \ge 0なら中央値は$ x以上。
差の絶対値の和
中央値は差の絶対値の和を最小化する。ここでいう中央値は、小さい方の中央値以上で大きい方の中央値以下ならなんでもいい。
$ \argmin_x \sum_i |A_i - x|
関連問題
参考