Pages: [1]   Go Down
Print
Author Topic: Esercizio  (Read 841 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« on: 03-03-2010, 20:07:11 »

Ragazzi qualcuno mi potrebbe dire perchè la ricorrenza

T(n) = 4T(n/5) + T(n/6) + n

risulta O(n)??

mi potreste dimostrare il perchè si ottiene questa soluzione?
Logged
Psycho
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 497



« Reply #1 on: 04-03-2010, 00:53:50 »

ho svolto questo esercizio nell'altro post, ti scrivo comunque la soluzione:
l'ho risolta tramite albero di ricorsione. ogni livello i ha costo 29/30, ne fai la sommatoria e la svolgi come serie geometrica con ragione <1 (la formula si trova nell'appendice A del libro). risultato 30n...O(n). svolto con metodo di sostituzione c mi risulta 30
Logged

Segnate le date, cancellate gli altri impegni, chiudete i libri e i quaderni e per un attimo accorgetevi che la vita non è piatta ma può essere... 3d!
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #2 on: 04-03-2010, 10:06:17 »

ma come limite superiore della sommatoria che valore dobbiamo prendere?
Logged
Psycho
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 497



« Reply #3 on: 04-03-2010, 10:11:40 »

log in base 5 di n, che è il ramo più lungo dell'albero
Logged

Segnate le date, cancellate gli altri impegni, chiudete i libri e i quaderni e per un attimo accorgetevi che la vita non è piatta ma può essere... 3d!
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #4 on: 04-03-2010, 14:45:56 »

quindi il numero delle foglie e la profondità dell'albero sarebbero log in base 5 di n vero??
Logged
Pages: [1]   Go Up
Print
Jump to: