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

Posts: 262



« on: 02-12-2010, 17:55:29 »

ragazzi come risolvereste questa eq. di ricorrenza?

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

grazie in anticipo

ps io ho provato con il telescoping e mi viene n2
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #1 on: 02-12-2010, 18:55:29 »

da quella equazione di ricorrenza hai
\sum_{i=1}^n \log i\ \leq\ n\log n
e quindi la complessita' e' O(n\log n)
Logged
KingDavid
Forumista
***
Offline Offline

Posts: 788


Alla fine [...] tutta la realtà è binaria.


« Reply #2 on: 02-12-2010, 19:12:19 »

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

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

T(n-2)=T(n-3) + log (n -2)

.....
T(n- (n-1))=T(n- (n-1) - 1) + log (n - (n-1)) = T(0) +log 1 = 0

In pratica hai che:

T(n) =  \sum_{i=1}^n \log i\ =   O(nlogn)*


* = in virtù da quanto detto da shiny
« Last Edit: 02-12-2010, 19:23:57 by KingDavid » Logged

Basti pensare che un ipotetico quadrato di specchi, lungo 200 chilometri per ogni lato, potrebbe produrre tutta l'energia necessaria all'intero pianeta.
(Carlo Rubbia)
francesco85
Apprendista Forumista
**
Offline Offline

Posts: 262



« Reply #3 on: 02-12-2010, 20:17:36 »

grazie ragazzi
Logged
Pages: [1]   Go Up
Print
Jump to: