Passa al tema normale
Discussioni su argomenti di Informatica

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

Complessità algoritmi

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!)?

Re: Complessità algoritmi

14/06/2019, 15:52

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

Re: Complessità algoritmi

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..?
Rispondi al messaggio


Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000— Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.