Java8 中分组的复杂性8

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

因此，假设没有影响时间复杂度的中间操作，则必须评估每个元素的函数，该函数应独立于其他元素，因此不会影响时间复杂度（无论它有多昂贵，因为时间复杂度仅告诉我们，时间如何缩放大量流元素）。然后，它将元素插入到映射中，这可能取决于已包含的元素的数量。如果没有自定义供应商，地图的类型是未指定的，因此，无法在此处进行任何声明。groupingByO(…)Map

在实践中，可以合理地假设结果将是某种具有网络查找复杂性的哈希映射。因此，我们有一个净时间复杂度，用于分组。然后，我们有下游收集器。O(1)O(n)

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

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

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

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