- 125 名前：デフォルトの名無しさん mailto:sage [2012/01/06(金) 17:33:36.32 ]
- Wikipediaにはソートが必要だからO(nlogn)かかるって書いてあるね。
中央値 - Wikipedia ja.wikipedia.org/wiki/%E4%B8%AD%E5%A4%AE%E5%80%A4
以下、データ数nが奇数だという前提の下でソートから省ける処理がないか考えてみた。
n-1個のソートされたデータに対してn番目のデータを追加するとき、
中央値を得るだけが目的ならば暫定中央値候補2つとの比較だけすればいい。
時間を戻して、同様にn-2個のソートされたデータに対してn-1番目,n番目のデータを
追加することを考えると、n-1番目のデータは暫定中央値候補3つとの比較だけでよい。
nを101だとすると、52番目までは普通にソート。
53番目は50回比較。
…
100番目は3回比較。
101番目は2回比較。
…ダメか。(n+3)/2個のデータのソートは必要なので、
係数は変化するかもしれんが計算量がO(nlogn)であることからは逃れられん
っていうかむしろO(n^2)の部分を含んでるしorz。
高速化自体が目的なら、データ数次第では計算量のみで必ずしも優劣が決まるというわけではないけど。
|
 |
