आसान: टी (एन) = टी (एन -1) + एन को इटरेशन विधि

Question

द्वारा हल करें कृपया कोई मेरी मदद कर सकता है?

इसे हल करने के लिए पुनरावृत्ति विधि का उपयोग करें। टी (एन) = टी (एन -1) + एन

चरणों की व्याख्या की सराहना की जाएगी।

Answer 1

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

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

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

और इतने पर आप (n- टी (n-1) और टी का मूल्य स्थानापन्न कर सकते हैं 2) टी (एन) में पैटर्न का एक सामान्य विचार प्राप्त करने के लिए।

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


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

T(n) = T(n-k) +kn - k(k-1)/2 

आधार मामले के लिए:

n - k =1 so we can get T(1) 

k = n - 1

ऊपर

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

कौन सा आप देख सकते हैं में स्थानापन्न आदेश के है n^2

Answer 2

इसका विस्तार करें!

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

और इतने पर, जब तक

T(n) = 1 + 2 + ... + n = n(n+1)/2 [= O(n^2)] 

बशर्ते कि T(1) = 1

Answer 3

छद्म में कोड पुनरावृत्ति का उपयोग कर:

function T(n) { 
    int result = 0; 

    for (i in 1 ... n) { 
     result = result + i; 
    } 

    return result; 
}  

Answer 4

आसान विधि:

T (n) = T (n - 1) + (n)-----------(1) 
//now submit T(n-1)=t(n) 

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

now submit (2) in (1) you will get 
i.e T(n)=[T(n-2)+n-1]+(n) 
T(n)=T(n-2)+2n-1 //simplified--------------(3) 

now, T(n-2)=t(n) 
T(n-2)=T((n-2)-2)+[2(n-2)-1] 
    T(n-2)=T(n-4)+2n-5---------------(4) 
    now submit (4) in (2) you will get 
    i.e T(n)=[T(n-4)+2n-5]+(2n-1) 
    T(n)=T(n-4)+4n-6 //simplified 
    ............ 
T(n)=T(n-k)+kn-6 
    **Based on General form T(n)=T(n-k)+k, ** 
    now, assume n-k=1 we know T(1)=1 
      k=n-1 

    T(n)=T(n-(n-1))+(n-1)n-6 
    T(n)=T(1)+n^2-n-10 
    According to the complexity 6 is constant 

     So , Finally O(n^2) 

Answer 5

एक और आसान समाधान

T(n) = T(n-1) + n 
    = T(n-2) + n-1 + n 
    = T(n-3) + n-2 + n-1 + n 
    // we can now generalize to k 
    = T(n-k) + n-k-1 + n-k-2 + ... + n-1 + n 
    // since n-k = 1 so k = n-1 and T(1) = 1 
    = 1 + 2 + ... + n 
    = n(n-1)/2 
    = n^2/2 - n/2 
    // we take the dominating term which is n^2*1/2 therefor 1/2 = big O 
    = big O(n^2)