Pages: [1]   Go Down
Print
Author Topic: Dubbio sulla sommatoria  (Read 714 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
the doctor 46
Matricola
*
Offline Offline

Posts: 31


« on: 20-02-2011, 20:26:18 »

Salve,

vorrei capire come si svolge passo passo questo tipo di sommatoria :

T(n) = \sum_{i=0}^{log(n)} 2^i (log(n-i))

Grazie.
Logged
kruger
Matricola
*
Offline Offline

Gender: Male
Posts: 47


benvenuti nel mio incubo...


WWW
« Reply #1 on: 20-02-2011, 21:31:20 »

ti basta notare che è una serie geometrica con ragione = 2 (che è maggiore di 1): quindi, essendo che tale serie diverge all'infinito, puoi porre come bound O(2n), senza bisogno di risolverla passo passo

Saluti  yoh
Logged

Il vero signore è lento nel parlare e rapido nell'agire
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #2 on: 20-02-2011, 21:58:17 »

ti basta notare che è una serie geometrica con ragione = 2 (che è maggiore di 1): quindi, essendo che tale serie diverge all'infinito, puoi porre come bound O(2n), senza bisogno di risolverla passo passo

Saluti  yoh
Non mai letto qualcosa di piu' sbagliato  testate... da quando

T(n) = \sum_{i=0}^{\log(n)}\ 2^i (\log(n-i))

e' lontanamente simile alla serie geometrica (\sum_{i=0}^{n} 2^i)?

Inoltre \sum_{i=0}^{n} 2^i\ =\ \frac{1-2^{n+1}}{1 - 2} (diverge solo per un numero infinito di termini)

Salve,

vorrei capire come si svolge passo passo questo tipo di sommatoria :

T(n) = \sum_{i=0}^{log(n)} 2^i (log(n-i))

Grazie.

Da dove ti e' uscita una tale serie?
Cmq ho provato ad approssimarla con gli integrali e ho trovato che una tale funzione non e' integrabile numericamente e per risolvere quell'integrale si usa questa funzione in sostituzione.

« Last Edit: 20-02-2011, 22:03:43 by shiny » Logged
kruger
Matricola
*
Offline Offline

Gender: Male
Posts: 47


benvenuti nel mio incubo...


WWW
« Reply #3 on: 22-02-2011, 10:28:47 »

ti basta notare che è una serie geometrica con ragione = 2 (che è maggiore di 1): quindi, essendo che tale serie diverge all'infinito, puoi porre come bound O(2n), senza bisogno di risolverla passo passo

Saluti  yoh
Non mai letto qualcosa di piu' sbagliato  testate... da quando

T(n) = \sum_{i=0}^{\log(n)}\ 2^i (\log(n-i))

e' lontanamente simile alla serie geometrica (\sum_{i=0}^{n} 2^i)?

Inoltre \sum_{i=0}^{n} 2^i\ =\ \frac{1-2^{n+1}}{1 - 2} (diverge solo per un numero infinito di termini)

Salve,

vorrei capire come si svolge passo passo questo tipo di sommatoria :

T(n) = \sum_{i=0}^{log(n)} 2^i (log(n-i))

Grazie.

Da dove ti e' uscita una tale serie?
Cmq ho provato ad approssimarla con gli integrali e ho trovato che una tale funzione non e' integrabile numericamente e per risolvere quell'integrale si usa questa funzione in sostituzione.



Chiedo umilmente scusa... 

comunque credo sia uscita da una ricorrenza come

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

almeno così mi pare di capire dalla sommatoria se si sviluppa l'abero di ricorsione...
Logged

Il vero signore è lento nel parlare e rapido nell'agire
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #4 on: 22-02-2011, 15:12:42 »

Intanto la somma che ti esce fuori e' questa:

T(n) = \sum_{i=0}^{n-1}\ 2^i \log(n-i) (l'altezza dell' albero e' n-1)
 
e l'ho risolta cosi'

T(n)\ =
               \sum_{i=0}^{n-1}\ 2^i\ \log(n-i)\ \leq\

               \sum_{i=0}^{n-1}\ 2^i\ (n-i)\ \ \ \ \leq\

               \int_{0}^{n}\ 2^x\ (n-x)\ dx\ \ \ =\

               \frac{1}{ln2}( 2^n - 2n + 1) \ =\ O(2^n)

P.s. l'integrale l'ho risolto a mente per parti quindi potrebbero esserci degli errori
« Last Edit: 22-02-2011, 15:44:04 by shiny » Logged
Pages: [1]   Go Up
Print
Jump to: