Rozwiąż: T (n) = T (n/2) + n/2 + 1

Question

Trudno mi zdefiniować czas działania dla następującego algorytmu w notacji O. Moje pierwsze przypuszczenie to O (n), ale różnica między iteracjami a liczbą, którą aplikuję, nie jest stała. Jak błędnie to zdefiniowałem?

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

The while jest wykonywany w około n/2 czasie.

rekursji jest wykonywany przekazując jako n wartość, która jest o połowę pierwotnego n, więc:

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

ten jest podobny do geometric serie.

Rzeczywiście może być reprezentowane

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

więc zbieżny do n * 1 = n

więc oznaczenie O jest O (n)

Answer 2

Innym podejściem jest to zapisać jako T(n) = T(n/2) + n/2 + 1 .
Podczas pracy w pętli działa n/2. Argument przekazany do następnego połączenia to n/2.

Rozwiązanie to pomocą master theorem gdzie:

• 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 

który jest:

T(n) = Θ(n)