Dễ dàng: Giải quyết T (n) = T (n-1) + n bằng phương pháp Iteration

Question

Ai đó có thể giúp tôi với điều này?

Sử dụng phương pháp lặp để giải quyết. T (n) = T (n-1) + n

Giải thích các bước sẽ được đánh giá cao.

Answer 1

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

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

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

và vân vân bạn có thể thay thế giá trị của T (n-1) và T (n 2) trong T (n) để có được một ý tưởng chung của mô hình.

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 

Đối với trường hợp cơ sở:

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

k = n - 1 thay thế ở trên

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

nào bạn có thể thấy là chính về trật tự n^2

Answer 2

Mở rộng!

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

và như vậy, cho đến khi

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

với điều kiện T(1) = 1

Answer 3

Trong giả mã sử dụng phép lặp:

function T(n) { 
    int result = 0; 

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

    return result; 
}  

Answer 4

Phương pháp dễ dàng:

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

Một giải pháp dễ dàng hơn

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)