java.util.stream की बिग-ओ जटिलता। स्ट्रीम <T> .sorted()

Question

क्या किसी को पता है कि java.util.stream.Stream<T>.sorted() की समय जटिलता क्या है?

Answer 1

ठीक है, sorted() अपने आप में ओ (1) है, क्योंकि यह एक मध्यवर्ती ऑपरेशन है जो धारा का उपभोग नहीं करता है, लेकिन बस पाइपलाइन पर एक ऑपरेशन जोड़ता है।

एक बार धारा एक टर्मिनल आपरेशन द्वारा सेवन किया जाता है, तरह होता है और या तो

• यह कुछ भी नहीं है (ओ (1)), क्योंकि धारा जानता है कि तत्वों को पहले ही हल कर रहे हैं (क्योंकि वे Arrays.sort() करने के लिए एक SortedSet से आते हैं, उदाहरण के लिए)
• या स्ट्रीम समानांतर नहीं है, और यह प्रतिनिधियों (O (n लॉग ऑन एन))
• या स्ट्रीम समानांतर है, और यह प्रतिनिधियों Arrays.parallelSort() (O (n लॉग में एन))

Answer 2

जेडीके 8 के रूप में, मुख्य सॉर्टिंग एल्गोरिदम जिसे अनुक्रमिक सॉर्टिंग के लिए मानक स्ट्रीम एपीआई कार्यान्वयन में भी उपयोग किया जाता है TimSort है। इसका सबसे खराब मामला O(n log n) है, लेकिन यह अविश्वसनीय रूप से तेज़ काम करता है (O(n) और काफी छोटा स्थिरांक के साथ) यदि डेटा को पूर्व निर्धारित किया जाता है (आंशिक रूप से या विपरीत दिशा में) या आंशिक रूप से संरक्षित (उदाहरण के लिए, यदि आप दो क्रमबद्ध सूचियों को जोड़ते हैं और उन्हें फिर से क्रमबद्ध करते हैं)।