चयन एल्गोरिथ्म: Difference between revisions

[[ कंप्यूटर विज्ञान |'''''कंप्यूटर विज्ञान''''']] '''''में''''', एक चयन एल्गोरिदम की  [[सूची (सार डेटा प्रकार)|सूची]]  या सरणी में k वें सबसे छोटी संख्या खोजने के लिए एल्गोरिदम है। इस तरह की संख्या को k वें ''[[ order statistic |क्रम सांख्यिकी]]''  कहा जाता है। इसमें [[ न्यूनतम |न्यूनतम]], अधिकतम और माध्यमिक तत्वों को खोजने की परिस्थिति सम्मिलित होती हैं। O(''n'')-time (सबसे खराब स्थिति का रैखिक समय) अधिकतम एल्गोरिदम हैं, तथा संरचित डेटा के लिए उपरेखीय प्रदर्शन संभव होता है। अत्यन्त O(1) वर्गीकृत किए गए डेटा की एक सरणी के लिए, चयनित अधिक जटिल समस्याओं जैसे  [[निकटतम पड़ोसी समस्या|निकटतम पास की]]  और सबसे छोटी पथ समस्याओं की उप-समस्या है। कई चयनित एल्गोरिदम एक  [[ छँटाई एल्गोरिथ्म |वर्गीकरण एल्गोरिथ्म]]  को सामान्यीकृत करके व्युत्पन्न किए जाते हैं, और इसके विपरीत कुछ वर्गिकरण एल्गोरिदम चयन के बार-बार आवेदन के रूप में प्राप्त किए जा सकते हैं।

चयन [[ कलन विधि |एल्गोरिदम]] सबसे सरल स्थिति सूची के माध्यम से पुनरावृति करके न्यूनतम या अधिकतम तत्व ढूंढ रहा है, चल रहे न्यूनतम का ट्रैक रखते हुए - अब तक का न्यूनतम या अधिकतम और चयन प्रकार संबंधित के रूप में देखा जा सकता है। इसके विपरीत चयन एल्गोरिथ्म का सबसे जटिल परिस्थिति माध्यिका को खोज रहा है। वास्तव में एक विशेष मध्य-चयन एल्गोरिदम का उपयोग सामान्य चयन एल्गोरिदम बनाने के लिए किया जा सकता है, जैसा कि मध्यस्थों के मध्य में होता है। सबसे प्रसिद्ध चयन एल्गोरिथम [[ तुरंत चयन | शीघ्र चयन]] है, जो [[ जल्दी से सुलझाएं |शीघ्र वर्गीकरण]] से संबंधित होता है। शीघ्र वर्गीकरण, इसका असम्बद्ध रूप से सर्वोत्तम औसत प्रदर्शन है, लेकिन सबसे खराब स्थिति वाला प्रदर्शन खराब है, हालांकि इसे सर्वोत्तम सबसे खराब प्रदर्शन देने के लिए संशोधित किया जा सकता है।

सूची या सरणी को क्रमबद्ध करके वांछित तत्व का चयन करके, चयन को क्रमबद्ध करने के लिए  [[ कमी (जटिलता) |कम]] किया जा सकता है। यह विधि एकल तत्व का चयन करने के लिए अप्रभावी है, लेकिन कुशल है जब एक सरणी से कई चयन किए जाने की आवश्यकता होती है, तो इस स्थिति में केवल एक प्रारंभिक बहुमूल्य प्रकार की आवश्यकता होती है, जिसके बाद कई सुलभ चयन संचालन होते हैं। O(1) सरणी के लिए, हालांकि चयन एक लिंक की गई सूची में O(''n'') है, युग्म क्रमबद्ध यादृच्छिक पहुंच की कमी के कारण सामान्य रूप से वर्गीकरण के लिए O(n log n) time की आवश्यकता होती है, जहां n सूची की लंबाई है, हालांकि  [[ आपको कामयाबी मिले |मूलांक वर्गीकरण]]  और [[ गिनती का प्रकार ]] जैसे गैर-तुलनात्मक वर्गीकरण एल्गोरिदम के साथ निम्न परिबंध संभव है।

पूरी सूची या सरणी को क्रमबद्ध करने के अतिरिक्त k सबसे छोटे या k सबसे बड़े तत्वों का चयन करने के लिए  [[ आंशिक छँटाई |आंशिक वर्गीकरण]]  का उपयोग कर सकते हैं। k वें सबसे छोटा (resp., k वें सबसे बड़ा तत्व) तब आंशिक रूप से क्रमबद्ध सूची का सबसे बड़ा (resp., सबसे छोटा तत्व) होता है तो इसके बाद किसी सरणी में पहुँचने के लिए O(1) लगता है तथा किसी सूची में पहुँचने के लिए O(k) लेता है।

यदि आंशिक वर्गीकरण को तनाव मुक्त किया जाता है, जिससे k सबसे छोटे तत्व लौटाए जाते हैं, लेकिन क्रम में नहीं O(k log k) के कारक को समाप्त किया जा सकता है। एक अतिरिक्त अधिकतम चयन (O(k) समय लेते हुए) आवश्यक होता है, लेकिन  <math>k \leq n</math> यह अभी भी O(n) की स्पर्शोन्मुख जटिलता उत्पन्न करता है। वास्तव में विभाजन-आधारित चयन एल्गोरिदम स्वयं k वें सबसे छोटा तत्व तथा k सबसे छोटा तत्व अन्य (तत्वों के क्रम में नहीं) दोनों को उत्पन्न करता है। यह O(''n'') time में किया जा सकता है - शीघ्र चयन की औसत जटिलता और परिष्कृत विभाजन-आधारित चयन एल्गोरिदम की सबसे खराब जटिलता की स्थिति होती है।

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

इस प्रकार अनियंत्रित आंशिक वर्गीकरण (न्यूनतम k तत्व, लेकिन आदेशित नहीं) और k वें तत्व का चयन बहुत समान समस्याएँ होती हैं। न केवल उनके पास समान स्पर्शोन्मुख जटिलता है, O(n), लेकिन दोनों में से किसी एक के समाधान को सीधा एल्गोरिथ्म द्वारा दूसरे के समाधान में परिवर्तित किया जा सकता है। अधिकतम k तत्व ढूँढना या k वें तत्व के मान के वर्गीकरण के नीचे सूची के तत्वों को फ़िल्टर करना होता है।  

=== आंशिक चयन प्रकार ===

अधिक सामान्य रूप से एक आंशिक चयन वर्गीकरण सरल चयन एल्गोरिदम उत्पन्न करता है, जो O(''kn'') time लेता है। यह असम्बद्ध रूप से अप्रभावी होता है, लेकिन पर्याप्त रूप से कुशल हो सकता है यदि k छोटा है, तथा लागू करना आसान है। विशेष रूप से हम केवल एसके न्यूनतम मान को पाते हैं और इसे प्रारम्भ में ले जाते हैं, शेष सूची में तब तक दोहराते हैं जब तक कि हम k तत्वों को संचित नहीं कर लेते हैं, और फिर k वें तत्व को वापस कर देते हैं। यहआंशिक चयन वर्गीकरण-आधारित एल्गोरिथम होता है।  

{{further|Quickselect}}

विभाजन-आधारित एल्गोरिदम आम तौर पर जगह में किया जाता है, जिसके परिणामस्वरूप डेटा को आंशिक रूप से सॉर्ट किया जाता है। O(n) अतिरिक्त स्थान की कीमत पर, मूल डेटा को बदले बिना, उन्हें जगह से बाहर किया जा सकता है।

=== पिवट रणनीति === के रूप में मेडियन चयन

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

विस्तार से, एक माध्य-चयन एल्गोरिथ्म दिया गया है, कोई इसे चयन एल्गोरिथ्म प्राप्त करते हुए, Quickselect में एक धुरी रणनीति के रूप में उपयोग कर सकता है। यदि माध्य-चयन एल्गोरिथ्म इष्टतम है, जिसका अर्थ ओ (एन) है, तो परिणामी सामान्य चयन एल्गोरिथ्म भी इष्टतम है, फिर से रैखिक अर्थ है। ऐसा इसलिए है क्योंकि क्विकसेलेक्ट एक डिवाइड और जीत एल्गोरिथ्म है, और प्रत्येक धुरी पर माध्यिका का उपयोग करने का अर्थ है कि प्रत्येक चरण में खोज सेट आकार में आधे से कम हो जाता है, इसलिए समग्र जटिलता एक ज्यामितीय श्रृंखला है जो प्रत्येक चरण की जटिलता से गुणा होती है, और इस प्रकार बस एक स्थिर समय एक एकल चरण की जटिलता, वास्तव में <math>2 = 1/(1-(1/2))</math> बार (श्रृंखला का योग)।

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

छँटाई द्वारा चयन के विपरीत, बार-बार चयन द्वारा क्रमिक रूप से क्रमबद्ध किया जा सकता है। संक्षेप में, चयन केवल एक तत्व, k वें तत्व उत्पन्न करता है। हालांकि, व्यावहारिक चयन एल्गोरिदम में अक्सर आंशिक छँटाई शामिल होती है, या ऐसा करने के लिए संशोधित किया जा सकता है। आंशिक छँटाई द्वारा चयन स्वाभाविक रूप से ऐसा करता है, तत्वों को k तक छाँटता है, और विभाजन द्वारा चयन भी कुछ तत्वों को छाँटता है: पिवोट्स को सही स्थिति में क्रमबद्ध किया जाता है, जिसमें k वें तत्व अंतिम धुरी होता है, और पिवोट्स के बीच के तत्वों का मान होता है धुरी मूल्यों के बीच। विभाजन-आधारित चयन और विभाजन-आधारित छँटाई के बीच का अंतर, जैसा कि Quickselect बनाम Quicksort में है, यह है कि चयन में प्रत्येक धुरी के केवल एक तरफ रिकर्स करता है, केवल पिवोट्स को छांटता है (औसतन लॉग (एन) पिवोट्स का उपयोग किया जाता है), धुरी के दोनों किनारों पर पुनरावर्ती होने के बजाय।

इसका उपयोग उसी डेटा पर बाद के चयनों को गति देने के लिए किया जा सकता है; चरम में, एक पूरी तरह से क्रमबद्ध सरणी ओ (1) चयन की अनुमति देती है। इसके अलावा, पहले एक पूर्ण सॉर्ट करने की तुलना में, बार-बार चयन द्वारा क्रमिक रूप से सॉर्ट करना परिशोधन विश्लेषण कई चयनों पर सॉर्टिंग लागत।

आंशिक रूप से सॉर्ट किए गए डेटा (k तक) के लिए, जब तक आंशिक रूप से सॉर्ट किया गया डेटा और इंडेक्स k जिस तक डेटा सॉर्ट किया जाता है, रिकॉर्ड किया जाता है, k से कम या उसके बराबर j के बाद के चयन केवल jth तत्व का चयन कर सकते हैं, क्योंकि यह पहले से ही सॉर्ट किया गया है, जबकि k से बड़ा j का चयन केवल k वें स्थिति से ऊपर के तत्वों को सॉर्ट करने की आवश्यकता है।

विभाजित डेटा के लिए, यदि पिवोट्स की सूची संग्रहीत की जाती है (उदाहरण के लिए, सूचकांकों की एक क्रमबद्ध सूची में), तो बाद के चयनों को केवल दो पिवोट्स (नीचे और ऊपर के निकटतम पिवोट्स) के बीच के अंतराल में चयन करने की आवश्यकता होती है। सबसे बड़ा लाभ शीर्ष-स्तरीय पिवोट्स से है, जो महंगे बड़े विभाजनों को समाप्त करता है: डेटा के मध्य के पास एक एकल पिवट भविष्य के चयन के लिए समय को आधा कर देता है। बाद के चयनों पर पिवट सूची बढ़ेगी, क्योंकि डेटा अधिक क्रमबद्ध हो जाता है, और यहां तक ​​​​कि एक पूर्ण प्रकार के आधार के रूप में विभाजन-आधारित सॉर्ट को भी पास किया जा सकता है।

== उपरेखीय समय == में चयन करने के लिए डेटा संरचनाओं का उपयोग करना

डेटा की एक असंगठित सूची को देखते हुए, न्यूनतम तत्व को खोजने के लिए रैखिक समय (Ω(n)) की आवश्यकता होती है, क्योंकि हमें प्रत्येक तत्व की जांच करनी होती है (अन्यथा, हम इसे याद कर सकते हैं)। यदि हम सूची को व्यवस्थित करते हैं, उदाहरण के लिए इसे हर समय क्रमबद्ध करके रखते हैं, तो k वें सबसे बड़ा तत्व का चयन करना तुच्छ है, लेकिन फिर सम्मिलन के लिए रैखिक समय की आवश्यकता होती है, जैसा कि दो सूचियों के संयोजन जैसे अन्य कार्यों में होता है।

उपरैखिक समय में एक आदेश आंकड़े खोजने की रणनीति उपयुक्त डेटा संरचनाओं का उपयोग करके डेटा को एक संगठित फैशन में संग्रहित करना है जो चयन की सुविधा प्रदान करता है। ऐसी दो डेटा संरचनाएँ ट्री-आधारित संरचनाएँ और फ़्रीक्वेंसी टेबल हैं।

जब केवल न्यूनतम (या अधिकतम) की आवश्यकता होती है, तो हीप (डेटा संरचना) का उपयोग करने के लिए एक अच्छा तरीका है, जो निरंतर समय में न्यूनतम (या अधिकतम) तत्व खोजने में सक्षम है, जबकि सम्मिलन सहित अन्य सभी ऑपरेशन ओ हैं (लॉग एन) या बेहतर। अधिक आम तौर पर, एक [[ स्व-संतुलन बाइनरी सर्च ट्री ]] को आसानी से संवर्धित किया जा सकता है ताकि एक तत्व को सम्मिलित करना और O(log n) समय में k वें सबसे बड़ा तत्व खोजना संभव हो सके; इसे [[ ऑर्डर स्टेटिस्टिक ट्री ]] कहा जाता है। हम बस प्रत्येक नोड में कितने वंशज हैं, इसकी गिनती करते हैं, और इसका उपयोग यह निर्धारित करने के लिए करते हैं कि किस पथ का अनुसरण करना है। सूचना को कुशलता से अपडेट किया जा सकता है क्योंकि एक नोड को जोड़ने से केवल इसके ओ (लॉग एन) पूर्वजों की संख्या प्रभावित होती है, और पेड़ के घुमाव केवल रोटेशन में शामिल नोड्स की गिनती को प्रभावित करते हैं।

एक और सरल रणनीति [[ हैश टेबल ]] जैसी कुछ अवधारणाओं पर आधारित है। जब हम पहले से मानों की श्रेणी जानते हैं, तो हम उस श्रेणी को h उपअंतरालों में विभाजित कर सकते हैं और इन्हें h बकेट को असाइन कर सकते हैं। जब हम कोई तत्व डालते हैं, तो हम इसे उस अंतराल के अनुरूप बाल्टी में जोड़ते हैं जिसमें यह गिरता है। न्यूनतम या अधिकतम तत्व खोजने के लिए, हम पहली खाली बाल्टी के लिए शुरुआत या अंत से स्कैन करते हैं और उस बाल्टी में न्यूनतम या अधिकतम तत्व ढूंढते हैं। . सामान्य तौर पर, k वें तत्व को खोजने के लिए, हम प्रत्येक बकेट में तत्वों की संख्या की गिनती बनाए रखते हैं, फिर बकेट को बाएं से दाएं जोड़कर तब तक स्कैन करते हैं जब तक कि हमें वांछित तत्व वाली बकेट नहीं मिल जाती है, फिर अपेक्षित रैखिक-समय का उपयोग करें एल्गोरिदम उस बाल्टी में सही तत्व खोजने के लिए।