Pagina 1 di 1

Complessità algoritmi

MessaggioInviato: 14/06/2019, 16:33
da ludovica_97
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!)?

Re: Complessità algoritmi

MessaggioInviato: 14/06/2019, 16:52
da caulacau
Beh, \(\log (n!) = \sum_{k=2}^n \log k\). Ora per stimare questo... che idee hai?

Re: Complessità algoritmi

MessaggioInviato: 15/06/2019, 08:36
da ludovica_97
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..?