Làm thế nào để giải quyết: T (n) = T (n - 1) + n

Question

Tôi đã sau đây làm việc ra:

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

Bây giờ khi tôi làm việc này ra tôi thấy rằng các ràng buộc là rất lỏng lẻo. Tôi đã làm điều gì đó sai hay chỉ là theo cách đó?

Answer 1

Hãy suy nghĩ theo cách này:
Trong mỗi "lần lặp" của đệ quy bạn thực hiện O (n).
Mỗi lần lặp lại có công việc n-1 để làm, cho đến khi n = trường hợp cơ sở. (Tôi giả sử trường hợp cơ sở là O (n) công việc)
Vì vậy, giả sử trường hợp cơ sở là một độc lập liên tục của n, có O (n) lặp đi lặp lại của đệ quy.
Nếu bạn có n lần lặp O (n) hoạt động, O (n) * O (n) = O (n^2).
Phân tích của bạn là chính xác. Nếu bạn muốn biết thêm thông tin về cách giải quyết các cuộc thám hiểm này, hãy nhìn vào cây Recursion. Chúng rất trực quan so với các phương pháp khác.

Answer 2

Bạn cũng cần trường hợp cơ sở cho mối quan hệ lặp lại của mình.

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

Để giải quyết vấn đề này, trước tiên bạn có thể đoán giải pháp và sau đó chứng minh nó hoạt động bằng cảm ứng.

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

Trường hợp cơ sở đầu tiên. Khi n = 1 điều này cho c theo yêu cầu.

Đối với n khác:

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

Vì vậy, các giải pháp công trình.

Để có được đoán ở nơi đầu tiên, nhận thấy rằng mối quan hệ tái phát của bạn tạo ra các triangular numbers khi c = 1:

T(1) = 1: 

* 

T(2) = 3: 

* 
** 

T(3) = 6: 

* 
** 
*** 

T(4) = 10: 

* 
** 
*** 
**** 

etc.. 

trực giác một tam giác là khoảng một nửa của một hình vuông, và trong ký hiệu Big-O hằng số có thể được bỏ qua vì vậy O (n^2) là kết quả mong đợi.

Answer 3

Có vẻ đúng, nhưng sẽ tùy thuộc vào trường hợp cơ sở T (1). Giả sử bạn sẽ thực hiện các bước n để lấy T (n) đến T (0) và mỗi lần n là bất kỳ từ 0 đến n với giá trị trung bình là n/2 sao cho n * n/2 = (n^2)/2 = O (n^2).

Answer 4

Giải pháp này khá dễ dàng cho giải pháp này. Bạn phải hủy đăng ký đệ quy:

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

Bạn có phép tính số học tại đây và tổng là 1/2*n*(n-1). Về mặt kỹ thuật bạn đang thiếu điều kiện biên ở đây, nhưng với bất kỳ điều kiện biên liên tục nào bạn thấy rằng đệ quy là O(n^2).