Complessità algoritmi

Messaggioda ludovica_97 » 14/06/2019, 15:33

Buonasera, sto studiando per l'esame di crittografia e devo imparare il calcolo della complessità di diversi algoritmi. Ho problemi con:
$n! $
Crivello di Eratostene
$b^m(modn) $
Algoritmo dei passi da bambino e da gigante
Andiamo per gradi e iniziamo dal primo.
Allora io so che devo contare il numero di operazioni elementari quindi, prendiamo ad esempio, $n! $
Questo consiste di operazioni del tipo $j! (j+1)$ con j<n
Quindi basta calcolare la complessità di ogni operazione di questo tipo e poi moltiplicarla per n perché va fatta n volte. Il problema in un calcolo di questo tipo è che sto facendo una moltiplicazione che ha quindi complessità o(log(j!) log(j+1)) ma quanto vale effettivamente log(j!)?
ludovica_97
Average Member
Average Member
 
Messaggio: 252 di 582
Iscritto il: 18/02/2017, 16:53

Re: Complessità algoritmi

Messaggioda caulacau » 14/06/2019, 15:52

Beh, \(\log (n!) = \sum_{k=2}^n \log k\). Ora per stimare questo... che idee hai?
Avatar utente
caulacau
Junior Member
Junior Member
 
Messaggio: 55 di 466
Iscritto il: 08/05/2019, 18:30

Re: Complessità algoritmi

Messaggioda ludovica_97 » 15/06/2019, 07:36

caulacau ha scritto:Beh, \(\log (n!) = \sum_{k=2}^n \log k\). Ora per stimare questo... che idee hai?


Be dovrei stimare la complessita' della somma che quindi e' la lunghezza del numero piu' grande..?
ludovica_97
Average Member
Average Member
 
Messaggio: 253 di 582
Iscritto il: 18/02/2017, 16:53


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite