विभाजित और एल्गोरिथ्म जीतना

इस ट्यूटोरियल में, आप सीखेंगे कि एल्गोरिथ्म कैसे विभाजित और जीतता है। हम पुनरावर्ती समस्या को हल करने के लिए विभाजन और अन्य दृष्टिकोणों के मुकाबले दृष्टिकोण की तुलना भी करेंगे।

एक फूट डालो और जीत एल्गोरिथ्म द्वारा एक बड़ी समस्या को हल करने के लिए एक रणनीति है

1. समस्या को छोटी उप-समस्याओं में तोड़ना
2. उप-समस्याओं को हल करना, और
3. वांछित उत्पादन प्राप्त करने के लिए उनका संयोजन।

डिवाइड और एल्गोरिथ्म को जीतने के लिए, रिकर्सन का उपयोग किया जाता है। विभिन्न प्रोग्रामिंग भाषाओं में पुनरावृत्ति के बारे में जानें:

• जावा में पुनरावृत्ति
• पायथन में पुनरावृत्ति
• C ++ में पुनरावृत्ति

डिवाइड और एल्गोरिथ्म कैसे काम करते हैं?

इसमें शामिल हैं:

1. डिवाइड : दी गई समस्या को रिकर्सन का उपयोग करके उप-समस्याओं में विभाजित करें।
2. जीतना : छोटी उप-समस्याओं को पुन: हल करें। यदि उपप्रकार काफी छोटा है, तो इसे सीधे हल करें।
3. गठबंधन: उप-समस्याओं के समाधानों को मिलाएं जो वास्तविक समस्या को हल करने के लिए पुनरावर्ती प्रक्रिया का हिस्सा हैं।

एक उदाहरण की मदद से इस अवधारणा को समझते हैं।

यहां, हम डिवाइड और विजय दृष्टिकोण (यानी। मर्ज सॉर्ट) का उपयोग करके एक सरणी सॉर्ट करेंगे।

1. दिए गए एरे को होने दें: मर्ज के लिए एरियर
2. सरणी को दो हिस्सों में विभाजित करें। सरणी को दो उप-भागों में विभाजित करें
   फिर से, प्रत्येक तत्व को पुन: दो भागों में विभाजित करें जब तक कि आप व्यक्तिगत तत्व प्राप्त न करें। सरणी को छोटे सबपार्ट्स में विभाजित करें
3. अब, व्यक्तिगत तत्वों को क्रमबद्ध तरीके से संयोजित करें। यहाँ, जीतना और कदमों को साथ -साथ जोड़ना । सबपार्ट्स को मिलाएं

समय जटिलता

फूट डालो और जीतो एल्गोरिथ्म की जटिलता मास्टर प्रमेय का उपयोग करके गणना की जाती है।

T (n) = aT (n / b) + f (n), जहां, n = इनपुट का आकार a = प्रत्येक सबप्रॉब्लम के पुनरावर्तन n / b = आकार में उपप्रकारों की संख्या। सभी उपप्रकारों को एक ही आकार का माना जाता है। f (n) = पुनरावर्ती कॉल के बाहर किए गए कार्य की लागत, जिसमें समस्या को विभाजित करने की लागत और समाधानों को विलय करने की लागत शामिल है

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

मर्ज सॉर्ट के लिए, समीकरण के रूप में लिखा जा सकता है:

 T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) कहां, एक = 2 ​​(हर बार, 2 उपप्रकारों में एक समस्या को विभाजित किया जाता है) n / b = n / 2 (प्रत्येक उप समस्या का आकार इनपुट का आधा होता है) f (n) = समस्या को विभाजित करने के लिए लिया गया समय और उपप्रोलेम्स T (n / 2) = O (n लॉग एन) को मर्ज करने के लिए (इसे समझने के लिए, कृपया देखें) मास्टर प्रमेय।) अब, टी (एन) = 2 टी (एन लॉग एन) + ओ (एन) n ओ (एन लॉग इन) 

विभाजित और जीत बनाम गतिशील दृष्टिकोण

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

जब एक ही उपप्रकार कई बार हल नहीं होता है तो विभाजन और जीत के दृष्टिकोण का उपयोग करें। भविष्य में कई बार उपप्रोब्लेम का उपयोग करने पर डायनेमिक दृष्टिकोण का उपयोग करें।

इसे एक उदाहरण से समझते हैं। मान लीजिए कि हम फिबोनाची श्रृंखला खोजने की कोशिश कर रहे हैं। फिर,

फूट डालो और जीतो दृष्टिकोण:

 फ़ाइब (n) यदि n <2, 1 एलीस लौटाएँ, f (n - 1) + f (n -2) लौटाएँ 

गतिशील दृष्टिकोण:

 मेम = () फ़ाइब (एन) यदि एन मे मेम: रिटर्न मेम (एन) और, यदि एन <2, एफ = 1 और, एफ = एफ (एन - 1) + एफ (एन -2) मेम (एन) = एफ वापसी एफ 

एक गतिशील दृष्टिकोण में, मेम प्रत्येक उपप्रकार का परिणाम संग्रहीत करता है।

फूट डालो और जीतो एल्गोरिथ्म के लाभ

• भोली विधि का उपयोग करते हुए दो मैट्रिस के गुणन के लिए जटिलता हे (n ³ ) है, जबकि विभाजन और विजय दृष्टिकोण (यानी ^{स्ट्रैसन} मैट्रिक्स गुणन) का उपयोग ओ (एन ^2.8074 ) है। यह दृष्टिकोण अन्य समस्याओं को भी सरल करता है, जैसे कि हनोई का टॉवर।
• यह दृष्टिकोण मल्टीप्रोसेसिंग सिस्टम के लिए उपयुक्त है।
• यह मेमोरी कैश का कुशल उपयोग करता है।

डिवाइड एंड कॉनवेयर एप्लीकेशन

• द्विआधारी खोज
• मर्ज़ सॉर्ट
• जल्दी से सुलझाएं
• स्ट्रैसन की मैट्रिक्स गुणन
• करत्सुबा एल्गोरिथम