Divide and Conquer (विभाजन और विजय)
Divide and Conquer (विभाजन और विजय) एल्गोरिथमिक समस्याओं को हल करने की एक लोकप्रिय तकनीक है। हमने पहले भी कुछ तरीकों से एल्गोरिथ्मिक समस्याओं को हल करना देखा है। उदाहरण के लिए, greedy approach (ग्रीडी अप्रोच) प्रत्येक चरण में सबसे बेहतर (optimal) परिणाम चुनती है, जबकि dynamic programming (डायनेमिक प्रोग्रामिंग) पिछली स्थितियों के आधार पर वर्तमान स्थिति का निर्माण करती है। Divide and Conquer पद्धति में हम समस्या को छोटे-छोटे उप-समस्याओं में बाँटते हैं, उन्हें एक-एक करके हल करते हैं और अंतिम चरण में उनके परिणामों को मिलाकर मूल समस्या का समाधान करते हैं। इस तरह, हम समस्या को उप-समस्याओं में “divide” करके और फिर उन उप-समस्याओं के हल को जोड़कर पूरी समस्या पर “conquer” करते हैं।
Challenge (चुनौती)
कल्पना कीजिए कि आपके पास 512 संख्याएँ हैं और 512 विशेषीकृत कंप्यूटर (बहुत छोटे और खास कार्यों के लिए बने कंप्यूटर) उपलब्ध हैं, जो केवल दो संख्याओं में से अधिकतम मान निकालकर लौटा सकते हैं।
आप चाहते हैं कि इन 512 संख्याओं में से अधिकतम मान को यथासंभव कम समय में ढूँढ़ा जाए।
प्रत्येक कंप्यूटर दो संख्याएँ लेकर उनका अधिकतम मान 1 सेकंड में लौटा सकता है (हाँ, वे थोड़े धीमे हैं 🐌)। क्या आप कोई ऐसा एल्गोरिथ्म सोच सकते हैं जिससे इन सभी संख्याओं में से अधिकतम मान खोजने में कम से कम समय लगे?