概要
キューに含まれた正の数値の分散を、キュー内の数値の個数に依存しない速度のアルゴリズムを求めています
例えば平均値の場合には、キューに含まれる数値の合計値を保持する変数を用意して、push時には加算、pop時には減算することで後は数値の個数で割るだけで計算できます
これと同じような計算方法で分散を求めることはできますでしょうか?
できる場合はどのようなアルゴリズムになりますでしょうか?
スタック・オーバーフローはプログラマーとプログラミングに熱心な人のためのQ&Aサイトです。すぐ登録できます。
登録してこのコミュニティに参加するキューに含まれた正の数値の分散を、キュー内の数値の個数に依存しない速度のアルゴリズムを求めています
例えば平均値の場合には、キューに含まれる数値の合計値を保持する変数を用意して、push時には加算、pop時には減算することで後は数値の個数で割るだけで計算できます
これと同じような計算方法で分散を求めることはできますでしょうか?
できる場合はどのようなアルゴリズムになりますでしょうか?
キュー(っつかコンテナ)とは別の変数を使ってよい、ってことですよね?
分散=(要素の二乗の平均値)-平均の二乗
なので、要素以外に「要素の和」「要素の二乗の和」「個数」を別途覚えておけば O(1)
で求めることができます。ソースコード書くまでもない感じ。
例: 77 80 83 の3つがあるとき、平均は 80 分散は 6
77+80+83 = 240 (要素の1乗の和)
77x77 + 80x80 + 83x83 = 19218 (要素の二乗の和)
分散 = 19218/3 - (240/3)x(240/3) = 6
# もろかぶりだけどせっかく書いたし...
# casio fx-502p でさんざん遊んだなー
可能だと思います。
数値の2乗の合計を保持する変数を用意し、数値の追加/数値の取り出し時に、数値の2乗の合計を増減しておきます。
「二乗の平均」-「平均の二乗」が分散なので、数値の合計値と数値の個数、数値の2乗の合計値があれば分散は計算できます。