Equazione di ricorrenza
[tex]T(n)=T(n-1)+n[/tex]
Se volessi provare a farla con l' albero di ricorsione avrei un solo nodo per ogni livello, come mi regolo per calcolare la somma?
Se volessi provare a farla con l' albero di ricorsione avrei un solo nodo per ogni livello, come mi regolo per calcolare la somma?
Risposte
Ciao,
un'altra equazione di ricorrenza
questo modo dell'albero ad un solo ramo mi pare di averlo già discusso in qualche vecchio post.
Se utilizzi l'albero, e lo "espandi" avrai, come dici bene, un solo ramo.
La sommatoria fino alla foglia (non compresa) è composta solo dai nodi interni (in generale), perciò è una spartana somma dei livelli:
$sum_{k=0}^(n-1) (n-k) = sum_{j=1}^(n) j = (n*(n+1))/2$
sommando pure la foglia che è una costante, diviene:
$(n*(n+1))/2 + O(1) in O(n^2)$
non vedo difficoltà. Se hai dubbi chiedi pure
un'altra equazione di ricorrenza
questo modo dell'albero ad un solo ramo mi pare di averlo già discusso in qualche vecchio post.
Se utilizzi l'albero, e lo "espandi" avrai, come dici bene, un solo ramo.
La sommatoria fino alla foglia (non compresa) è composta solo dai nodi interni (in generale), perciò è una spartana somma dei livelli:
$sum_{k=0}^(n-1) (n-k) = sum_{j=1}^(n) j = (n*(n+1))/2$
sommando pure la foglia che è una costante, diviene:
$(n*(n+1))/2 + O(1) in O(n^2)$
non vedo difficoltà. Se hai dubbi chiedi pure
In quella sommatoria avrei:
[tex]n-0+n-1+n-2+...+n-k[/tex]
Cioè la somma dei primi n naturali...solo che andiamo indietro noi fino ad ottenere come termine 1 giusto?
Scusa un secondo ma sto pensando, ma in questo modo perchè la foglia è esclusa nella sommatoria? Arrivato a k=n-1 io ottengo 1, e non è esattamente la foglia quella? Allora la foglia per quale valore di k la ottengo?
Si tornano le equazioni di ricorrenza, mi sto ripreparando algoritmi, nella speranza di poterlo fare per luglio...
Grazie
[tex]n-0+n-1+n-2+...+n-k[/tex]
Cioè la somma dei primi n naturali...solo che andiamo indietro noi fino ad ottenere come termine 1 giusto?
Scusa un secondo ma sto pensando, ma in questo modo perchè la foglia è esclusa nella sommatoria? Arrivato a k=n-1 io ottengo 1, e non è esattamente la foglia quella? Allora la foglia per quale valore di k la ottengo?
Si tornano le equazioni di ricorrenza, mi sto ripreparando algoritmi, nella speranza di poterlo fare per luglio...
Grazie
Si questo è un caso particolare, dove l'albero serve solo a darti un'idea.
Quello che ti ho detto, e lo ho messo tra parentesi con "in generale" è fare una somma con i nodi interni e sommare la foglia separatamente.
In questo caso, non cambia nulla, vedi la sommatoria se partte da $k=0$ e $k=1$, il risultato è identico.
Può variare il risultato finito della sommatoria solo se hai qualche condizione sui casi base, nell'equazione di riccorrenza su valori particolari di $n$, tipo se hai scritto:
${(4 if n=2),(T(n-1) + n\ \ other):}$
ma non era mia intenzione crearti confusione, questo caso (non l'esempio) è banalmente risolvibile con il metodo della sostituzione, senza scomodare l'albero che è inutile.
PS: se hai problemi sugli argomenti dell'esame posta pure qua
Quello che ti ho detto, e lo ho messo tra parentesi con "in generale" è fare una somma con i nodi interni e sommare la foglia separatamente.
In questo caso, non cambia nulla, vedi la sommatoria se partte da $k=0$ e $k=1$, il risultato è identico.
Può variare il risultato finito della sommatoria solo se hai qualche condizione sui casi base, nell'equazione di riccorrenza su valori particolari di $n$, tipo se hai scritto:
${(4 if n=2),(T(n-1) + n\ \ other):}$
ma non era mia intenzione crearti confusione, questo caso (non l'esempio) è banalmente risolvibile con il metodo della sostituzione, senza scomodare l'albero che è inutile.
PS: se hai problemi sugli argomenti dell'esame posta pure qua
Ah ok ok, grazie, mi dedico agli esercizi una due volte alla settimana, quando avrò dubbi, speriamo meno possibili posterò.
E grazie come sempre.
posterò.E grazie come sempre.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo