質問: 概要 -- キューに含まれた正の数値の分散を、キュー内の数値の個数に依存しない速度のアルゴリズムを求めています 例えば平均値の場合には、キューに含まれる数値の合計値を保持する変数を用意して、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 でさんざん遊んだなー