क्या Collections.sort(list) जांचता है कि list पहले ही सॉर्ट किया गया है या यह शायद किसी अन्य कारण से ओ (1) है?
या, क्या सॉर्ट किए गए को सॉर्ट करने का अच्छा विचार है और इसे पर कॉल करने पर सूची में तत्व जोड़ने पर true/false पर सेट करें?जावा - एक ओ (1) ऑपरेशन पहले से क्रमबद्ध सूची पर सॉर्ट() को कॉल कर रहा है?
आप कैसे निर्धारित कर सकते हैं कि कोई सूची इसे देखे बिना क्रमबद्ध है? यह O(1) नहीं होगा। यह निर्धारित करना कि कोई सूची क्रमबद्ध है, कम से कम O(n) लेता है।
इसका मतलब यह होगा कि Collections.sort यह जांचने के लिए परेशान था कि प्रत्येक सॉर्टिंग ऑपरेशन पहले O(n) + O(n log n) का औसत लेगा या नहीं।
ओ (1) का कोई तरीका नहीं है, आप यह जांच नहीं सकते कि संग्रह ओ (एन) से तेज क्रमबद्ध है या नहीं। झंडा होना ठीक होना चाहिए, लेकिन यह सुनिश्चित करने के लिए कि आप वास्तव में क्या कर रहे हैं, निश्चित रूप से कहना मुश्किल है।
आम तौर पर, पहले से क्रमबद्ध सूची को सॉर्ट करने से यह तेज़ नहीं होता है (बबल प्रकार जैसे सरल प्रकार को छोड़कर) कुछ मामलों में पूर्व-क्रमबद्ध धीमा होता है।
संग्रह .sort() के मामले में, क्रमबद्ध सूची को सॉर्ट करने के लिए कोई तेज़ नहीं है।
वास्तव में पूरी तरह से सच नहीं है। iirc जावा कुछ Java7 और Timsort के साथ शुरू बातों के लिए Timsort उपयोग कर रहा है आंशिक रूप से क्रमबद्ध सूची, यानी सैद्धांतिक 'हे की तुलना में बेहतर छँटाई में काफी अच्छा है (एन एन लॉग इन करें)' – Voo
+1 के लिए पूर्व हल कर कुछ मामलों में धीमी –
जावा 7 के साथ तथ्य के मामले में, जावा ने कुछ क्रमबद्ध कार्यों के लिए विलय से TimSort (पायथन देव टिम पीटर्स के नाम पर इसे लागू किया है) के नाम पर स्विच किया है।
हालांकि यह ओ (1) नहीं है, जबकि पहले से क्रमबद्ध, या आंशिक रूप से क्रमबद्ध सूची को टिमसॉर्ट के साथ सॉर्ट करना पूरी तरह यादृच्छिक डेटा सेट को सॉर्ट करने से काफी अधिक कुशल है (बाद में तुलनात्मक प्रकार के लिए O(n log n) से अधिक कुशल होने का कोई तरीका नहीं है , यह यादृच्छिक डेटा के लिए सच नहीं है)।
ठीक है, लेकिन संभावना है कि जो व्यक्ति से पूछा उपयोग कर रहा है जावा 7 काफी कम है (कुछ लोगों का कहना 18% http://blog.jelastic.com/2011/12/07/java-7-adoption-grows-to-18-percent/) –
@ vitalik संभावना है कि भविष्य के पाठक जावा 7 का उपयोग करेंगे या बाद में केवल वहां से बढ़ सकते हैं। एसओ एक सूचना के संग्रह के रूप में इरादा है, एक मंच नहीं। – EJP
@EJP इस बात को ध्यान में रखते हुए कि उस टिप्पणी को पोस्ट करते समय उस पोस्टिक ने मेरी पोस्ट को कम नहीं किया, क्या आपने अनजाने में गलत बात की? अन्यथा मुझे आश्चर्य है कि कोई भी मेरी पोस्ट को कम करेगा। बी 2 टी: मुझे लगता है कि जब तक मैं स्पष्ट रूप से उल्लेख करता हूं कि यह जावा 7 के लिए केवल सच है + कितने लोग जो भी संस्करण का उपयोग कर रहे हैं, वह बहुत महत्वपूर्ण नहीं है - 18% अभी भी बहुत सारे लोग हैं। – Voo
सख्ती से बोलते हुए, ओ (1) का मतलब 1 सूचकांक नहीं है :) – unbeli
@unbeli +1 ने मेरा जवाब सही किया। – Aidanc
और 'ओ (एन) + ओ (एन लॉग एन) 'ओ (एन लॉग एन) के समान है' :) – unbeli