Java Stream distinct（）.sorted（） 的时间复杂度是多少？

Question

每次我接受编码面试时，我总是避免使用Java流，因为我不能很好地分析时间复杂性。

举个例子:在我的日常工作中，我可能会这样写:

Arrays.stream(a).distinct().sorted().toArray();

以获取唯一编号并对其进行排序。

但我很好奇时间的复杂性会是..？是 distinct（）.sorted 会变成一个嵌套的循环？

我需要将它们分开吗？

int[] arr = Arrays.stream(a).distinct().toArray();
Arrays.stream(arr).sorted().toArray();

所以有时候当我接受采访时，我会使用set来区分然后对它们进行排序......但是我真的很想写一个干净的代码......

如果有人能帮忙！谢谢大家！

Answer 1

不可能有明确的说法，因为你是针对一个接口进行开发的，而规范并没有要求特定的排序算法。

对于通用的流，我们必须假设一个比较排序，其最坏情况为O（n log n）是任何算法都无法避免的。

但您的示例使用的是IntStream，原则上可以使用计数排序或类似排序，具有O（n）。对于参考实现，这在实践中不会发生，因为在实践中，具有更好的最坏情况时间复杂性并不一定会导致更好的性能，并且元素的最大数量限制为JVM的最大数组大小。

准确度（）的时间复杂度为O（n），因为它只是检查添加到HashSet中是否成功。将O（n）与O（n log n）组合导致整体复杂度为O（n log n）。也许面试官把时间复杂性的组合弄错了。

但这是一个很好的例子，表明时间复杂度并不等于性能。使用 sorted（）.distinct（） 时，distinct（） 操作将利用传入元素的排序特性，因此无需在后台构建 HashSet¹。由于参考实现没有设置基元值，因此这消除了大量的装箱开销。另一方面，使用 distinct（）.sorted（） 可以减少要排序的元素数量，但它需要具有明显少于总流元素的独特元素才能获得回报。

这种性能差异不包括在时间复杂度中，这两种方法仍然相同。但是如前所述，对于原始类型的流，具有不同时间复杂度的不同算法是可能的。

但是有一件事，我们可以肯定地说。当您将操作拆分为两个流操作时，例如从第一个流请求结果数组并再次将其传递给Arrays.stream，底层实现不可能在下一个操作中利用有关上一个操作的知识。

请注意，上面的语句假设了一个终端操作，就像您的示例中的< code>toArray一样，它消耗所有元素，并要求维护生成的相遇顺序。对于其他短路或无序的终端操作，总的时间复杂度可能会改变，例如< code>sorted()。findFirst()可以优化为相当于< code>min()的值，或者可以取消无序终端操作的排序步骤，比如< code>sum()。这在当前的参考实现中不会发生，但是，如前所述，您是针对接口进行编程的。

对于原始流，这仅适用于Java