मैं इसके लिए बिल्कुल नया हूं इसलिए स्टेम द्वारा एक कदम बहुत मदद करेगा, धन्यवाद।

1
dan 8 अप्रैल 2020, 17:47

1 उत्तर

सबसे बढ़िया उत्तर

सबसे पहले, आप पुनरावृत्ति विधि से शुरू कर सकते हैं यह समझने के लिए कि यह कैसे व्यवहार करता है।

T(n) = 2T(n-1) + 1 = 
     = 2*(2T(n-2) + 1) + 1 = 4T(n-2) + 3
     = 4(2T(n-3) + 1) + 3 = 8T(n-3) + 7
     = 8*(2T(n-4) + 1) + 7 = 16T(n-4) + 15
     = 16*(2T(n-5) + 1) + 15 = 32T(n-5) + 31

अब, जब हम व्यवहार को समझते हैं, तो हम बता सकते हैं

T(n) = 2^i * T(n-i) + (2^i - 1)

अब, हमें बेस क्लॉज (जो प्रश्न में नहीं दिया गया है) का उपयोग करने और i=n के लिए एक्सट्रेक्ट करने की आवश्यकता है। उदाहरण के लिए, यदि T(0) = 0:

T(n) = 2^n * T(0) + (2^n - 1) = 2^n - 1

स्पर्शोन्मुख जटिलता की गणना करते समय यह O(2^n) में होता है।

नोट: पुनरावृत्ति विधि अच्छी और पालन करने में आसान है - लेकिन यह औपचारिक प्रमाण नहीं है। औपचारिक रूप से जटिलता को साबित करने के लिए, आपको एक अन्य उपकरण की आवश्यकता होगी, जैसे कि प्रेरण।

1
amit 9 अप्रैल 2020, 09:30