复杂度小于O(n)的平均算法

Question

是否有任何算法可以找到n复杂度小于O(n)？的平均值？

Answer 1

听起来像你真的想要一种能够根据新数据计算平均值而不必查看旧数据的算法.换句话说,你真正想要的是一个不是O(n ^ 2)的在线算法.

你可以很容易地拥有它.还有在线算法的方差和标准偏差.手段的基本公式很简单:

new_mean = old_mean + (next_val - old_mean) / n

它也很容易派生出来.假设A_n是一个n项数组,并且A_(n-1)是没有最后一个元素(a_n)的相同数组.我们想知道的价值x,使得mean(A_(n-1)) + x = mean(A_n).

x == mean(A_n) - mean(A_(n-1))

到目前为止一切顺利,但这似乎要求我们知道我们寻求的价值mean(A_n).幸运的是,我们可以发现只使用我们已有的信息.我们知道这一点mean(A_n) = sum(A_n) / n,并没有太多考虑到这一点sum(A_n) = mean(A_(n-1)) * (n - 1) + a_n

x = sum(A_n) / n - mean(A_(n-1))
x = (mean(A_(n-1)) * (n - 1) + a_n) / n - mean(A_(n-1))

现在替换xin中的原始值:

mean(A_n) - mean(A_(n-1)) = 
    (mean(A_(n-1)) * (n - 1) + a_n) / n - mean(A_(n-1))

该- mean(A_(n-1))条款取消了:

mean(A_n) = (mean(A_(n-1)) * (n - 1) + a_n) / n

剩下的就是重新分配条款:

mean(A_n) = (n * mean(A_(n-1)) - mean(A_(n-1)) + a_n) / n
mean(A_n) = mean(A_(n-1)) - mean(A_(n-1)) / n + a_n / n
mean(A_n) = mean(A_(n-1)) + a_n / n - mean(A_(n-1)) / n
mean(A_n) = mean(A_(n-1)) + (a_n - mean(A_(n-1))) / n
new_mean = old_mean + (next_val - old_mean) / n