Metodo dii unfolding

[darkmiento]

ciao ragazzi qualcuno potrebbe spiegarmi la parte finale del metodo di unfolding? vi faccio vedere con un esempio dove so arrivare:
es) T(n)=3T(n/2)+n^2
T(n/2)=3T(n/4)+(n/2)^2
T(n/4)=3T(n/8)+(n/4)^2
quindi
T(n)=27T(n/8)+9/16n^2+3/4n^2+n^2
la serie mi viene
$\sum_{i=1}^M (3/4)^i$

poi??? so che ci sono 3 casi, ma non so come usarli e come arrivare alla complessità!
grazie

[hamming_burst]

Ciao,

$T(n) = 3T(n/2)+n^2 = 3*(3T(n/4) + (n/2)^2)+ n^2 = 3*(3*(3T(n/8) + (n/4)^2) + (n/2)^2)+ n^2 = ...$
$... = 3^iT(n/2^i) + n^2/(2^(2i)) = .... = T(1)$ fino perciò a $i = log_2(n)$.

calcoliamo il termine generale:
$\sum_{i=0}^{log_2(n)-1} (3^i/2^(2i))n^2 = n^2\sum_{i=0}^{log_2(n)-1} (3/4)^i = (1 - (3/4)^{log_2(n)})/(1 - (3/4)) = 4n^2 - n^1.58 in O(n^2)$

so che ci sono 3 casi, ma non so come usarli e come arrivare alla complessità!

penso tu ti riferisca al Master Theorem ma è tutt'altra tecnica e non c'entra con questa.

[darkmiento]

ok come trovi log2(n) come estremo superiore di i?
cmq i tre casi erano per k (l'argomento della serie) <,= o > a 1...

[hamming_burst]

"noblex":cmq i tre casi erano per k (l'argomento della serie) <,= o > a 1...

ah ok, sorry...
bhe è la serie Serie geometica finita. In algoritmica valori negativi non hanno nessun senso (in questi esercizi), perciò hai due possibilità o trovi $=1$ (somma generica) o $>1$ (forma chiusa).

"noblex":ok come trovi log2(n) come estremo superiore di i?

lo si trova calcolando per quando $n=1$ cioè quando termina la ricorsione a $T(1)$.
In questo caso:

$T(n/2^i) = T(1)$ quando $n/2^i = n/2^{log_2(n)} = n/n^{log_2(2)} = n/n = 1$.