Giải quyết: T (n) = T (n/2) + n/2 + 1

Question

Tôi cố gắng xác định thời gian chạy cho thuật toán sau trong ký hiệu O. Đoán đầu tiên của tôi là O (n), nhưng khoảng cách giữa các lần lặp lại và số tôi áp dụng không ổn định. Làm thế nào tôi đã xác định không chính xác điều này?

public int function (int n) 
{ 
    if (n == 0) { 
    return 0; 
    } 

    int i = 1; 
    int j = n ; 
    while (i < j) 
    { 
    i = i + 1; 
    j = j - 1; 
    } 
    return function (i - 1) + 1; 
} 

Answer 1

while được thực hiện trong khoảng thời gian n/2.

Các đệ quy được thực hiện thông qua như n một giá trị đó là khoảng một nửa số bản gốc n, vì vậy:

n/2 (first iteration) 
n/4 (second iteration, equal to (n/2)/2) 
n/8 
n/16 
n/32 
... 

này tương tự như một geometric serie.

Infact nó có thể được biểu diễn dưới dạng

n * (1/2 + 1/4 + 1/8 + 1/16 + ...) 

Vì vậy, khi hội tụ tới n * 1 = n

Vì vậy, các ký hiệu O là O (n)

Answer 2

Một cách khác là để viết nó xuống như T(n) = T(n/2) + n/2 + 1 .
Vòng lặp while n/2 hoạt động. Đối số được chuyển đến cuộc gọi tiếp theo là n/2.

Giải quyết này bằng cách sử dụng master theorem nơi:

• a = 1
• b = 2
• f = n/2 + 1

Let c=0.9 
1*(f(n/2) + 1) <? c*f(n) 
1*(n/4)+1 <? 0.9*(n/2 + 1) 
0.25n + 1 <? 0.45n + 0.9 
    0 < 0.2n - 0.1 

Đó là:

T(n) = Θ(n)