Complessità algoritmi
Inviato: 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!)?
$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!)?