java - Java8中分组的复杂性

Question

我想了解下面给定语句的时间复杂度。(在 Java 8 中)

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

任何的想法？

Answer 1

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

因此，假设没有影响时间复杂度的中间操作，groupingBy必须评估每个元素的函数，它应该独立于其他元素，所以不会影响时间复杂度(不管它有多昂贵，因为 O(…) 时间复杂度只告诉我们，时间复杂度如何随着大量流元素)。然后，它会将元素插入到映射中，这可能取决于已包含元素的数量。没有定制Map供应商， map 的类型未指定，因此这里不能做任何声明。

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

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

当前的实现产生一个 ArrayList , 超出容量时不得不进行复制操作，但由于容量每次增加一个倍数，所以仍然存在O(n)的净复杂度。用于添加 n 个元素。可以合理地假设 toList() 的 future 更改实现不会使成本比我们今天更糟。所以默认的时间复杂度groupingBy Collection 很可能O(n) .

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

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