क्या आप ओ (एन) अमूर्त जटिलता में एन पूर्णांक को सॉर्ट कर सकते हैं?

Question

क्या यह सैद्धांतिक रूप से ओ (एन) की एक अमूर्त जटिलता में एन पूर्णांक की सरणी को सॉर्ट करना संभव है?

ओ (एन) जटिलता का सबसे खराब मामला बनाने की कोशिश करने के बारे में क्या?

आज अधिकांश एल्गोरिदम ओ (nlogn) औसत + ओ (एन^2) सबसे खराब मामले पर बनाए जाते हैं। कुछ, अधिक स्मृति का उपयोग करते समय ओ (nlogn) सबसे खराब हैं।

क्या आप स्मृति उपयोग पर कोई सीमा नहीं दे सकते हैं ऐसे एल्गोरिदम बनाते हैं? यदि आपकी मेमोरी सीमित है तो क्या होगा? यह आपके एल्गोरिदम को कैसे नुकसान पहुंचाएगा?

Answer 1

किसी भी पेज intertubes कि तुलना आधारित प्रकार will tell you के साथ सौदों पर है कि आप नहीं कर सकते हैं तरह तुलना प्रकार के साथ O(n lg n) की तुलना में तेजी। यही है, अगर आपका सॉर्टिंग एल्गोरिदम एक दूसरे के खिलाफ 2 तत्वों की तुलना करके आदेश का निर्णय लेता है, तो आप उससे बेहतर नहीं कर सकते हैं। उदाहरणों में क्विकॉर्ट, बबलसॉर्ट, विलयोर्ट शामिल हैं।

गिनती सॉर्ट या बाल्टी सॉर्ट या रेडिक्स सॉर्ट जैसे कुछ एल्गोरिदम तुलना का उपयोग नहीं करते हैं। इसके बजाए, वे डेटा के मूल्यों या डेटा मूल्य के आकार की तरह डेटा के गुणों पर भरोसा करते हैं।

उन एल्गोरिदम में तेज जटिलताएं हो सकती हैं। यहां एक उदाहरण परिस्थिति है:

आप 10^6 पूर्णांकों छँटाई कर रहे हैं, और प्रत्येक पूर्णांक 0 और 10 के बीच है। फिर आप शून्य, संख्या, जुड़वां इत्यादि की संख्या गिन सकते हैं और सॉर्ट किए गए क्रम में उन्हें वापस थूक सकते हैं। इस प्रकार countsort काम करता है, O(n + m) में जहां m आपके डेटाम को लेने वाले मानों की संख्या है (इस मामले में, m=11)।

एक और:

आप 10^6 द्विआधारी तार कि सभी लंबाई में ज्यादा से ज्यादा 5 चरित्र छँटाई कर रहे हैं। आप इसके लिए रेडिक्स सॉर्ट का उपयोग कर सकते हैं: पहले उन्हें अपने पहले अक्षर के आधार पर 2 बाल्टी में विभाजित करें, फिर रेडिक्स-उन्हें दूसरे अक्षर, तीसरे, चौथे और पांचवें के लिए क्रमबद्ध करें। जब तक प्रत्येक चरण एक स्थिर प्रकार है, तो आपको O(nm) में पूरी तरह से क्रमबद्ध सूची के साथ समाप्त होना चाहिए, जहां एम आपके डेटाम में अंकों या बिट्स की संख्या है (इस मामले में, m=5)।

लेकिन सामान्य स्थिति में, आप विश्वसनीय रूप से O(n lg n) से अधिक क्रमबद्ध नहीं कर सकते (तुलनात्मक प्रकार का उपयोग करके)।

Answer 2

मुझे विश्वास है कि आप radix sort देख रहे हैं।

Answer 3

यदि पूर्णांक सीमित सीमा में हैं तो उनमें से एक ओ (एन) "सॉर्ट" में "एन" बिट्स का थोड़ा वेक्टर होना शामिल होगा ... प्रश्न में पूर्णांक पर लूपिंग और एन% 8 बिट सेट करना ऑफ बाइट सरणी में ऑफसेट एन // 8 का सच है। यह एक "ओ (एन)" ऑपरेशन है। सभी सेट बिट्स को सूचीबद्ध/गणना/वापसी/प्रिंट करने के लिए उस बिट सरणी पर एक और लूप, इसी तरह, एक ओ (एन) ऑपरेशन है। (स्वाभाविक रूप से ओ (2 एन) ओ (एन) में कम हो गया है)।

यह एक विशेष मामला है जहां एन स्मृति या फ़ाइल (तलाश()) संचालन के भीतर फिट करने के लिए पर्याप्त छोटा है)।यह एक सामान्य समाधान नहीं है; लेकिन यह बेंटले के "प्रोग्रामिंग मोती" में वर्णित है --- और कथित तौर पर वास्तविक दुनिया की समस्या का एक व्यावहारिक समाधान था (जिसमें टेलीफोन नंबरों की "फ्रीलीस्ट" जैसी कुछ शामिल थी ... कुछ ऐसा: पहला उपलब्ध फ़ोन नंबर ढूंढ सकता है जो एक नए ग्राहक को जारी किया जाना चाहिए)।

(नोट: लॉग (10 * 10) लंबाई के 10 अंकों तक प्रत्येक संभावित पूर्णांक का प्रतिनिधित्व करने के लिए ~ 24 बिट्स है ... इसलिए 2 * में एक बहुत ही कमरा है जो सामान्य यूनिक्स/लिनक्स अधिकतम के 31 बिट्स आकार मेमोरी मैपिंग)।

Answer 4

मैं अभी तक स्वीकार किए गए उत्तर से काफी खुश नहीं हूं। तो मैं एक उत्तर पुनः प्रयास कर रहा हूं:

क्या यह सैद्धांतिक रूप से ओ (एन) की एक अमूर्त जटिलता में एन पूर्णांक की सरणी को सॉर्ट करना संभव है?

इस प्रश्न का उत्तर उस मशीन पर निर्भर करता है जो सॉर्टिंग एल्गोरिदम निष्पादित करेगा। यदि आपके पास यादृच्छिक एक्सेस मशीन है, जो बिल्कुल 1 बिट पर काम कर सकती है, तो आप radix sort को k बिट्स के साथ पूर्णांक के लिए कर सकते हैं, जो पहले ही सुझाया गया था। तो आप O(kn) जटिलता के साथ समाप्त हो जाते हैं।
लेकिन यदि आप कम से कम k बिट्स (जो सभी उपभोक्ता कंप्यूटर हैं) के शब्द आकार के साथ एक निश्चित आकार की वर्ड मशीन पर काम कर रहे हैं, तो आप सबसे अच्छा प्राप्त कर सकते हैं O(n log n)। ऐसा इसलिए है क्योंकि log n < k या आप पहले count sort कर सकते हैं और फिर O (n log n) एल्गोरिदम के साथ सॉर्ट कर सकते हैं, जो पहले मामले को भी उत्पन्न करेगा।

ओ (एन) जटिलता का सबसे खराब मामला बनाने की कोशिश करने के बारे में क्या?

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

क्या आप स्मृति उपयोग पर कोई सीमा नहीं दे सकते हैं ऐसे एल्गोरिदम बनाते हैं?

तो ऊपर से जैसा संभव नहीं है। और शेष प्रश्न इसलिए प्रासंगिक नहीं हैं।