निम्नलिखित पुनरावृत्ति को कैसे हल करें?

Question

मैं मास्टर प्रमेय, रिकर्सन पेड़ और प्रतिस्थापन विधि के बाहर पुनरावृत्ति सुलझाने की तकनीक से परिचित नहीं हूं। मैं अनुमान लगा रहा हूँ कि एक बड़ा-ओ बाध्य निम्नलिखित पुनरावृत्ति को सुलझाने उन तरीकों में से एक का उपयोग नहीं करता है:

T(n) = T(n-1) + 2T(n-2) + 1 

Answer 1

हम प्रतिस्थापन U(n) = T(n) + 1/2 कर सकते हैं और फिर एक पुनरावृत्ति

U(n) = T(n) + 1/2 
    = T(n-1) + 2T(n-2) + 1 + 1/2 
    = T(n-1) + 1/2 + 2(T(n-2) + 1/2) 
    = U(n-1) + 2U(n-2), 

जो एक है मिल थोड़ा जादू लेकिन, जैसे templatetypedef उल्लेख करता है, जादू को विनाशक विधि के साथ बनाया जा सकता है। अब हमें रैखिक सजातीय पुनरावृत्ति को हल करना होगा। (x+1)(x-2) के रूप में विशेषता बहुपद x^2 - x - 2 कारक, इसलिए समाधान U(n) = a(-1)^n + b2^n हैं जहां a और b कोई स्थिरांक हैं। समकक्ष, T(n) = a(-1)^n + b2^n - 1/2, जो विशेष मामलों को छोड़कर Theta(2^n) है।

Answer 2

यह प्रत्यावर्तन non-homogeneous linear recurrence. कहा जाता है और यह एक सजातीय एक के लिए परिवर्तित करके हल किया जाता है:

T(n) = T(n-1) + 2T(n-2) + 1 
T(n+1) = T(n) + 2T(n-1) + 1 

2 से घटाने पर 1 और आधार बदल रहा है, तो आप T(n) = 2 T(n-1) + T(n-2) - 2 T(n-3) मिलता है। इसी विशेषता समीकरण है:

x^3 - 2x^2 - x + 2 = 0 

जो समाधान x = {-1, 1, 2} है। इसका मतलब है कि रिकर्सन इस तरह दिखता है:

c1 * (-1)^n + c2 * 2^n + c3 * 1^n = c1 * 2^n + c2 (-1)^n + c3 

जहां ये सभी स्थिरांक टी (0) और टी (1) को जान सकते हैं। आपके जटिलता विश्लेषण के लिए यह स्पष्ट है कि यह घातीय O(2^n) है।