Calcolo complessita' e teorema master

[jack012]

Salve,

Ho il seguente algoritmo per il quale devo calcolare la complessita':

void test(intero n)
    if(n=1) then return 1
    else
      somma=0
      for i=1 to n do
        for j=1 to n/2 do
          for k=1 to 5 do
            somma++
    return test(n/2)

La relazione di ricorrenza risulta essere: $ T(n) = T(n/2) + (5n^2)/2 + 1 $. Adesso sto cercando di risolvere con il Teorema Master:

$ a=1, b = 2, f(n) = O(n^2) $.

quindi $ n^((log_2) 1) = n^0 = 1 $, percio' $ f(n) > 1 $ quindi sono nel terzo caso del TM.

Per il terzo caso devo calcolare anche $ a * f(n/b) <= c * f(n) $ per $ c < 1 $. Quindi:

$ ((5n^2)/(2) + 1)/2 <= c * (5n^2)/(2) + 1 $


$ (5n^2)/(4) + 1/2 <= c * (5n^2)/(2) + 1 $

scelgo $ c = 1/2 $. Qualcuno mi puo' dire se questa soluzione e' corretta? Grazie.

[hamming_burst]

Ciao,

"jack01":
La relazione di ricorrenza risulta essere: $ T(n) = T(n/2) + (5n^2)/2 + 1 $. Adesso sto cercando di risolvere con il Teorema Master:

$ a=1, b = 2, f(n) = O(n^2) $.

quindi $ n^((log_2) 1) = n^0 = 1 $, percio' $ f(n) > 1 $ quindi sono nel terzo caso del TM.

Si/No.
Ma per me è sbagliato.

ti ricordo che nel master devi considerare un $0<\epsilon<=1$ per delimitare la funzione. In questo caso puoi farlo ma sforando polinomialmente la funzione:
$n^2 \in \Omega(n^{(log_2)(1) + \epsilon})$ con $\epsilon=1$ perciò $n^2 \in \Omega(n)$

certo la condizione dovrebbe esser valida, ma per applicare il master si deve avare lo stesso ordine del polinomio e scalare di poco per far combaciare la limitazione. In questo caso vai da ordine $1$ ad ordine $2$ cosa non possibile per la definizione di applicabilità del master.
Devi utilizzare altre tecniche.

[jack012]

Ho capito adesso, grazie.

Provo a risolverla srotollando.

$ T(n) = T(\frac{n}{2}) + 5\frac{n^2}{2} + 1 $

$ T(n) = T(\frac{n}{2^2}) + 5\frac{n^2}{2^2} + 1 $

$ T(n) = T(\frac{n}{2^3}) + 5\frac{n^2}{2^3} + 1 $

per 3 passi ho:

$ T(n) = T(\frac{n}{2^3}) + 5\frac{n^2}{2^3} + 5\frac{n^2}{2^2} + 5\frac{n^2}{2^1} + 3 $

sostituisco il numero di passi con j e ho:

$ T(n) = T(\frac{n}{2^3}) + 5\frac{n^2}{2^3} + 5\frac{n^2}{2^2} + 5\frac{n^2}{2^1} + 1*3 $

$ T(n) = T(\frac{n}{2^3}) + \sum_{j=0}^{2} 5\frac{n^2}{2^j} + 1*3 $

per i passi:

$ T(n) = T(\frac{n}{2^i}) + \sum_{j=0}^{i-1} 5\frac{n^2}{2^j} + 1*i $

ma $ \frac{n}{2^i} = 1 $ quando $ 2^i = n => i = log_2 n $

sostituindo nella mia equazione ho:

$ T(n) = T(1) + 5n^2 \sum_{i=0}^{logn-1} \frac{1}{2^i} + logn $

$ T(n) = 5n^2 \sum_{i=0}^{logn-1} (\frac{1}{2})^i + logn $