Metodo di unfolding/ricorrenze
Salve a tutti,
Vorrei chiedervi come risolvere questa equazione alle ricorrenze:
T(n) = 4*T(n/2) + n^2
Il procedimento, almeno come l'ho capito sarebbe:
1)Scrivo le equazioni per i primi 2/3 sviluppi:
T(n/2) = 4*T(n/4) + (n/2)^2
T(n/4) = 4*T(n/8) + (n/4)^2
2) Ricavo la forma della serie corrispondente:
T(n) = n^2 * sommatoria(4^i/(2^2i))
3) RIcavo l'estremo superiore della serie imponendo che la cardinalita' sia 1.
n/(2^i) = 1
4) Applico la formula per la progressione geometrica e il grado dell'equazione rappresenta la complessita' dell'algoritmo.
Il mio problema in questo caso, a meno di non aver sbagliato il metodo, e' che il valore dell'i-esimo elemento della sommatoria e' 1 mentre immagino che dovrebbe essere diverso. Di conseguenza quando applico la formula per la progressione geometrica ottengo al numeratore (1-1) = 0.
Grazie mille.
Vorrei chiedervi come risolvere questa equazione alle ricorrenze:
T(n) = 4*T(n/2) + n^2
Il procedimento, almeno come l'ho capito sarebbe:
1)Scrivo le equazioni per i primi 2/3 sviluppi:
T(n/2) = 4*T(n/4) + (n/2)^2
T(n/4) = 4*T(n/8) + (n/4)^2
2) Ricavo la forma della serie corrispondente:
T(n) = n^2 * sommatoria(4^i/(2^2i))
3) RIcavo l'estremo superiore della serie imponendo che la cardinalita' sia 1.
n/(2^i) = 1
4) Applico la formula per la progressione geometrica e il grado dell'equazione rappresenta la complessita' dell'algoritmo.
Il mio problema in questo caso, a meno di non aver sbagliato il metodo, e' che il valore dell'i-esimo elemento della sommatoria e' 1 mentre immagino che dovrebbe essere diverso. Di conseguenza quando applico la formula per la progressione geometrica ottengo al numeratore (1-1) = 0.
Grazie mille.
Risposte
$T(n) = 4T(n/2) + n^2$
Se dovessi fare un Guess direi almeno $O(n^2)$ ma non sono ancora sicuro con queste carissime ricorrenze.
Tramite l'albero si potrebbe ottenere
$4^0 n^2$ che si paga al primo passo
$4^1 n^2 /2^2$ al secondo passo
$4^2 n^2 /2^4$ al terzo
Prima di arrivare a tutti i $T(1)$ di "grandezza unica" (ossia $4^(log_2 n)$ ) dovrei avere il passo:
$4^((log n)-1) * (n^2)/(2^(2(log n)-1))$
Altezza dell'albero è $log_2 n$, $n/2^i=1$ quando $i=log_2 n$
Il passo dove termina la ricorsione che mi sono permesso di chiamare di "grandezza uno" costa:
$4^(log_2 n ) * T(1)$ quindi si può trasformare in $n^(log_2 4) *T(1)$ ossia $n^2$.
Però dobbiamo sommare tutto l'albero.
$T(n) = sum_{i=0}^((log n )-1) 4^i * n^2 / (2^(2*i))$
$= n^2 * sum_{i=0}^((log n )-1) 2^(2*i) / (2^(2*i))$
QUI CHIEDO AIUTO
Se dovessi fare un Guess direi almeno $O(n^2)$ ma non sono ancora sicuro con queste carissime ricorrenze.
Tramite l'albero si potrebbe ottenere
$4^0 n^2$ che si paga al primo passo
$4^1 n^2 /2^2$ al secondo passo
$4^2 n^2 /2^4$ al terzo
Prima di arrivare a tutti i $T(1)$ di "grandezza unica" (ossia $4^(log_2 n)$ ) dovrei avere il passo:
$4^((log n)-1) * (n^2)/(2^(2(log n)-1))$
Altezza dell'albero è $log_2 n$, $n/2^i=1$ quando $i=log_2 n$
Il passo dove termina la ricorsione che mi sono permesso di chiamare di "grandezza uno" costa:
$4^(log_2 n ) * T(1)$ quindi si può trasformare in $n^(log_2 4) *T(1)$ ossia $n^2$.
Però dobbiamo sommare tutto l'albero.
$T(n) = sum_{i=0}^((log n )-1) 4^i * n^2 / (2^(2*i))$
$= n^2 * sum_{i=0}^((log n )-1) 2^(2*i) / (2^(2*i))$
QUI CHIEDO AIUTO
"Giova411":
$T(n) = 4T(n/2) + n^2$
Se dovessi fare un Guess direi almeno $O(n^2)$ ma non sono ancora sicuro con queste carissime ricorrenze.
Non prendere questa cosa che ho scritto sul serio!!!
Perché non puo' essere solo $O(n^2)$. Ci sarà "un qualcosa" di superiore ma non è sicuro $O(n^3)$.
Ma diciamo che mi sono tirato la zappa sui piedi perchè non serve andare ad occhio...
@Giova411: Perché cercare di indovinare una complessità quando esiste il Master Theorem proprio per risolvere questo tipo di ricorrenze? La complessità di quella ricorrenza è \(\Theta(n^2\,\log n)\) (caso 2)..
Ovviamente si poteva arrivare alla stessa conclusione anche usando il tuo metodo.. Stai sommando degli uno..
Ovviamente si poteva arrivare alla stessa conclusione anche usando il tuo metodo.. Stai sommando degli uno..
Master da studiare ancora 
Grazie Mille
"Giova411":
$= n^2 * sum_{i=0}^((log n )-1) (1)$
Non so perché allora
dovrebbe venire $n^2 * log n$Quindi sommiamo il caso dove avevamo tutti i $T(1)$:
$T(n) = n^2 + n^2 * log n = O(n^2 log n)$
Certo col Teorema abbiamo più precisione e ci si mette 30 secondi..... (Almeno credo
)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo