java - 平均两个以上浮点数组的最快方法是什么？

Question

我有大约 200 个此类列表，(index , float)我想计算它们之间的平均值，我知道复杂度时间的方法O(first Array size + ... + last Array size)是否有任何解决方案来计算具有更好复杂度时间的平均值？

Answer 1

没有可能的方法来计算时间复杂度小于O(n): 的 N 个独立项目的平均值，因为您必须至少访问每个项目一次才能计算总数。

如果你想击败 O(n) 复杂度，那么你需要做一些特别的事情，例如：

• 对子列表使用预先计算的总和
• 利用数据中的已知依赖性（例如某些元素相等）

当然，复杂性并不总是直接等同于速度。如果您想快速完成，那么还有很多其他技术（例如使用并发或并行）。但就复杂性而言，它们仍然是 O(n)。

Answer 2

你接近它divide and conquer。为此，您可以使用ExecutorService

Answer 3

根据您在列表/数组中的读取方式，您可以将浮点数加在一起，同时将它们读入内存。将值除以数组的大小很便宜。因此，您不需要两次处理这些值。

如果您使用Collection类来存储值，则可以扩展例如ArrayList并覆盖该add()方法以更新sum字段并提供getMean()方法。

Answer 4

不，没有比在计算中包含每个元素（即O(first Array size + ... + last Array size)）更好的方法了，至少对于上述问题来说不是。如果列表具有某些特殊属性，或者您想在添加、删除或更改元素或列表后反复重新计算平均值，那就另当别论了。

非正式证明：

假设您设法通过跳过一个元素来计算平均值。从逻辑上讲，您可以通过将跳过的元素更改为任何其他值来达到相同的平均值（因为我们跳过了它，所以它的值无关紧要）。但是，在这种情况下，平均值应该不同。因此，您必须使用计算中的每个元素。