java.util.stream.Stream<T>.sorted() 的大 O 复杂度
有谁知道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))
相关文章