私は浮動小数点値の集まりがx[n]です。私はmeanvalueと標準偏差を計算したい場合は、私はすべての値にわたって2つのループを繰り返し処理する必要があります：私は計算する第二のループでは一つのループに平均値と標準偏差を得る近似はありますか
sum = 0
for(i=0; i<n; i++)
sum += x[i]
mean = sum/n
：すべての値を合計し、meanvalueを計算する
最初のループを標準偏差：
sum = 0
for(i=0; i<n; i++)
sum += pow2(x[i] - mean)
sder = sqrt(sum/n)
平均値と標準偏差の正確な値を求める場合は、この複雑さを減らすことはできません。しかし、おおよそ近似すれば、より少ない時間でそれらを計算する方法はありますか？ 1つのループで好意。
は、標準偏差のウィキのthis sectionを見てください、特に最後の式は、以下のアルゴリズムにつながる：
sum = 0;
sumsqrd = 0;
for(i = 0; i < n; i++)
sum += x[i]
sumsqrd += x[i] * x[i]
mean = sum/n
stddev = sqrt(sumsqrd/n - mean * mean)
ああ、私は数学でもっと注意を払わなければなりませんでした。私はそれが簡単だろうとは思わなかった。 – RomCoo
このアルゴリズムの数値的安定性は、平均を最初に計算し、次に平均からの二乗平均平方根偏差を計算することよりも悪いことに注意する価値があります。たとえば、IEEE 754倍では、[1e8 + 1,1e8-1]の標準偏差が0になります。とにかく近似を受け入れるつもりなら、それはおそらく問題ありませんが、このアルゴリズムには欠点がないと考えるのは間違いでしょう。 – user2357112
ここに1つのパスで計算を行い、バージョンだ、と計算がより安定しています：
mean = 0.0
sum_sqrs = 0.0
n = 0
loop do
x = get_x()
break if x == nil
delta = x - mean
n += 1
mean += delta/n
sum_sqrs += delta * (x - mean)
end
sample_var = sum_sqrs/(n - 1)
これはStandard deviationのためのウィキペディアのページのRapid calculation methodsセクションの下半分で見つかった式に基づいています。
あなたが持っているものはO（n）です。あなたは1回のパスでそれをしたいと思っていますか？ – SirGuy
はい、私はそれを意味します。私は質問を編集するつもりです – RomCoo
O（2n）はO（n）です。あなたが定数の改善を望むときにbig-O表記法を使用しているなら、おそらくこれを間違った方法と考えているでしょう。 – user2357112