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 = 平均值 [P 中 p 的绝对值 (H - p)]

根据 H、P 和 E_i 和 H_i，假设 H、E 和 P 继续用作 H< sub>i、E_i 和 P_i 对于某些 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。现在您将总是有 E1 = 1 和 E2 = 1，不管 P1 和 P2 中的实际值如何。但是，你可以看到，如果 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，则无法判断您将获得 0.5 到 1.5 之间的 E 的确切值。所以你不能比 O(n) 时间更好地计算 E，其中 n 是 P 的总大小，如果你直接从它的定义公式计算你想要的数量 E，这与运行时间相同。