java.util.stream.Stream<T>.sorted() 的大 O 复杂度 [英] Big-O complexity of java.util.stream.Stream<T>.sorted()

问题描述

有谁知道java.util.stream.Stream<T>.sorted()的时间复杂度是多少?

Does anyone know what the time complexity of java.util.stream.Stream<T>.sorted() is?

推荐答案

嗯，sorted() 本身就是 O(1)，因为它是一个不消耗流的中间操作，但只是简单地向管道添加一个操作.

Well, sorted() in itself is O(1), since it's an intermediate operation that doesn't consume the stream, but simply adds an operation to the pipeline.

一旦终端操作消耗了流，就会发生排序

Once the stream is consumed by a terminal operation, the sort happens and either

• 它什么都不做 (O(1))，因为流知道元素已经排序(例如，因为它们来自 SortedSet)
• 或者流不是并行的，它委托给Arrays.sort() (O(n log n))
• 或者流是并行的，它委托给Arrays.parallelSort() (O(n log n))

• it doesn't do anything (O(1)) because the stream knows that the elements are already sorted (because they come from a SortedSet, for example)
• or the stream is not parallel, and it delegates to Arrays.sort() (O(n log n))
• or the stream is parallel, and it delegates to Arrays.parallelSort() (O(n log n))

这篇关于java.util.stream.Stream<T>.sorted() 的大 O 复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！