Equazione di ricorrenza
Buongiorno sto cercando di fare questo esercizio...scusate se allego l’immagine ma mi risulta difficile scriverlo, ho dei dubbi sul contributo dei nodi di ogni livello...potete dirmi se è corretto?
Risposte
Se hai davanti quel tipo di ricorrenze (con più chiamate e taglie di input differenti) non è scontato effettuare una stima esatta del contributo dei nodi, in quanto sicuramente ci sarà qualche chiamata che sarà arrivata al caso base prima di altre. In queste situazioni l'albero possiede le foglie a livelli differenti.
Una volta disegnato l'albero puoi decidere se risolvere la ricorrenza ipotizzando una soluzione applicando la sostituzione, altrimenti calcolare la sommatoria dei costi: in tal caso quello che potresti fare è effettuare una stima per eccesso considerando il contributo di foglie dalla "parte" delle chiamate che impiegano più tempo ad arrivare al caso base (più profondi), in altre parole maggiorando la sommatoria effettiva dei costi con una sommatoria "superiore" e ottenere il limite superiore della tua funzione. Nel tuo caso hai dei sottoproblemi di dimensione $\frac{n^2}{2^i}$ e $\frac{n^2}{3^i}$, dove $\frac{n^2}{3^i}$ decresce più rapidamente e arriverà al caso base prima di $\frac{n^2}{2^i}$.
Calcolando i costi dei livelli ottieni
Una volta disegnato l'albero puoi decidere se risolvere la ricorrenza ipotizzando una soluzione applicando la sostituzione, altrimenti calcolare la sommatoria dei costi: in tal caso quello che potresti fare è effettuare una stima per eccesso considerando il contributo di foglie dalla "parte" delle chiamate che impiegano più tempo ad arrivare al caso base (più profondi), in altre parole maggiorando la sommatoria effettiva dei costi con una sommatoria "superiore" e ottenere il limite superiore della tua funzione. Nel tuo caso hai dei sottoproblemi di dimensione $\frac{n^2}{2^i}$ e $\frac{n^2}{3^i}$, dove $\frac{n^2}{3^i}$ decresce più rapidamente e arriverà al caso base prima di $\frac{n^2}{2^i}$.
Calcolando i costi dei livelli ottieni
Livello 0: $n^2$
Livello 1: $[(\frac{1}{2})^2+(\frac{1}{2})^2+(\frac{1}{3})^2]n^2 = \frac{11}{18}n^2$
Livello 2: $[4(\frac{1}{4})^2+4(\frac{1}{6})^2+(\frac{1}{9})^2]n^2 = \frac{121}{324}n^2=(\frac{11}{18})^2 n^2$
...
Livello i: $(\frac{11}{18})^i n^2$
[/list:u:3i9pswed]
Ora sicuramente il costo reale della ricorrenza è minore o uguale di $(\frac{11}{18})^i n^2$, quindi calcolando la sommatoria dell'i-esimo livello ti ricavi un limite superiore.
"Leyxargon":
Se hai davanti quel tipo di ricorrenze (con più chiamate e taglie di input differenti) non è scontato effettuare una stima esatta del contributo dei nodi, in quanto sicuramente ci sarà qualche chiamata che sarà arrivata al caso base prima di altre. In queste situazioni l'albero possiede le foglie a livelli differenti.
Una volta disegnato l'albero puoi decidere se risolvere la ricorrenza ipotizzando una soluzione applicando la sostituzione, altrimenti calcolare la sommatoria dei costi: in tal caso quello che potresti fare è effettuare una stima per eccesso considerando il contributo di foglie dalla "parte" delle chiamate che impiegano più tempo ad arrivare al caso base (più profondi), in altre parole maggiorando la sommatoria effettiva dei costi con una sommatoria "superiore" e ottenere il limite superiore della tua funzione. Nel tuo caso hai dei sottoproblemi di dimensione $\frac{n^2}{2^i}$ e $\frac{n^2}{3^i}$, dove $\frac{n^2}{3^i}$ decresce più rapidamente e arriverà al caso base prima di $\frac{n^2}{2^i}$. Calcolando i costi dei livelli ottieni
Livello 0: $n^2$
Livello 1: $(\frac{1}{2}+\frac{1}{2}+\frac{1}{3})n^2 = \frac{4}{3}n^2$
Livello 2: $(4\frac{1}{4}+4\frac{1}{6}+\frac{1}{9})n^2 = \frac{16}{9}n^2=(\frac{4}{3})^2 n^2$
...
Livello i: $(\frac{4}{3})^i n^2$
[/list:u:2gamj7k6]
Ora sicuramente il costo reale della ricorrenza è minore di $(\frac{4}{3})^i n^2$, quindi calcolando la sommatoria dell'i-esimo livello ti ricavi un limite superiore.
Ma per ogni nodo il suo contributo non va elevato al quadrato?
"sara09":
Ma per ogni nodo il suo contributo non va elevato al quadrato?
Errore mio, ho corretto i calcoli. La procedura resta la medesima.
"Leyxargon":
[quote="sara09"]Ma per ogni nodo il suo contributo non va elevato al quadrato?
Errore mio, ho corretto i calcoli. La procedura resta la medesima.[/quote]
Va bene e se ho:
$ 3(n/2) $
Nella seconda equazione del sistema allora al secondo livello dell’albero avrei:
$ 9(n/2)^2+9(n/2)^2+(n/3)^2 $
Giusto?
"sara09":
[quote="Leyxargon"][quote="sara09"]Ma per ogni nodo il suo contributo non va elevato al quadrato?
Errore mio, ho corretto i calcoli. La procedura resta la medesima.[/quote]
Va bene e se ho:
$ 3(n/2) $
Nella seconda equazione del sistema allora al secondo livello dell’albero avrei:
$ 9(n/2)^2+9(n/2)^2+(n/3)^2 $
Giusto?[/quote]
Se ho capito bene, stai supponendo una relazione di questo tipo
\[ T(n) = 3T(\frac{n}{2}) + T(\frac{n}{3}) + n^2 \]
In tal caso lo svolgimento sarebbe il seguente
Livello 0: $n^2$
Livello 1: $[3(\frac{1}{2})^2 + (\frac{1}{3})^2]n^2 = \frac{31}{36}n^2$
Livello 2: $[9(\frac{1}{4})^2 + 6(\frac{1}{6})^2 + (\frac{1}{9})^2]n^2 = \frac{961}{1296}n^2$
...
Livello i: $(\frac{31}{36})^i n^2$
[/list:u:j2q84l5t]
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo