java.util.stream.Stream的大O复杂性<T> .sorted()

Question

有谁知道时间的复杂性java.util.stream.Stream<T>.sorted()是什么？

Answer 1

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

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

• 它没有做任何事情(O(1)),因为流知道元素已经排序(例如,因为它们来自SortedSet)
• 或者流不是并行的,它委托给Arrays.sort()(O(n log n))
• 或者流是并行的,它委托给Arrays.parallelSort()(O(n log n))

Answer 2

从JDK 8开始，在标准流API实现中用于顺序排序的主要排序算法是TimSort。最坏的情况是O(n log n)，但是O(n)如果对数据进行预排序（正向或反向）或部分进行预排序（例如，如果您将两个排序后的列表连接起来并再次对其进行排序），则它的工作速度将非常快（常数很小）。