Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: rondey on 20-03-2012, 12:18:48



Title: Classificazione complessità asintotica: lg(n!) o (lg(n))! ?
Post by: rondey on 20-03-2012, 12:18:48
Salve a tutti, premesso che ho cercato con la funzionalità "search" del forum e mi pare di non aver ritrovato soluzione a questo problema.

La domanda è: fra lg(n!) o (lg(n))! chi dei due è più grande? E soprattutto per quale motivo?

A chi saprà rispondere correttamente alla domanda verrà eretta in suo onore una statua all'entrata del dipartimento  :pray


Title: Re:Classificazione complessità asintotica: lg(n!) o (lg(n))! ?
Post by: cock86 on 20-03-2012, 12:42:25
La seconda. E mi spiego:

log(n!)=log(n * (n-1) * (n-2) * ... * log(2) * log(1))=log(n) + log(n-1) + log(n-2) + ... + log(2) + log(1)

che cresce più lentamente di

(log(n))!=log(n) * log(n)-1 * log(n)-2 * ... * 2 * 1

quindi possiamo dire che
log(n!)<=(log(n))!


mmm di preciso dov'è che metti la statua!!!


Title: Re:Classificazione complessità asintotica: lg(n!) o (lg(n))! ?
Post by: rondey on 20-03-2012, 15:46:37
log(n) + log(n-1) + log(n-2) + ... + log(2) + log(1)

Ecco perchè non mi risultava! al posto della somma mi ostinavo a metterci il prodotto!!! :-)|

mmm di preciso dov'è che metti la statua!!!

Pensavo di metterla nella stanza più frequentata dell'intera università: la sala dove ci sono le macchinette del caffè e i ditributori automatici.  :[Emoticon] Asd:

[Fonte: Camera Cafè]

Grazie per l'aiuto


Title: Re:Classificazione complessità asintotica: lg(n!) o (lg(n))! ?
Post by: cock86 on 20-03-2012, 16:02:18
Quote
Pensavo di metterla nella stanza più frequentata dell'intera università: la sala dove ci sono le macchinette del caffè e i ditributori automatici.
ahahah non vedo l'ora  .wink
figurati!!!