समझौता मास्टर प्रमेय

Question

जेनेरिक रूप: T(n) = aT(n/b) + f(n)

तो मैं n^logb तुलना चाहिए (क) च (एन)

अगर n^logba>f(n)मामले 1 और T(n)=Θ(n^logb(a))

अगर n^logba है साथ < f(n)केस 2 और T(n)=Θ((n^logb(a))(logb(a)))

क्या यह सही है? या मैंने कुछ गलत समझा?

और मामले 3 के बारे में क्या? जब यह लागू होता है?

Answer 1

मुझे लगता है कि आपने इसे गलत समझा है। यदि n^Logba> च (एन) मामले 1 और टी (एन) = Θ है (एन^logb (एक))

यहाँ आप च (एन) के बारे में चिंतित नहीं होना चाहिए परिणाम के रूप में मिल रहा है टी (एन) = Θ (एन^logb (ए) है)। एफ (एन) टी (एन) का हिस्सा है .. और यदि आपको परिणाम टी (एन) मिलता है तो उस मान में एफ (एन) शामिल होगा। तो, उस भाग पर विचार करने की कोई आवश्यकता नहीं है।

अगर आप स्पष्ट नहीं हैं तो मुझे बताएं।

Answer 2

नोट: मैं समझता हूं कि इस प्रश्न का उत्तर देने में बहुत देर हो चुकी है। मैं तो बस इसे यहाँ भविष्य की पीढ़ियों :)

मास्टर प्रमेय के लिए डाल रहा हूँ सुलझाने recurrences

recurrences एक विभाजन में होते हैं और जटिल समस्याओं के हल के लिए रणनीति को जीत के लिए।

यह क्या हल करता है?

• यह प्रपत्र टी (एन) = पर (एन/बी) + F (n) की पुनरावृत्ति को हल करती है।
• 1 से अधिक या बराबर होना चाहिए। जिसका अर्थ यह है कि समस्या कम से कम एक छोटी उप समस्या में कम हो जाती है। कम से कम एक रिकर्सन की आवश्यकता है
• बी 1 से अधिक होना चाहिए। प्रत्येक पुनरावर्तन पर जिसका मतलब है, समस्या का आकार एक छोटे आकार में कम हो गया है। यदि बी 1 से अधिक नहीं है, तो इसका मतलब है कि हमारी उप समस्याएं छोटे आकार की नहीं हैं।
• एफ (एन) एन के अपेक्षाकृत बड़े मूल्यों के लिए सकारात्मक होना चाहिए।

पर विचार करें नीचे दी गई छवि:

चलें कहते हैं कि हम आकार n की एक समस्या को हल किया जाना है। प्रत्येक चरण में समस्या को उप-समस्याओं में विभाजित किया जा सकता है और प्रत्येक उप समस्या छोटे आकार की होती है, जहां आकार बी के कारक द्वारा कम किया जाता है।

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

इसके अलावा, उपर्युक्त चित्र दिखाता है कि अंत में जब हमने कई बार समस्याओं को विभाजित किया है, तो प्रत्येक उप समस्या इतनी छोटी होगी कि इसे निरंतर समय में हल किया जा सके।

नीचे व्युत्पत्ति के लिए आधार ख को लॉग पर विचार

हम कहते हैं कि एच पेड़ की ऊंचाई, तो एच = logn में है। पत्तियों की संख्या = एक^लॉगन।

• कुल काम स्तर 1 पर किया: च (एन)
• कुल काम लेवल 2 पर किया: एक * च (एन/ख)
• कुल काम स्तर 1 पर किया: एक * एक * च (एन/बी 2)
• अंतिम स्तर पर किए गए कुल कार्य: पत्तियों की संख्या * θ (1)। यह n^loga के बराबर मास्टर प्रमेय

  प्रकरण की

तीन मामलों 1: अब हम मान लेते हैं कि आपरेशन की लागत प्रत्येक स्तर पर और से एक महत्वपूर्ण कारक द्वारा बढ़ती जा रही है चलो समय हम पत्ती के स्तर तक पहुंचते हैं एफ (एन) का मान मूल्य n^loga से बहुपद रूप से छोटा हो जाता है। फिर कुल चलने का समय अंतिम स्तर की लागत से काफी प्रभावित होगा। इसलिए टी (एन) = θ (एन^loga)

केस 2: हमें लगता है कि प्रत्येक स्तर पर संचालन की लागत लगभग बराबर में है। उस मामले में एफ (एन) लगभग n^loga के बराबर है। इसलिए, कुल चलने का समय एफ (एन) स्तरों की कुल संख्या होगी। टी (एन) = θ (एन^लॉगा * लॉगन) जहां के हो सकता है> = 0। कहाँ logn कश्मीर के लिए एक पेड़> = 0

प्रकरण की ऊंचाई होगा 3: हमें लगता है कि प्रत्येक स्तर पर संचालन की लागत प्रत्येक स्तर पर और समय से एक महत्वपूर्ण कारक द्वारा कम हो रही है चलो हम पत्ती के स्तर तक पहुंचें एफ (एन) के मूल्य मूल्य n^loga से बहुपद रूप से बड़े हो जाते हैं। फिर कुल चलने का समय पहले स्तर की लागत से काफी प्रभावित होगा। इसलिए टी (एन) = θ (एफ (एन))

यदि आप अधिक विस्तृत पढ़ने में रुचि रखते हैं और शायद अभ्यास करने के लिए कुछ उदाहरण हैं। आप हमेशा इसके लिए मेरे ब्लॉग एंट्री पर जा सकते हैं। Master Method to Solve Recurrences