algorithm - 简化递归均值计算

Question

如果我们有

E _{i = 均值 [在 P i}中 p 的绝对值 (H _i - p) ]

H = 平均值 [H ₀ , H ₁ , ... H _i , ... H _n ]

P = concat [P ₀ , P ₁ , ... P _i , ... P _n ]

那么是否存在一种更有效的计算方式

E = mean [abs (H - p) for p in P]

在 H、P 和 E _i s 和 H _i s 方面，假设 H、E 和 P在更高的递归级别上继续用作某些 i 的 H _i、 E _i和 P _{i ？}

如果我们在每个阶段将 P _i的长度存储为 L _{i ，那么我们可以让}

L = 总和 [L ₀ , L ₁ , ... L _i , ... L _n ]

允许我们执行更简单的计算

E = sum ([abs (H - p) for p in P] / L)

但是 abs 函数的使用似乎严重限制了我们可以用来简化分子的代数操作的种类。

Answer 1

不。想象你只有两组，一组有 H1 = 1，另一组有 H2 = 2。想象 P1 中的每个 p 要么是 0 要么是 2，而 P2 中的每个 p 要么是 1 要么是 3。现在无论 P1 和 P2 中的实际值如何，您将始终拥有 E1 = 1 和 E2 = 1。但是，您可以看到，如果 P1 中的所有 p 都是 2，并且 P2 中的所有 p 都是 1，那么 E 将被最小化（特别是 0.5），因为 H = 1.5。或者 P1 中的所有 p 都可以为 0，而 P2 中的所有 p 都可以为 3，在这种情况下，E 将被最大化。（特别是 1.5）。根据 p 的分布，您可以获得介于 0.5 和 1.5 之间的 E 的任何答案。如果您实际上不去查看所有单个 p，则无法确定 E 在 0.5 和 1.5 之间的确切值。所以你不能比 O(n) 时间更好地计算 E，其中 n 是 P 的总大小，