我想了解下面给定语句的时间复杂度。(在 Java 8 中)
list.stream().collect(groupingBy(...));
任何的想法?
最佳答案
这个问题没有通用的答案,因为时间复杂度取决于所有操作。由于必须完全处理流,因此基本时间复杂度为 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 的查找和下游收集器的元素处理(乘以元素数量)中最糟糕的情况,因为我们可以有一个包含所有项目的组,或者每个项目都在自己的组中。
但通常,您能够预测特定分组操作的偏差,因此您可能希望计算该特定操作的时间复杂度,而不是依赖关于所有分组操作的一般声明。
关于java - Java8中分组的复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40823293/