栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

Java8中分组的复杂性

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Java8中分组的复杂性

由于时间复杂度取决于所有操作,因此没有通用的答案。由于必须完全处理流,因此必须将其基本时间复杂度

O(n)
乘以每个元素完成的所有操作的成本。假设迭代成本本身并不比差
O(n)
,大多数流源就是这种情况。

因此,假设没有影响时间复杂度的中间操作,则

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

实际上,可以合理地假设结果将是某种

O(1)
默认情况下具有净查找复杂性的某种哈希映射。因此
O(n)
,分组的净时间复杂度为。然后,我们有了 下游
收集器。

默认的 下游 收集器是

toList()
,它会产生未指定的
List
类型,因此,再说一遍,关于添加元素的成本我们无能为力。

当前的实现产生一个

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

如果我们将自定义

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

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



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/464062.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号