इस ट्यूटोरियल में, आप सीखेंगे कि मास्टर प्रमेय क्या है और इसका उपयोग पुनरावृत्ति संबंधों को हल करने के लिए कैसे किया जाता है।
मास्टर विधि फॉर्म के पुनरावृत्ति संबंधों को हल करने के लिए एक सूत्र है:
T (n) = aT (n / b) + f (n), जहां, n = इनपुट का आकार a = प्रत्येक सबप्रॉब्लम के पुनरावर्तन n / b = आकार में उपप्रकारों की संख्या। सभी उपप्रकारों को एक ही आकार का माना जाता है। f (n) = पुनरावर्ती कॉल के बाहर किए गए कार्य की लागत, जिसमें समस्या को विभाजित करने और समाधानों को विलय करने की लागत शामिल है यहां, एक ≧ 1 और b> 1 स्थिरांक हैं, और f (n) एक असमान रूप से सकारात्मक है समारोह।
एक asymptotically सकारात्मक फ़ंक्शन का मतलब है कि पर्याप्त रूप से बड़े मूल्य के लिए n, हमारे पास है f(n)> 0।
मास्टर प्रमेय का उपयोग पुनरावृत्ति संबंधों की समय जटिलता (विभाजित और एल्गोरिदम को जीतना) की सरल और त्वरित तरीके से गणना करने में किया जाता है।
मास्टर प्रमेय
यदि a ≧ 1और b> 1स्थिरांक हैं और f(n)एक विषम रूप से सकारात्मक कार्य है, तो एक पुनरावर्ती संबंध की समय जटिलता द्वारा दी गई है
T (n) = aT (n / b) + f (n) जहां, T (n) में निम्नलिखित स्पर्शोन्मुख सीमाएं हैं: 1. यदि f (n) = O (n log b a- ,), तो T (n) ) = N (एन लॉग बी ए )। 2. यदि f (n) = Θ (n log b a ), तो T (n) = Θ (n log b a * log b a )। 3. यदि f (n) = Ω (n log b a + then), तो T (n) = Θ (f (n))। constant> 0 एक स्थिर है।
उपरोक्त शर्तों में से प्रत्येक की व्याख्या की जा सकती है:
- यदि प्रत्येक स्तर पर उप-समस्याओं को हल करने की लागत एक निश्चित कारक से बढ़ जाती है, तो मूल्य
f(n)बहुपद से कम हो जाएगा । इस प्रकार, समय की जटिलता अंतिम स्तर की लागत से उत्पीड़ित होती है।nlogb anlogb a - यदि प्रत्येक स्तर पर उप-समस्या को हल करने की लागत लगभग बराबर है, तो
f(n)इच्छा का मूल्य होगा । इस प्रकार, समय की जटिलता स्तरों की कुल संख्या का समय होगा ।nlogb af(n)nlogb a * log n - यदि प्रत्येक स्तर पर उपप्रकारों को हल करने की लागत एक निश्चित कारक से कम हो जाती है, तो मूल्य
f(n)बहुपद के मुकाबले बड़ा हो जाएगा । इस प्रकार, समय की जटिलता से उत्पीड़न होता है ।nlogb af(n)
मास्टर प्रमेय का हल उदाहरण
T (n) = 3T (n / 2) + n2 यहाँ, a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1.58 <2। f (n) <n लॉग बी ए + ,, जहां,। एक स्थिरांक है। केस 3 का तात्पर्य यहाँ है। इस प्रकार, टी (एन) = एफ (एन) = n (एन 2 )
मास्टर प्रमेय सीमाएँ
यदि मास्टर प्रमेय का उपयोग नहीं किया जा सकता है:
- T (n) मोनोटोन नहीं है। उदा।
T(n) = sin n f(n)बहुपद नहीं है। उदा।f(n) = 2n- a स्थिर नहीं है। उदा।
a = 2n a < 1
