Java8中分组的复杂性

Question

我想了解下面给出的语句的时间复杂性.(在Java8中)

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定义下游收集器的自定义收集器,则复杂性取决于组的平均数量与每组的元素数量比率.最糟糕的情况是最差的,地图的查找和下游收集器的元素处理(元素数量的次数),因为我们可以有一个组包含所有项目或每个项目在其自己的组中.

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