arrays - 从数组平均值计算数组元素平均差的有效方法

Question

有没有办法通过只“访问”每个数组元素一次来计算数组元素与数组平均值的平均距离？ (我搜索算法)

例子:

Array : [ 1 , 5 , 4 , 9 , 6 ]
Average : ( 1 + 5 + 4 + 9 + 6 ) / 5 = 5
Distance Array : [|1-5|, |5-5|, |4-5|, |9-5|, |6-5|] = [4 , 0 , 1 , 4 , 1 ]
Average Distance : ( 4 + 0 + 1 + 4 + 1 ) / 5 = 2

简单的算法需要 2 遍。

第 1 遍)读取并累加值，然后将结果除以数组长度以计算数组元素的平均值。

第 2 遍)读取值，累加每个值与先前计算的平均值的距离，然后将结果除以数组长度，以求出元素与数组平均值的平均距离。

这两个过程是相同的。它是计算一组值的平均值的经典算法。第一个将数组的元素作为输入，第二个将每个元素与数组平均值的距离作为输入。

计算平均值可以修改为不累加值，而是在我们从数组中顺序读取元素时“即时”计算平均值。

公式为:

Compute Running Average of Array's elements
-------------------------------------------
RA[i] = E[i] {for i == 1}
RA[i] = RA[i-1] - RA[i-1]/i + A[i]/i { for i > 1 }

其中 A[x] 是数组在位置 x 处的元素，RA[x] 是数组元素在位置 1 和 x 之间的平均值(移动平均值)。

我的问题是:

是否有类似的算法来计算“动态”(当我们读取数组元素时)元素与数组平均值的平均距离？

问题是，当我们读取数组的元素时，数组的最终平均值是未知的。只有运行平均值是已知的。因此计算与运行平均值的差异不会产生正确的结果。我想，如果存在这样的算法，它可能应该有“能力”以某种方式补偿每个新元素读取的到目前为止计算出的错误。

Answer 1

我不认为你能比 O(n log n) 做得更好。

假设数组已排序。那么我们可以把它分成小于平均值的元素和大于平均值的元素。 (如果某些元素等于平均值​​，那没关系。)假设前 k 个元素小于平均值。那么平均距离为

D = ((x_ave-x₁) + (x_ave-x₂) + (x_ave-x₃) + ... + (x_ave-x_k) + (x _k+1-x_ave) + (x_k+2-x_ave) + ... + (x_n-x_ave))/n

= (-x₁) + (-x₂) + (-x₃) + ... + (-x _k) + (x_k+1) + (x_k+2) + ... + (x_n) + (n-2k)x_ave)/n

= ( [高于平均值的元素总和] - [低于平均值的元素总和] + (n-2k)x_ave)/n

您可以通过从两端进行计算，同时调整(目前未知的)平均值的限制，一次性计算出这一点。 这将是 O(n)，排序是 O(n logn)(它们可能在同一操作中完成)，所以整个事情是 O(n logn)。