algorithm - 关于队列和标准差

Question

我不确定这个问题应该放在哪里，因为它听起来也很数学化，但由于编程的性质，我仍然决定把它放在这里。

我有一个大小不变的队列，它不断地向后加载数据并从前面弹出数据(保持大小不变​​)，并且我想要队列中的标准偏差 (sigma)。我知道 for 循环实现很容易，但是当大小变大时，时间会变得非常糟糕。有没有更好的实现方式？

Answer 1

由于公式 std dev = sqrt(E(x^2)-E(x)^2) (proof on wikipedia)，您可以使用有效方法计算均值和标准差.

换句话说，跟踪值的平方和(例如在变量 sum_of_squares 中)，并跟踪值的总和(例如在变量 sum_of_values 中)。在这两种情况下，您都可以通过添加一个值并删除旧值来更新 O(1) 中的变量。

那么标准偏差可以计算为:

mean = sum_of_values/n
std_dev = sqrt( sum_of_squares/n - mean*mean )