Pages: [1]   Go Down
Print
Author Topic: Dubbio eq. di ricorrenza  (Read 1169 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Nova
Forumista
***
Offline Offline

Gender: Male
Posts: 567


-.-"


WWW
« on: 21-06-2010, 10:09:24 »

Ciao a tutti,
vorrei esporvi un dubbio su questa eq. di ricorrenza: T(n) = 4T(n/5) + T(n/6) + n
La sua soluzione non dovrebbe essere O(nlogn)?
Sul testo che ho io invece è segnata come soluzione O(n), non capisco come mai.

Mi aiutereste a far luce su questo caso? XD
Logged

Ubuntu user:
#29872
n2o1988
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 206



« Reply #1 on: 16-09-2010, 12:08:01 »

Ciao a tutti,
vorrei esporvi un dubbio su questa eq. di ricorrenza: T(n) = 4T(n/5) + T(n/6) + n
La sua soluzione non dovrebbe essere O(nlogn)?
Sul testo che ho io invece è segnata come soluzione O(n), non capisco come mai.

Mi aiutereste a far luce su questo caso? XD

Ciao a tutti, chiedo scusa se riprendo questo vecchio post, ma non mi è chiaro il procedimento per risolvere questa ricorrenza. Qualcuno può illuminarmi? Grazie mille 
Logged
8leoncina7
Apprendista Forumista
**
Offline Offline

Posts: 266



« Reply #2 on: 16-09-2010, 14:44:20 »

Ciao a tutti,
vorrei esporvi un dubbio su questa eq. di ricorrenza: T(n) = 4T(n/5) + T(n/6) + n
La sua soluzione non dovrebbe essere O(nlogn)?
Sul testo che ho io invece è segnata come soluzione O(n), non capisco come mai.

Mi aiutereste a far luce su questo caso? XD

Ciao a tutti, chiedo scusa se riprendo questo vecchio post, ma non mi è chiaro il procedimento per risolvere questa ricorrenza. Qualcuno può illuminarmi? Grazie mille 


la soluzione corretta è O(n).. è sufficiente utilizzare il metodo dell'albero di ricorsione che trovi ben spiegato sul testo
 ciao
Logged

meglio fare e pentirsi che non fare e pentirsi lo stesso..
                                                                Machiavelli
n2o1988
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 206



« Reply #3 on: 16-09-2010, 17:01:09 »

Ok, ti ringrazio... c'ero arrivato tramite dimostrazione per induzione ma non ero sicuro di averla fatta corretta. 
Logged
8leoncina7
Apprendista Forumista
**
Offline Offline

Posts: 266



« Reply #4 on: 16-09-2010, 17:23:18 »

di nulla  però se posso intromettermi ti consiglio di provare anche a svolgerla con l'albero di ricorsione, usare più metodi ti aiuta ad essere più certo della tua risposta e a capire bene ogni singolo metodo ..
in ogni caso buon lavoro e in bocca a lupo per l'esame
 ciao
Logged

meglio fare e pentirsi che non fare e pentirsi lo stesso..
                                                                Machiavelli
Pages: [1]   Go Up
Print
Jump to: