Łatwo: Rozwiąż T (n) = T (n-1) + n metodą iteracji

Question

Czy ktoś może mi w tym pomóc?

Użyj metody iteracji, aby go rozwiązać. T (n) = T (n-1) + n

Wyjaśnienie kroków byłoby bardzo docenione.

Answer 1

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

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

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

itd można zastąpić wartość T (n-1) i T (N 2) w T (n), aby uzyskać ogólne pojęcie o wzorze.

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 

Dla przypadku podstawowym:

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

k = n - 1 substytut podano

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

które można zobaczyć jest rzędu n^2

Answer 2

Rozwiń to!

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

i tak dalej, aż do

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

ile T(1) = 1

Answer 3

pseudo kod z iteracją:

function T(n) { 
    int result = 0; 

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

    return result; 
}  

Answer 4

Łatwy Metoda:

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

Inną prostsze rozwiązanie

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)