Pages: [1]   Go Down
Print
Author Topic: Equazioni di ricorrenza  (Read 2081 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
the doctor 46
Matricola
*
Offline Offline

Posts: 31


« on: 21-04-2010, 16:35:08 »

Salve,
 sapete dirmi come svolgere con relativo risultato finale, le seguenti equazioni di ricorrenza :



1)      T(n) = T(n-1) + logn

2)      T(n) = T(n-1) + 1/n


Grazie.
Logged
leviadragon
Apprendista Forumista
**
Offline Offline

Posts: 217


WWW
« Reply #1 on: 21-04-2010, 20:47:17 »

Secondo il mio ragionamento :
1) costruendoti l'albero di ricorsione (che sta volta albero non è ma è una lista) con 1 chiamata da logn.
l'altezza dell'albero è n , poichè ogni nodo va  n , n -1 , n-2 .. ecc .
in totale dovresti moltiplicare l'altezza(n) dell'albero per il costo del nodo (logn) quindi  O(nlogn)

Spero di averti aiutato , ma se ho sbagliato qualcuno mi corregga per favore!
Logged

www.darkzero.altervista.org <-- se vi piace mettetela come homepage

Link Immagine


--gratuitamente ricevete,gratuitamente date--
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #2 on: 22-04-2010, 10:51:52 »

dall' abero di ricorrenza vengono fuori queste 2 sommatorie

1) \sum_{i=1}^n (logi)

2) \sum_{i=1}^n (1/i)

che sono 2 serie note  ok
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #3 on: 22-04-2010, 14:21:01 »

@the doctor 46
al di là del risultato.

Quote
Secondo il mio ragionamento :
1) costruendoti l'albero di ricorsione (che sta volta albero non è ma è una lista) con 1 chiamata da logn.
l'altezza dell'albero è n , poichè ogni nodo va  n , n -1 , n-2 .. ecc .
in totale dovresti moltiplicare l'altezza(n) dell'albero per il costo del nodo (logn) quindi  O(nlogn)
ha dette bene!
dopo aver calcolato l'albero di ricorsione (parliamo di alberi completi) e il costo esterno ad ogni livello, devi confrontare il costo dell'ultimo livello con il costo della radice, quale dei due è asintoticamente più grande, è il costo dell'albero.
Se sono asintoticamente uguali devi calcolare la sommatoria del costo esterno di ogni livello.
come ha fatto Shiny...
Questo però vale solo per gli alberi completi!
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Pages: [1]   Go Up
Print
Jump to: