你好 假设我有一组数字,我想快速计算出一些均匀性度量。 我知道方差是最明显的答案,但我担心朴素算法的复杂度太高 有人有什么建议吗?
最佳答案
用于计算方差的“直观”算法通常会遇到以下一种或两种情况:
- 使用两个循环(一个用于计算均值,另一个用于计算方差)
- 不是numerically stable
一个好的算法,只有一个循环并且数值稳定是由于D. Knuth (一如既往)。
n = 0
mean = 0
M2 = 0
def calculate_online_variance(x):
n = n + 1
delta = x - mean
mean = mean + delta/n
M2 = M2 + delta*(x - mean) # This expression uses the new value of mean
variance_n = M2/n
variance = M2/(n - 1) #note on the first pass with n=1 this will fail (should return Inf)
return variance
您应该为每个点调用 calculate_online_variance(x),它返回到目前为止计算的方差。
关于algorithm - 计算数字集的均匀性或差异性的快速方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4259463/