73792


## 概要

キューに含まれた正の数値の分散を、キュー内の数値の個数に依存しない速度のアルゴリズムを求めています  
例えば平均値の場合には、キューに含まれる数値の合計値を保持する変数を用意して、push時には加算、pop時には減算することで後は数値の個数で割るだけで計算できます  
これと同じような計算方法で分散を求めることはできますでしょうか?  
できる場合はどのようなアルゴリズムになりますでしょうか?


CC BY-SA 4.0
2021-02-04T06:15:36.043
73789
2021-02-04T06:50:26.547
19500
question
c++ アルゴリズム
キューに含まれた正の数値の分散をO(1)で計算するアルゴリズムはありますか


可能だと思います。  
数値の２乗の合計を保持する変数を用意し、数値の追加/数値の取り出し時に、数値の２乗の合計を増減しておきます。  
「二乗の平均」-「平均の二乗」が分散なので、数値の合計値と数値の個数、数値の２乗の合計値があれば分散は計算できます。


CC BY-SA 4.0
2021-02-04T06:42:59.703
73790
2021-02-04T06:42:59.703
35558
73789
answer


キュー（っつかコンテナ）とは別の変数を使ってよい、ってことですよね？

分散＝（要素の二乗の平均値）－平均の二乗

なので、要素以外に「要素の和」「要素の二乗の和」「個数」を別途覚えておけば `O(1)` で求めることができます。ソースコード書くまでもない感じ。

例： 77 80 83 の３つがあるとき、平均は 80 分散は 6  
77+80+83 = 240 (要素の１乗の和)  
77x77 + 80x80 + 83x83 = 19218 (要素の二乗の和)  
分散 = 19218/3 - (240/3)x(240/3) = 6

# もろかぶりだけどせっかく書いたし...  
# casio fx-502p でさんざん遊んだなー


CC BY-SA 4.0
2021-02-04T06:50:26.547
73792
2021-02-04T06:50:26.547
8589
73789
answer