Equazione di ricorrenza
Ho la seguente equazione di ricorrenza: $T(n)=T(n/2)+T(n/4)+T(n/8)+n$
per la risoluzione ho applicato l'albero di ricorsione e ho fatto le seguenti considerazioni: l'altezza è $log_2(n)$ perché devo considerare il ramo più lungo; ogni nodo al livello $i$ ha un costo di $(7/8)^i*n$. Il costo totale dell'albero è la sua altezza moltiplicata per il costo dei nodi, quest'ultimo costo determinato con la serie geometrica di ragione $q=7/8$, qundi la soluzione dovrebbe essere $T(n)=O(n*log_2(n))$. Ma la soluzione proposta è Theta(n).
per la risoluzione ho applicato l'albero di ricorsione e ho fatto le seguenti considerazioni: l'altezza è $log_2(n)$ perché devo considerare il ramo più lungo; ogni nodo al livello $i$ ha un costo di $(7/8)^i*n$. Il costo totale dell'albero è la sua altezza moltiplicata per il costo dei nodi, quest'ultimo costo determinato con la serie geometrica di ragione $q=7/8$, qundi la soluzione dovrebbe essere $T(n)=O(n*log_2(n))$. Ma la soluzione proposta è Theta(n).
Risposte
"avanzo una possibile spiegazione": $T(n)=O(n⋅log_2(n))$ non può essere perché il costo esterno non è costante ossia $cn$ e di conseguenza l'altezza dell'albero non va cosiderata!. Per cui si stima solo il costo esterno come un possibile upper bound.
Secondo me potresti provare se è $theta(n)$
Butta giù una GUESS ed usi la sostituzione per O grande e dopo omega.
L'albero, come forse hai capito, ha diverse altezze come anche $log_4 n$.
Lascia stare l'altezza totale, anzi guarda anche quella minore: in questo caso hai un albero strambo che ha la parte destra che termina prima con altezza $log_8 n$
$n$ --> $n((4+2+1)/8) = 7/8n$ --> $n(49/64)=(7/8)^2 n$ --> $..$ devi arrivare alle foglie e capirai che la suddetta GUESS può andare.
Se guardi bene hai quasi sempre una serie geometrica $sum_(k=0)^(n) x^k$ come quella che hai indicato tu che è teta di n perché arrivi ad avere al massimo $(7/8)^(log_2 n)$ che sta dentro $O(n)$ (..e lascio a te trovare un $c$ ed un $n_o$ dopo la sostituzione per avere la limitazione superiore)
Limitazione inferiore banale ora che vedo, ad occhio si vede:
$T(n) = T(n/2) + T(n/4) + T(n/8) + n >= n $ ? $>=cn$ ?
vero per $c<=1$ con un $n=1$ quindi $Omega(n)$
Se ho detto cavolate correggetemi
Butta giù una GUESS ed usi la sostituzione per O grande e dopo omega.
L'albero, come forse hai capito, ha diverse altezze come anche $log_4 n$.
Lascia stare l'altezza totale, anzi guarda anche quella minore: in questo caso hai un albero strambo che ha la parte destra che termina prima con altezza $log_8 n$
$n$ --> $n((4+2+1)/8) = 7/8n$ --> $n(49/64)=(7/8)^2 n$ --> $..$ devi arrivare alle foglie e capirai che la suddetta GUESS può andare.
Se guardi bene hai quasi sempre una serie geometrica $sum_(k=0)^(n) x^k$ come quella che hai indicato tu che è teta di n perché arrivi ad avere al massimo $(7/8)^(log_2 n)$ che sta dentro $O(n)$ (..e lascio a te trovare un $c$ ed un $n_o$ dopo la sostituzione per avere la limitazione superiore)
Limitazione inferiore banale ora che vedo, ad occhio si vede:
$T(n) = T(n/2) + T(n/4) + T(n/8) + n >= n $ ? $>=cn$ ?
vero per $c<=1$ con un $n=1$ quindi $Omega(n)$
Se ho detto cavolate correggetemi
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo