Độ phức tạp lớn của O. java.util.stream.Stream <T> .sorted()

Question

Có ai biết độ phức tạp thời gian của java.util.stream.Stream<T>.sorted() là gì không?

Answer 1

Vâng, sorted() chính nó là O (1), vì nó là một hoạt động trung gian không tiêu thụ luồng, nhưng chỉ cần thêm hoạt động vào đường ống.

Khi dòng được tiêu thụ bởi một hoạt động thiết bị đầu cuối, các loại xảy ra và một trong hai

• nó không làm bất cứ điều gì (O (1)) vì dòng biết rằng các yếu tố đã được sắp xếp (vì họ đến từ một SortedSet, ví dụ)
• hoặc suối không được song song, và nó đại biểu Arrays.sort() (O (n log n))
• hoặc dòng là song song, và nó đại biểu Arrays.parallelSort() (O (n log n))

Answer 2

Kể từ JDK 8, thuật toán sắp xếp chính cũng được sử dụng trong triển khai API luồng chuẩn để phân loại tuần tự là TimSort. Trường hợp xấu nhất của nó là O(n log n), nhưng nó hoạt động cực nhanh (với O(n) và hằng số khá nhỏ) nếu dữ liệu được phân loại (theo hướng trước hoặc ngược) hoặc được phân loại một phần (ví dụ, nếu bạn nối hai danh sách đã sắp xếp và sắp xếp lại chúng).