पुनरावृत्ति को हल करने के लिए प्रतिस्थापन विधि

Question

सबसे पहले इस तरह के एक बुनियादी सवाल पूछने के लिए खेद है।

लेकिन मुझे पुनरावृत्ति को हल करने के लिए प्रतिस्थापन विधि को समझने में कठिनाइयों का सामना करना पड़ रहा है। मैं Algo.s -CLRS के परिचय का अनुसरण कर रहा हूं। चूंकि मैं पर्याप्त उदाहरण और अस्पष्टता नहीं ढूंढ पा रहा हूं, मुख्य चिंता है। विशेष रूप से प्रेरण चरण। पाठ्य पुस्तकों में हमें साबित करना होगा कि एफ (एन) का मतलब है एफ (एन + 1) लेकिन सीएलआरएस में यह कदम गुम है या हो सकता है मुझे उदाहरण नहीं मिल रहा है। कृपया चरणबद्ध तरीके से बताएं कि ओ (एन^2) पुनरावृत्ति समारोह टी (एन) = टी (एन -1) + एन

प्रतिस्थापन विधि का सामान्य कदम है जिसे मैं समझना चाहता हूं । यदि आप मजबूत गणितीय प्रेरण पर कुछ प्रकाश डाल सकते हैं और प्रतिस्थापन विधि पर सामग्री के लिंक प्रदान कर सकते हैं जो सहायक भी होंगे।

Answer 1

प्रतिस्थापन विधि में, T(k) के किसी भी अवसर को T(k-1) + k द्वारा प्रतिस्थापित करें, और इसे सामान्य रूप से करें।

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

sum of arithmetic progression से

, आप प्राप्त कर सकते हैं कि टी (एन) O(n^2) में है।

ध्यान दें कि प्रतिस्थापन विधि आमतौर पर जटिलता के बारे में अंतर्ज्ञान प्राप्त करने के लिए उपयोग की जाती है, औपचारिक रूप से साबित करने के लिए - आपको शायद एक अलग उपकरण की आवश्यकता होगी - जैसे कि mathematical induction।

Claim: T(n) <= n^2 
Base: T(1) = 1 <= 1^2 
Hypothesis: the claim is true for each `k < n` for some `n`. 
T(n) = T(n-1) + n <= (hypothesis) (n-1)^2 + n = n^2-2n + 1 < n^2 (for n > 1) 

:

औपचारिक प्रमाण ऐसा ही कुछ जाना होगा