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

Posts: 232



« on: 07-12-2012, 12:06:58 »

Salve a tutti,
Stamani esercitandomi mi sono imbattuto in questo interessante esercizio:
Code:
T(n)=T(n-1)+log n

Ho pensato di risolverlo con il metodo dell'albero di ricorsione (Dato anche che non mi è troppo chiaro, un modo quindi per capirlo più a fondo)

Ho creato quindi l'albero:
Code:
log n ----------------------------------------> log (n)                            |
    |                                                                                                     |
    |                                                                                                     |
    |                                                                                                     |
log (n-1) ------------------------------------> log (n-1)                       |
    |                                                                                                     |
    |                                                                                                     |            h=n-1
    |                                                                                                     |
log (n-2) -------------------------------------> log (n-i)                       |
    |                                                                                                     |
    |                                                                                                     |
    |                                                                                                     |
  T(1) -----------------------------------------> [tex]\Theta (1)[/tex]     +

Ecco alcune mie considerazioni (spero esatte):
- Per ogni livello i abbiamo una sola chiamata, con costo log (n-i)
- All'ultimo livello avremo log (n-i)=1, da cui credo che i=n-2
- Quindi in totale n-1 livelli, considerando la presenza della radice al livello 0
- Sempre all'ultimo livello abbiamo una chiamata, di costo T(1), cioè: log (n-(n-2)) =\Theta (1)

Provo a sommare i costi:
\sum_{i=0}^{log (n-1)} log (n-i) + \Theta (1)
Il che, intuitivamente, mi suggerirebbe di rispondere con T(n)=O(log n)

Spero qualcuno possa dargli un'occhiata e dirmi eventualmente dove sbaglio
Grazie anticipatamente
Logged
Andrea2990
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 235



WWW
« Reply #1 on: 07-12-2012, 12:23:38 »

Io l'avrei fatto col telescoping...
Logged
Il Capitano
Apprendista Forumista
**
Offline Offline

Posts: 409


« Reply #2 on: 07-12-2012, 12:34:08 »

Io l'avrei fatto col telescoping...
Potresti spiegarmi come fare con il telescoping? Grazie
Logged
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #3 on: 07-12-2012, 15:46:01 »

Io l'avrei fatto col telescoping...
Potresti spiegarmi come fare con il telescoping? Grazie

Vi do un consiglio guardate i vecchi post

POST
Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
Andrea2990
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 235



WWW
« Reply #4 on: 08-12-2012, 21:40:45 »

Sottolineo che non sono un esperto della materia, la sto studiando senza averla seguita.

TELESCOPING
T(n)=T(n-1)+f(n) ---> T(n)=sommatoria per i=1->n di f(i)

Nel nostro caso
T(n)=T(n-1)+log(n) ---> T(n)=sommatoria per i=1->n di log(i)

sommatoria per i=1->n di log(i) = log(1)+log(2)+log(3)+...+log(n)= numeri vari + log(n)

Tra i numeri vari e log(n) prendiamo log(n) perché è più grande.
Quindi T(n)=theta(log(n))

Almeno, credo che sia così, ma non ti fidare.
« Last Edit: 08-12-2012, 21:42:37 by Andrea2990 » Logged
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #5 on: 10-12-2012, 15:13:07 »

Sottolineo che non sono un esperto della materia, la sto studiando senza averla seguita.

Io da quello che vedo in questo post non sei esperto nemmeno di latex, visto che hai scritto le formule in quel modo.

Comunque si devi risolvere quella sommatoria \sum_{i=0}^n log(n) che ha come risultato \Theta(log(n))

E in futuro se vuoi che un collega ti aiuti a risolvere un problema guardati la guida in latex
Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
Vincenzo Cutello
Administrator
Forumista
*****
Offline Offline

Gender: Male
Posts: 600


« Reply #6 on: 11-12-2012, 11:37:34 »

Sottolineo che non sono un esperto della materia, la sto studiando senza averla seguita.

Io da quello che vedo in questo post non sei esperto nemmeno di latex, visto che hai scritto le formule in quel modo.

Comunque si devi risolvere quella sommatoria \sum_{i=0}^n log(n) che ha come risultato \Theta(log(n))

E in futuro se vuoi che un collega ti aiuti a risolvere un problema guardati la guida in latex
Tu sei sicuro che  \sum_{i=0}^n log(n)=\Theta(log(n)) ?
Logged
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #7 on: 11-12-2012, 15:13:32 »

Sottolineo che non sono un esperto della materia, la sto studiando senza averla seguita.

Io da quello che vedo in questo post non sei esperto nemmeno di latex, visto che hai scritto le formule in quel modo.

Comunque si devi risolvere quella sommatoria \sum_{i=0}^n log(n) che ha come risultato \Theta(log(n))



E in futuro se vuoi che un collega ti aiuti a risolvere un problema guardati la guida in latex
Tu sei sicuro che  \sum_{i=0}^n log(n)=\Theta(log(n)) ?

ops mea culpa dovevo scrivere \sum_{i=1}^n log(i) errore di copia e incolla  testate

come l'avevo scritto io dava come risultato nlog(n)
« Last Edit: 11-12-2012, 15:15:11 by corel_86 » Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
Andrea2990
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 235



WWW
« Reply #8 on: 11-12-2012, 17:53:45 »

Quote
io da quello che vedo in questo post non sei esperto nemmeno di latex, visto che hai scritto le formule in quel modo.
[...]
E in futuro se vuoi che un collega ti aiuti a risolvere un problema guardati la guida in latex

Scusate, non sapevo nemmeno dell'esistenza del LATEX.

In ogni caso, a mio modo, seppur sbagliando nella forma, ho cercato di aiutare qualcuno.
Comunque, mi rincuora il fatto che almeno il risultato sia giusto.
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #9 on: 11-12-2012, 18:46:02 »

Sottolineo che non sono un esperto della materia, la sto studiando senza averla seguita.

TELESCOPING
T(n)=T(n-1)+f(n) ---> T(n)=sommatoria per i=1->n di f(i)

Nel nostro caso
T(n)=T(n-1)+log(n) ---> T(n)=sommatoria per i=1->n di log(i)

sommatoria per i=1->n di log(i) = log(1)+log(2)+log(3)+...+log(n)= numeri vari + log(n)

Tra i numeri vari e log(n) prendiamo log(n) perché è più grande.
Quindi T(n)=theta(log(n))

Almeno, credo che sia così, ma non ti fidare.
Andrea potresti scriverla meglio? magari in un foglio e lo posti..
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.475


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #10 on: 11-12-2012, 23:48:52 »

Quote
[...]
ops mea culpa dovevo scrivere Σi=1n(log (i)) errore di copia e incolla  testate

come l'avevo scritto io dava come risultato n log(n)
Non ho seguito l'intera discussione, ma faccio notare che:

\fs{4}\sum_{i=1}^n{\log{\({i}\)}}=\log(1)+\log(2)+\cdots+\log(n)=\log{\({1\cdot 2\cdot\cdots n}\)}=\log{\({n!}\)} < n\log{\({n}\)}=\log{\({n^n}\)}
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Andrea2990
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 235



WWW
« Reply #11 on: 12-12-2012, 08:56:40 »

Io sapevo che \Theta(\log(n!))=\Theta(n*\log(n))
quindi dovrebbe dare \Theta(n*\log(n))
a questo punto...
Logged
Twitch
Apprendista Forumista
**
Offline Offline

Posts: 183


Orange Moka Frappucinoooo!!!


« Reply #12 on: 12-12-2012, 09:22:55 »

Io l'avrei fatto col telescoping...

Esatto! Io anche l'ho risolta con il telescoping:

\sum_{i=1}^n \log( i ) = \Theta ( n log n )

In quanto la sommatoria è riconducibile alla serie Armonica.

Spero di non aver detto boiate e di non aver fatto casini con il latex  pc
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #13 on: 12-12-2012, 10:06:01 »

Io l'avrei fatto col telescoping...

Esatto! Io anche l'ho risolta con il telescoping:

sum_{i=1}^n log( i ) = Theta ( n log n )

In quanto la sommatoria è riconducibile alla serie Armonica.

Spero di non aver detto boiate e di non aver fatto casini con il latex  pc
Potresti scrivere i passaggi?Te ne sarei grato.
Logged
Pages: [1]   Go Up
Print
Jump to: