मुझे आश्चर्य है कि विभाजित करने और जीतने की तकनीक हमेशा एक ही प्रकार के उपप्रोबल में समस्या को विभाजित करती है? उसी प्रकार से, मेरा मतलब है कि कोई इसे रिकर्सन के साथ फ़ंक्शन का उपयोग करके कार्यान्वित कर सकता है। विभाजित करके हमेशा जीत और जीत सकते हैं?विभाजित करें और जीतें और रिकर्सन
धन्यवाद!
"हमेशा" एक डरावना शब्द है, लेकिन मैं एक विभाजन और जीत की स्थिति के बारे में नहीं सोच सकता जिसमें आप रिकर्सन का उपयोग नहीं कर सके। यह परिभाषा है कि विभाजित और जीत प्रारंभिक समस्या के समान रूप के उपप्रणाली बनाता है - कुछ उप-मामले तक पहुंचने तक इन सबप्रोबम्स लगातार टूट जाते हैं, और विभाजन की संख्या इनपुट के आकार से संबंधित होती है। इस तरह की समस्या के लिए रिकर्सन एक प्राकृतिक पसंद है।
अधिक अच्छी जानकारी के लिए Wikipedia article देखें।
एक विभाजन-और-जीत एल्गोरिदम परिभाषा द्वारा है जिसे रिकर्सन द्वारा हल किया जा सकता है। तो उत्तर हां है।
आमतौर पर, हाँ! Merge sort इसका एक उदाहरण है। यहां एक animated version है।
हां। एल्गोरिदमिक तकनीक को विभाजित और जीतने में हम दी गई बड़ी समस्या को छोटी उप-समस्याओं में विभाजित करते हैं। ये छोटी उप-समस्याएं बड़ी समस्या के समान होनी चाहिए, सिवाय इसके कि ये आकार में छोटे हैं।
उदाहरण के लिए, आकार एन की सरणी को सॉर्ट करने की समस्या आकार एन/2 की सरणी को सॉर्ट करने की समस्या से अलग नहीं है। सिवाय इसके कि बाद की समस्या का आकार पूर्व की तुलना में छोटा है।
यदि छोटी उप-समस्या बड़े के समान नहीं है, तो विभाजन और जीत तकनीक को बड़ी समस्या को हल करने के लिए उपयोग नहीं किया जा सकता है। दूसरे शब्दों में, किसी दिए गए समस्या को विभाजित करके तकनीक को जीतने के लिए हल किया जा सकता है, अगर केवल बड़ी समस्या को छोटी उप समस्याओं में विभाजित किया जा सकता है जो कि बड़ी समस्या के समान हैं।
रिकर्सन एक प्रोग्रामिंग विधि है जहां आप स्वयं के संदर्भ में एक फ़ंक्शन को परिभाषित करते हैं। फ़ंक्शन आमतौर पर थोड़ा संशोधित पैरामीटर (अभिसरण करने के लिए) के साथ स्वयं को कॉल करता है।
मर्ज सॉर्ट एल्गोरिदम की जांच इस प्रश्न के लिए पर्याप्त होगी। विलय और जीत (भी रिकर्सन) के साथ मर्ज सॉर्ट एल्गोरिदम के कार्यान्वयन को समझने के बाद आप देखेंगे कि यह बिना रिकर्सन के कितना मुश्किल होगा।
असल में सबसे महत्वपूर्ण बात यह है कि एल्गोरिदम की जटिलता है जो बड़े-ओह नोटेशन और विलय प्रकार के लिए nlogn के साथ व्यक्त की जाती है।
विलय के लिए exapmle के लिए एक और संस्करण है जिसे नीचे-अप मर्ज सॉर्ट कहा जाता है। यह इसका सरल और गैर-पुनरावर्ती संस्करण है।
यह सामान्य प्रणालियों पर रिकर्सिव, टॉप-डाउन विलयोर्ट से लगभग 10% धीमी है। आप अधिक जानकारी के लिए निम्नलिखित लिंक का उल्लेख कर सकते हैं। यह तीसरे व्याख्यान में अच्छी तरह से समझाया गया है।