Complessità computazionale delle quattro operazioni

Ingegneria di Antonio Parziale guida dal 29-06-2004

Popolarità:

economia news e media viaggi informatica internet salute e benessere int rattenimento e spettacolo sport tempo libero istruzio ne e formazione arte cultura scienza

Le categorie della guida

I link preferiti della guida

Il Sondaggio

Ti sei iscritto a:

Guarda i risultati

Appunti Informatica

A cura di Antonio Parziale

Pubblicato il 04/07/2005

» Invia tramite EMAIL

» Versione per la STAMPA

» Le vostre opinioni

Il calcolo della complessità computazionale per le quattro operazioni base usando algoritmi classici su n bit. L'articolo è tratto dalla tesi di laurea in "Applicazione delle tecniche di crittografia nella trasmissione ed elaborazione dati" redatta dall'ingegnere Federico Gennari nell'anno accademico 2000/2001.

Siano a e b due interi non negativi, ognuno minore o uguale ad n . Ricordiamo che il numero di bit (cifre binarie) nella rappresentazione binaria di n è circa log₂ n. Il numero di operazioni su bit per le quattro operazioni base usando gli algoritmi classici sono elencati nella tabella sottostante.

Operazione su bit	Complessità
Addizione a+b	O(lg a + lgb) =O(lg n)
Sottrazione a-b	O(lg a + lgb) =O(lg n)
Moltiplicazione ab	O((lg a)(lg b)) = O((lg n) 2 )
Divisione a =q b + r	O((lg q)(lg b)) = O((lg n) 2 )

I link correlati all'argomento

Feed