Java8 中分组的复杂性

Complexity of grouping in Java8

我想了解下面给定语句的时间复杂度。（在Java8）

list.stream().collect(groupingBy(...));

有什么想法吗？

这个问题没有通用的答案，因为时间复杂度取决于所有操作。由于必须完全处理流，因此基础时间复杂度为 O(n)，必须乘以每个元素完成的所有操作的成本。这是假设迭代成本本身不比 O(n) 差，大多数流源都是这种情况。

所以，假设没有影响时间复杂度的中间操作，groupingBy必须为每个元素评估函数，它应该独立于其他元素，所以不影响时间复杂度（不管如何它是昂贵的，因为 O(…) 时间复杂度只告诉我们，时间 扩展 有大量的流元素）。然后，它将元素插入到地图中，这可能取决于已包含元素的数量。没有自定义 Map 供应商，地图的类型未指定，因此无法在此处进行声明。

在实践中，可以合理地假设结果将是某种哈希映射，默认情况下具有净 O(1) 查找复杂度。因此，我们的分组净时间复杂度为 O(n)。然后，我们有 下游 收集器。

默认的下游收集器是toList()，它产生一个未指定的List类型，所以再说一次，我们不能说什么成本向其中添加元素。

当前的实现产生了一个ArrayList，当超出容量时必须执行复制操作，但由于容量每次增加因子，添加 n 元素仍然存在 O(n) 的净复杂性。可以合理地假设 toList() 实施的未来变化不会使成本比我们现在的成本更糟。所以默认 groupingBy 集合的时间复杂度可能是 O(n).

如果我们将自定义 Map 收集器与自定义下游收集器一起使用，复杂性取决于平均组数与每组元素数的比率。最坏的情况是地图的查找和下游收集器的元素处理（乘以元素数量）中的最坏情况，因为我们可以有一个包含所有项目的组，或者每个项目都在其自己的组中。

但通常情况下，您能够预测特定分组操作的偏差，因此您希望计算该特定操作的时间复杂度，而不是依赖于一般所有分组操作的陈述。