Ricorrenze e domande

[Darèios89]

Ho un paio di domande, ho provato a risolvere questa ricorrenza:

[tex]T(n)=4T(n/5)+T(n/6)+n[/tex]

Ho pensato di provare per induzione che [tex]T(n)\leq cn[/tex]

Non so fare le dimostrazioni per induzione, vedendo gli appunti ci ho provato ma non sono convinto affatto.

Ho considerato [tex]n=(k/5)[/tex]

[tex]T(k/5)= ck/5[/tex]

Per n=k/6 [tex]T(k/6)=ck/6[/tex]

La ricorrenza è [tex]T(k)=4T(k/5)+T(k/6)+k[/tex] e diventa:

[tex]T(k)\leq 4ck/5+ck/6+k[/tex]

E continuando trovo [tex]T(k)\leq k(1+29c)[/tex]

E' scorretta? Si può concludere vera per ogni c>1?


In un' altra ricorrenza:

[tex]T(n)=T(n-1)+T(n-2)+n[/tex]

Ho provato a rappresentarla con l' albero di ricorsione e ottengo come costi:

n
2n-3
4n-12
.
.
.

Solo che per scriverla formalmente avrei [tex]2^in...[/tex] e non riesco a capire come rappresentare il secondo termine che non è una potenza di 2 ma un multiplo....

[hamming_burst]

"krak":[
Forse dirò una cosa sbagliata..ma la soluzione di questa ricorrenza non è [tex]O(n)[/tex]??

no non può essere $O(n)$ si vede subito utilizzando la sostituzione:

\( 4c\frac{n}5 + c\frac{n}6 + n = (\frac{29}{30}c + 1)n \not\leq cn\) per nessuno $c$.

Una curiosità, lo sviluppo l'albero, così come ho fatto sotto è giusto?
[tex]n[/tex]
[tex](\frac{n}{5}+\frac{n}{5}+\frac{n}{5}+\frac{n}{5})+(\frac{n}{6})= \frac{29}{30}n[/tex]
[tex](\frac{n}{5}+\frac{n}{5}+\frac{n}{5}+\frac{n}{5})+(\frac{n}{5}+\frac{n}{5}+\frac{n}{5}+\frac{n}{5})+(\frac{n}{5}+\frac{n}{5}+\frac{n}{5}+\frac{n}{5})+(\frac{n}{5}+\frac{n}{5}+\frac{n}{5}+\frac{n}{5})+(\frac{n}{6})[/tex]

mi pare di no, per queste sosotituzioni che avvengono in modo diverso da come hai fatto e come trattare in generale questo genere di ricorrenze prova a vedere questo riassunto che feci qualche settimana fa, se hai domande chiedi pure

[krak2]

Si, in effetti mi sono complicata un pò la vita con quell'albero che ho fatto.
Quindi in generale, quando ho più rami di ricorsione e se questi non sono equilibrati, semplifico l'albero riscrivendolo con una limitazione superiore o inferiore.
Grazie mille!!!

[hamming_burst]

"krak":Si, in effetti mi sono complicata un pò la vita con quell'albero che ho fatto.

non è detto che tu ti sia complicato la vita, dipende dal tipo di ricorrenza (vedi (*))
Per la ricorrenza con l'albero, per essere corretti verrebbe in questo modo:

$n$
$n/5 n/5 n/5 n/5 n/6$
$(n/(25)\ n/(25)\ n/(25)\ n/(25)\ n/(30))\ (n/(25)\ n/(25)\ n/(25)\ n/(25)\ n/(30))\ (n/(25)\ n/(25)\ n/(25)\ n/(25)\ n/(30))$ cont.
$(n/(25)\ n/(25)\ n/(25)\ n/(25)\ n/(30))\ (n/(30) n/(30) n/(30) n/(30) n/(36))$
...

Quindi in generale, quando ho più rami di ricorsione e se questi non sono equilibrati, semplifico l'albero riscrivendolo con una limitazione superiore o inferiore.
Grazie mille!!!

Sì, io ti consiglio di fare in questo modo.
(*) Si studia l'interno della ricorrenza così da capirne l'andamento e dare un'ipotesi più stretta, ma attenzione che non sempre funziona se vedi cosa è accaduto in quel post, dove si poteva utilizzare direttamente l'albero sulla ricorrenza senza riscrittura. Questo si può fare ssse se le costanti in gioco sono "equilibrate" (nn è il termine corretto, meglio dire "distribuite equamente").

[krak2]

Va bene ok, mi hai spiegato chiaramente.
Grazie!!