9 : Analisi degli Algoritmi Vers . 2.0 – Aprile 2022
Esempio : Se T ( N ) = 2N 2 + 5 essendo comportamenti asintotici ossia all ’ infinito risultano irrilevanti ai fini della determinazione dell ’ ordine di grandezza sia la costante 5 sia la costante moltiplicativa 2 . Ciò che interessa è dunque il termine N 2 . perché formalmente
= costante
Quindi programmi ed algoritmi saranno valutati confrontando la loro funzione T ( N ) e tralasciando le loro costanti di proporzionalità .
Pertanto :
- algoritmi con funzioni di complessità N , 2N , 3N oppure 2N + 3 , 2N + 200 , 3N + 4000 sono tutti O ( N ) ossia sono proporzionali al funzione g ( N ) = N ;
- algoritmi con funzioni di complessità 5N 2 , 8N 2 + 67 , 19N 2 + 67N + 2 sono tutti O ( N 2 ) ossia sono proporzionali al funzione g ( N ) = N 2
CLASSI DI COMPUTABILITA ’
E ’ possibile individuare alcuni ordini di grandezza per le funzioni T ( N ) che individuano le cosiddette classi di complessità o di computabilità degli algoritmi :
1 ) complessità COSTANTE O ( 1 ) oppure O ( C ): indica la complessità degli algoritmi che eseguono sempre lo stesso numero di operazioni indipendentemente dalla dimensione dei dati di input ( ad esempio algoritmi senza cicli );
2 ) complessità LOGARITMICA O ( logN ): indica la complessità degli algoritmi che eseguono un numero di operazioni proporzionale a logN ( ad esempio algoritmo di ricerca binaria );
3 ) complessità LINEARE O ( N ): indica la complessità degli algoritmi che eseguono un numero di operazioni proporzionale a N ( ad esempio algoritmo di ricerca sequenziale , algoritmo di caricamento degli elementi di un vettore , algoritmo di stampa degli elementi di un vettore );
4 ) complessità PSEUDOLINEARE O ( N logN ): indica la complessità della maggior parte degli algoritmi di ordinamento esistenti ( ad esempio l ’ algoritmo di MergeSort ha in tutti i casi ordine di complessità proporzionale ad N logN );
5 ) complessità POLINOMIALE O ( N K ): indica la complessità degli algoritmi che hanno complessità pari alla potenza K-sima della dimensione del problema . Se K = 2 si parla di complessità quadratica ( ad esempio l ’ algoritmo di ordinamento BubbleSort ), se K = 3 di complessità cubica ( ad esempio l ’ algoritmo di moltiplicazione tra due matrici quadrate di dimensione N );
6 ) complessità ESPONENZIALE O ( K N ): indica la complessità degli algoritmi che hanno complessità pari alla potenza che ha come esponente la dimensione del problema ( ad esempio l ’ algoritmo che produce tutte le possibili stringhe di lunghezza P su di un alfabeto di 10 simboli ).
I problemi con complessità al più polinomiale si definiscono TRATTABILI ; I problemi con complessità almeno esponenziale si definiscono INTRATTABILI
Le classi di complessità dal punto di vista matematico sono classi di equivalenza generate dalla relazione di equivalenza dell ’ ordine di grandezza . Quindi tutti gli algoritmi che hanno lo stesso ordine di grandezza T ( N ) ossia hanno la stessa classe di complessità appartengono alla stessa classe di equivalenza .
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 11