Java8中分组的复杂性

Question

我想在下面学习给定语句的时间复杂度。（在Java8中）

html" target="_blank">list.stream().collect(groupingBy(...));

任何想法？

Answer 1

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

因此，假设没有影响时间复杂度的中间操作，则groupingBy必须评估每个元素的功能，该功能应独立于其他元素，因此不影响时间复杂度（无论它有多昂贵，因为O(…)时间复杂度仅表明我们，时间如何随着大量流元素而
缩放 ）。然后，它将元素插入地图，这可能取决于已经包含的元素的数量。如果没有定制Map供应商，则地图的类型是不确定的，因此在此无法声明。

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

默认的 下游 收集器是toList()，它会产生未指定的List类型，因此，再说一遍，关于添加元素的成本我们无能为力。

当前的实现产生一个ArrayList，当超出容量时必须执行复制操作，但是由于每次都会将容量提高一个 因数 ，因此O(n)添加 n个
元素仍然存在净复杂性。可以合理地假设，将来对toList()实现进行更改不会使成本比我们今天要差。因此，默认groupingBy集合的时间可能很复杂O(n)。

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

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