हम आम तौर पर विभाजित करने और एल्गोरिदम जीतने में दो हिस्सों में क्यों विभाजित होते हैं?

Question

मर्ज सॉर्ट में हम हल करते समय दो भागों में विभाजित होते हैं। हमने इसे 3 या अधिक हिस्सों में क्यों विभाजित नहीं किया? इसी प्रकार कई विभाजनों में और समस्याओं को जीतने में मैंने देखा है कि एक व्यक्ति दो हिस्सों में विभाजित होता है। 3 या अधिक हिस्सों क्यों नहीं? समाधान/जटिलता पर इसका क्या असर होगा?

Answer 1

आप कर सकते हैं। लेकिन इससे कोई फर्क नहीं पड़ता। विभाजितlog की जटिलता (चलो इसके बारे में बहुत आम बात करते हैं)।

सटीक होना आप log_2 मिलता बल्कि इसलिए निरंतर कारकों जटिलता विश्लेषण में (बिग-ओ-संकेतन, Wikipedia) कोई बात नहीं यह log का सामान्यीकरण है। एक अधिक विशिष्ट स्तर पर

log_a(x) = log_b(x) * (1/log_b(a)) 

जब दो हिस्सों में विभाजित करने तुम कहीं एक निरंतर कारक 2 की मिल: और तुम हमेशा केवल एक निरंतर कारक का उपयोग करके एक एक log_b में log_a बदल सकता है। यदि अब आप 4 में विभाजित हैं तो आप 2 को प्रतिस्थापित करेंगे, लेकिन वास्तव में यह किसी भी मामले में वास्तव में एक स्थिर कारक परिवर्तन है।

---

असल में जब समानांतर या वितरित प्रोग्रामिंग का उपयोग कर दो से अधिक भागों अक्सर अभ्यास में किया जाता है में विभाजित।

लेकिन के अलावा विभाजित करें और जीतें एक तकनीक है जो मनुष्यों के लिए समस्याओं को समझने में आसान बनाती है। आप एक कठिन समस्या को छोटी आसान समस्याओं में बदल देते हैं।

अधिकांश बार का एकमात्र लाभ को विभाजित और जीतने के लिए यह समझना अधिक आसान होगा।

Answer 2

आप कभी-कभी इसे लागू कर सकते हैं। हालांकि एल्गोरिदम की सबसे बुरी स्थिति जटिलता अभी भी big-O नोटेशन के संबंध में समान होगी।

स्पष्ट रूप से विभाजित करें और एल्गोरिदम पर विजय प्राप्त करें प्रकृति द्वारा पुनरावर्ती हैं और इसलिए जब भी समस्या एक मामूली स्थिति में होती है तब तक आप तब तक विभाजित हो जाएंगे (आधारभूत मामला - उदाहरण के लिए दो संख्याओं को सॉर्ट करना)। आप जल्द ही इस मामले में पहुंच सकते हैं लेकिन वहां पहुंचने के लिए और अधिक काम कर सकते हैं, वे सबसे खराब केस प्रदर्शन में समान होंगे। https://softwareengineering.stackexchange.com/questions/197107/divide-and-conquer-algorithms-why-not-split-in-more-parts-than-two

आशा इस मदद करता है:

कृपया निम्नलिखित के रूप में इस सवाल से पहले ऑनलाइन कहा गया है और लोगों की तुलना में मैं कर सकता बेहतर और अधिक पूरा जवाब प्रदान नहीं की है!

ऊपर के लिंक से

इसके अलावा, मैं particulaly intesting पाया जो:

"दूसरी ओर, कुछ पेड़-ish डेटा संरचना एक उच्च शाखाओं में कारक (3 से काफी बड़ा है, अक्सर 32 या अधिक प्रयोग करते हैं), हालांकि आमतौर पर अन्य कारणों से।यह स्मृति पदानुक्रम के उपयोग को बेहतर बनाता है: रैम में संग्रहित डाटा संरचनाओं कैश का बेहतर उपयोग कर, डिस्क पर संग्रहीत डेटा संरचनाओं की आवश्यकता कम HDD- पढ़ता> रैम "

Answer 3

3 या अधिक भागों में समस्या डिवाइडिंग। आमतौर पर असुविधाजनक होता है और इसका एल्गोरिदमिक जटिलता पर कोई असर नहीं पड़ता है। यह आमतौर पर वास्तविक दुनिया के प्रदर्शन को नकारात्मक रूप से प्रभावित करेगा क्योंकि अधिक जटिल कोड सरल सुव्यवस्थित कोड की तुलना में अभ्यास में कम कुशल होता है। लेकिन यह हमेशा ऐसा नहीं होता है।

वहां कुछ व्यावहारिक डी & सी एल्गोरिदम हैं जो समस्या को दो भागों में विभाजित करते हैं क्योंकि ऐसा करने के लिए फायदेमंद है। दोहरी-पिवट Quicksort एक उदाहरण है। नियमित क्विकॉर्ट की तुलना में यह कुछ हद तक तेज (स्थिर कारक द्वारा) होता है।

Answer 4

क्योंकि समय जटिलता व्यापारिक बनाम कार्यान्वयन जटिलता।

इसे एक उदाहरण के माध्यम से समझें और कैसे "विभाजित" काम करता है। आइए कहें कि हमारे पास n तत्व हैं, जिन पर हमें कुछ एल्गोरिदम करना है। चलिए रैखिक और लॉग जटिलताओं में अंतर देखते हैं।

कहो, उदाहरण के लिए, n~10^6 के लिए है, तो डेटा सेट पर किसी भी रेखीय कार्य समय है, जहां t समय एक डेटा बिंदु को संसाधित करने पर खर्च किया जाता है के बारे में 10^6 * t इकाइयों ले जाएगा। एक विभाजन और जीत दृष्टिकोण के लिए, यह समय के log(10^6) * t इकाइयों को कम कर देता है। यह लॉग के आधार के मूल्य पर भिन्न होता है, जो एल्गोरिदम को विभाजित और जीतने में, केवल "भागों" की संख्या है जिसे हम अपने डेटासेट को विभाजित करते हैं।

विभिन्न अड्डों के लिए लॉग के लिए संख्याओं को देखें।

base    log 10^6 in base 

    2     20 
    3     12.6 
    4     10 

आदि

तो, हम देख सकते हैं कि अधिक भागों में विभाजित वास्तव में से समय में कमी नहीं है कि ज्यादा है, क्योंकि डेटा सेट में 10 की तरह^6 तत्वों के लिए, आप कर 20 पुनरावृत्तियों या 12 या 10, इससे कोई फर्क नहीं पड़ता है, लेकिन इसकी तुलना 10^6 (ओ (एन) -complex) से करें, वहां आप इसे देखते हैं।

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

साथ ही, जैसा कि अन्य ने अपने उत्तरों में समझाया है, लॉग का आधार समय जटिलता के लिए सैद्धांतिक बड़े-ओ कारक को नहीं बदलता है।