एल्गोरिदम क्यों विभाजित और जीतते हैं अक्सर ब्रूट फोर्स की तुलना में तेज़ी से दौड़ते हैं? उदाहरण के लिए, अंक की निकटतम जोड़ी ढूंढने के लिए। मुझे पता है कि आप मुझे गणितीय सबूत दिखा सकते हैं। लेकिन सहजता से, ऐसा क्यों होता है? जादू?एल्गोरिदम क्यों विभाजित और जीतते हैं अक्सर ब्रूट फोर्स की तुलना में तेज़ी से दौड़ते हैं?
सैद्धांतिक रूप से, क्या यह सच है कि "विभाजन और विजय हमेशा बलपूर्वक बल से बेहतर है"? यदि यह नहीं है, तो क्या कोई counterexample है?
आपके पहले प्रश्न के लिए, विभाजन और जीत के पीछे अंतर्ज्ञान यह है कि कई समस्याओं में जो काम करना है, वह इनपुट की कुछ संयोजी संपत्ति पर आधारित है जो रैखिक रूप से अधिक पैमाने पर है।
उदाहरण के लिए, अंक की सबसे नज़दीकी जोड़ी में, ब्रूट-फोर्स उत्तर का रनटाइम इस तथ्य से निर्धारित होता है कि आपको सभी ओ (एन) बिंदुओं के संभावित जोड़े को देखना होगा।
यदि आप कुछ ऐसा करते हैं जो चतुर्भुज रूप से बढ़ता है और इसे दो टुकड़ों में काटता है, जिनमें से प्रत्येक आधा आकार पहले होता है, तो प्रत्येक आधे में समस्या को हल करने के लिए प्रारंभिक समय में से एक चौथाई लेता है, इसलिए दोनों में समस्या को हल करना हिस्सों में ब्रूट फोर्स समाधान के लिए लगभग आधे समय की आवश्यकता होती है। इसे चार टुकड़ों में काटकर उस समय का एक चौथाई हिस्सा ले जाएगा, इसे आठ टुकड़ों में आठवें समय में काट दिया जाएगा।
रिकर्सिव संस्करण इस मामले में तेजी से समाप्त होता है क्योंकि प्रत्येक चरण में, हम बहुत कुछ करने से बचते हैं यह सुनिश्चित करके तत्वों के जोड़े से निपटने से काम करें कि बहुत सारे जोड़े नहीं हैं जिन्हें हमें वास्तव में जांचना है। अधिकतर एल्गोरिदम जिनमें विभाजित होता है और समाधान जीतता है, इसी कारण से तेज़ी से समाप्त होता है।
आपके दूसरे प्रश्न के लिए, नहीं, एल्गोरिदम को विभाजित और जीतना ब्रूट-बल एल्गोरिदम से आवश्यक नहीं है। सरणी में अधिकतम मान खोजने की समस्या पर विचार करें। ब्रूट-फोर्स एल्गोरिदम ओ (एन) समय लेता है और ओ (1) स्पेस का उपयोग करता है क्योंकि यह डेटा पर रैखिक स्कैन करता है। विभाजित और जीत एल्गोरिदम यहां दिया गया है:
यह रूप में अच्छी तरह समय हे (एन) लेता है, लेकिन ढेर अंतरिक्ष के लिए हे (लॉग एन) स्मृति का उपयोग करता है। यह वास्तव में सरल रैखिक एल्गोरिदम से भी बदतर है।
एक और उदाहरण के रूप में, maximum single-sell profit problem में विभाजित और जीत समाधान है, लेकिन अनुकूलित गतिशील प्रोग्रामिंग समाधान दोनों समय और स्मृति में तेज़ है।
आशा है कि इससे मदद मिलती है!
मैं आपको एल्गोरिदम डिजाइन के अध्याय 5 के माध्यम से पढ़ने की सलाह देता हूं, यह विभाजन को अच्छी तरह से विभाजित करता है और जीतता है।
सहजता से, किसी समस्या के लिए, यदि आप इसे मूल रूप से समान पैटर्न के साथ दो उप-समस्याओं में विभाजित कर सकते हैं, और अंतिम परिणाम में दो उप-समस्याओं के परिणामों को मर्ज करने की जटिलता किसी भी तरह छोटी है , तो यह क्रूर बल द्वारा संरेखण पूर्ण समस्या को हल करने से तेज़ है।
रूप एल्गोरिथ्म में कहा डिजाइन, आप वास्तव में समय के संदर्भ में विभाजन और जीत से बहुत ज्यादा हासिल नहीं कर सकते, सामान्य आप केवल बहुपद कम करने के लिए उच्च बहुपद समय जटिलता को कम कर सकते हैं (उदाहरण के लिए हे से (एन^3) से ओ (एन^2)), लेकिन शायद ही घातीय से बहुपद तक (उदाहरण के लिए ओ (2^एन) से ओ (एन^3))।
मुझे लगता है कि आप विभाजित और जीत से प्राप्त कर सकते हैं सबसे अधिक समस्या हल करने के लिए मानसिकता है। मूल बड़ी समस्या को छोटी और आसान उप-समस्याओं को तोड़ना हमेशा अच्छा प्रयास है। भले ही आपको बेहतर चलने का समय न मिले, फिर भी यह आपको समस्या के बारे में सोचने में मदद करता है।
केक को 16 टुकड़ों में साझा करने के लिए, पहला समाधान केक के 1/16 को काटने की कोशिश करना है और ... मुश्किल। एक और समाधान केक को 2 में कटौती करना है, फिर 2 में फिर से, फिर 1/4 में से प्रत्येक, और 1/8 में से प्रत्येक में कटौती करना है। –