由于时间复杂度取决于所有操作,因此没有通用的答案。由于必须完全处理流,因此必须将其基本时间复杂度
O(n)乘以每个元素完成的所有操作的成本。假设迭代成本本身并不比差
O(n),大多数流源就是这种情况。
因此,假设没有影响时间复杂度的中间操作,则
groupingBy必须评估每个元素的功能,该功能应独立于其他元素,因此不影响时间复杂度(无论它有多昂贵,因为
O(…)时间复杂度仅表明我们,时间如何随着大量流元素而
缩放 )。然后,它将元素插入地图,这可能取决于已经包含的元素的数量。如果没有定制
Map供应商,则地图的类型是不确定的,因此在此无法声明。
实际上,可以合理地假设结果将是某种
O(1)默认情况下具有净查找复杂性的某种哈希映射。因此
O(n),分组的净时间复杂度为。然后,我们有了 下游
收集器。
默认的 下游 收集器是
toList(),它会产生未指定的
List类型,因此,再说一遍,关于添加元素的成本我们无能为力。
当前的实现产生一个
ArrayList,当超出容量时必须执行复制操作,但是由于每次都会将容量提高一个 因数 ,因此
O(n)添加 n个
元素仍然存在净复杂性。可以合理地假设,将来对
toList()实现进行更改不会使成本比我们今天要差。因此,默认
groupingBy集合的时间可能很复杂
O(n)。
如果我们将自定义
Map收集器与自定义下游收集器一起使用,则复杂度取决于平均组数与每个组中元素的数量之比。最坏的情况是地图查找和下游收集器的元素处理(元素数量的乘积)中的最坏情况,因为我们可以有一个包含所有项目的组,或者每个项目都在自己的组中。
但是通常,您能够预测特定分组操作的偏差,因此,您将希望计算该特定操作的时间复杂度,而不是通常依赖于所有分组操作的声明。



