मास्टर प्रमेय वास्तव में कब लागू किया जा सकता है?

Question

मैं इस पर काफी निराश हूं।

CLRS में 3 संस्करण, पेज 95 (अध्याय 4.5), यह कहा गया है कि

T(n) = 2T(n/2) + n lg n

मास्टर प्रमेय के साथ हल नहीं किया जा सकता अंतर

f(n)/n^(log_b(a)) = (n lg n)/n^1 = lg n

है क्योंकि पुनरावृत्ति

की तरह बहुपद नहीं।

लेकिन फिर मैं this जैसे पृष्ठों पर आया हूं, जहां पृष्ठ के निचले हिस्से में, यह सटीक वही पुनरावृत्ति का उल्लेख करता है और कहता है कि इसे मास्टर प्रमेय के साथ हल किया जा सकता है क्योंकि यह "विस्तारित केस 2" में भी पड़ता है हालांकि अंतर गैर-बहुपद है। यह n lg^2 n बन जाता है (f(n) पर लॉग कारक को एक से बढ़ाकर)।

तब मैं this तरह पृष्ठों के पार चलो जहां उदाहरण में (ई) विस्तारित केस 2 (पुनरावृत्ति T(n) = 4T(n/2) + n^2 lg n है) का एक स्पष्ट आवेदन की तरह लगता है, लेकिन फिर समाधान n^2 log^2 n नहीं है, बल्कि n^2 log n! क्या मैं गलत हूं या पेपर गलत है?

क्या कोई भी विरोधाभास को साफ़ कर सकता है और इसे बिल्कुल स्पष्ट कर सकता है जब मास्टर प्रमेय का उपयोग किया जा सकता है और जब यह नहीं हो सकता है? बहुपद-अंतर जांच मामले कब होता है, और यह कब नहीं होता? विस्तारित मामला 2 उपयोग योग्य है, या क्या यह वास्तव में कुछ का उल्लंघन करता है?

संपादित करें:

मैं सुलझाने की कोशिश की पुनरावृत्ति (ई) सीधे दूसरे पेपर से और मैं:

T(n) = n^2 lg^2(n)/2 + n^2 lg(n)/2

यह नहीं बड़ा थीटा n^2 lg^2 n है?

Answer 1

पुस्तक में कहा गया है कि यह Case 3 का उपयोग कर हल नहीं किया जा सकता है:

यह उचित रूप प्रतीत होता है, भले ही: ... आपने गलती से सोच सकते हैं कि इस मामले 3

---

आवेदन करना चाहिए

हालांकि, इस पुनरावृत्ति सूत्र मास्टर प्रमेय, मामले का उपयोग कर हल किया जा सकता 2.

T(n) = 2T(n/2) + nlgn: 

हम परिभाषित:

a = 2, b = 2, f(n) = nlgn 

Master theorem case 2 का उपयोग करना:

c = log_2(2) = 1 
k = 1 

और f(n)Theta(nlogn) में वास्तव में है।

तो, मास्टर प्रमेय मामले 2 करने के लिए सभी शर्तें लागू होती हैं, और हम यह मान सकते हैं:

T(n) कम Theta(n^c * log(n)^(k+1)) = Theta(n*log(n)^2)

---

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