विभाजन और विजय (Divide and Conquer)

विभाजन और विजय एक एल्गोरिथम डिज़ाइन प्रतिमान है जो किसी समस्या को उसी प्रकार की छोटी उप-समस्याओं में विभाजित करके, उन्हें पुनरावर्ती रूप से हल करके, और उनके समाधानों को मूल समस्या के समाधान में संयोजित करके हल करता है।

Definition

एक विभाजन-और-विजय एल्गोरिथम पुनरावर्ती रूप से एक समस्या को दो या अधिक उप-समस्याओं में विभाजित करता है जो एक ही या संबंधित प्रकार की होती हैं जब तक कि उप-समस्याएं सीधे हल करने के लिए पर्याप्त सरल न हों, फिर मूल समस्या का उत्तर उत्पन्न करने के लिए उप-समस्या समाधानों को संयोजित करता है।

Scope

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

Core questions

• किसी समस्या को कैसे विघटित किया जाता है ताकि उप-समस्याएं स्वतंत्र और एक ही रूप की हों?
• संयोजन चरण में क्या कार्य किया जाता है, और यह कुल लागत को कैसे प्रभावित करता है?
• परिणामी पुनरावृत्तियों को स्पर्शोन्मुख चलने के समय प्राप्त करने के लिए कैसे हल किया जाता है?
• विभाजन-और-विजय एक सीधी पुनरावृत्ति दृष्टिकोण को कब मात देता है?

Key concepts

• विभाजित करें, जीतें, संयोजित करें
• पुनरावृत्ति संबंध
• मास्टर प्रमेय
• मर्जसॉर्ट
• क्विकसॉर्ट
• बाइनरी सर्च
• करात्सुबा गुणन
• स्ट्रासेन का मैट्रिक्स गुणन

Key theories

पुनरावृत्तियों के लिए मास्टर प्रमेय

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

अपघटन के माध्यम से सबक्वाड्रेटिक गुणन

ऑपरेंड को पुनरावर्ती रूप से विभाजित करना और पुनरावर्ती गुणा की संख्या को कम करना (जैसा कि करात्सुबा गुणन और स्ट्रासेन के मैट्रिक्स गुणन में है) भोली द्विघात और घन विधियों की तुलना में स्पर्शोन्मुख रूप से तेज़ एल्गोरिदम उत्पन्न करता है।

Clinical relevance

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

History

मर्जसॉर्ट का श्रेय जॉन वॉन न्यूमैन (1945) को दिया जाता है। सी. ए. आर. होरे ने 1962 में क्विकसॉर्ट प्रकाशित किया। करात्सुबा के 1960 के सबक्वाड्रेटिक गुणन और स्ट्रासेन के 1969 के मैट्रिक्स-गुणन एल्गोरिथम ने प्रदर्शित किया कि पुनरावर्ती अपघटन शास्त्रीय सीमाओं को पार कर सकता है, जिससे विभाजन-और-विजय को एक मूलभूत प्रतिमान के रूप में स्थापित करने में मदद मिली।

Key figures

• C. A. R. Hoare
• John von Neumann
• Anatoly Karatsuba
• Volker Strassen

Seminal works

• hoare1962
• cormen2009

Frequently asked questions

मर्जसॉर्ट O(n log n) क्यों है?

मर्जसॉर्ट सरणी को दो हिस्सों में विभाजित करता है (पुनरावृत्ति के log n स्तर) और प्रत्येक स्तर पर सभी तत्वों में रैखिक-समय विलय करता है, जिससे पुनरावृत्ति T(n) = 2T(n/2) + O(n) प्राप्त होती है, जिसे मास्टर प्रमेय O(n log n) के रूप में हल करता है।

क्या क्विकसॉर्ट एक विभाजन-और-विजय एल्गोरिथम है, भले ही इसमें कोई स्पष्ट संयोजन चरण न हो?

हाँ। क्विकसॉर्ट एक धुरी के चारों ओर विभाजन के माध्यम से विभाजन चरण में अपना मुख्य कार्य करता है; एक बार जब दो विभाजन पुनरावर्ती रूप से सॉर्ट हो जाते हैं, तो किसी संयोजन कार्य की आवश्यकता नहीं होती है। प्रतिमान तीनों चरणों में से किसी में भी अधिकांश प्रयास को गिरने की अनुमति देता है।