algorithm - 是否有一个近似值可以在一个循环中获得平均值和标准偏差

Question

我有一个包含 n 个浮点值的集合:x[n]。当我想计算平均值和标准差时，我需要对所有值进行两次循环:

首先循环对所有值求和并计算平均值:

sum = 0
for(i=0; i<n; i++)
    sum += x[i]
mean = sum/n

在第二个循环中，我计算标准偏差:

sum = 0
for(i=0; i<n; i++)
    sum += pow2(x[i] - mean)
sder = sqrt(sum/n)

我知道，如果您想要平均值和标准差的精确值，则无法降低这种复杂性。但是，如果您只是近似，是否有一种方法可以在更短的时间内计算出它们？在一个循环中受到青睐。

Answer 1

看看this section关于标准偏差的 wiki，特别是最后一个公式导致以下算法:

    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)