COMPLESSITA' DEGLI ALGORITMI
Il
\mathit{“costo”} dell'esecuzione di un algoritmo dipende non solo dalla dimensione dei dati in Input, ma anche da quanto è “disordinato” il vettore da ordinare. Infatti, se il vettore è già ordinato (o quasi), terminano in breve tempo, mentre se è "molto disordinato" devono eseguire molti più passi.
Si distinguono tre casi: caso peggiore, caso medio e caso migliore.
La ricerca e l'ottimizzazione di algoritmi di ordinamento è molto importante in ambito informatico e per queste classi di algoritmi sono stati dimostrati svariati teoremi che ne definiscono i limiti. Il più importante è il seguente:
Teorema del LOWER BOUND: La complessità in tempo di un qualsiasi algoritmo di ordinamento basato su confronti è di almeno
\Omega(n log n) [cioè deve effettuare almeno (n log n) confronti], dove n è il numero di elementi da ordinare.
| ALGORTIMO |
CASO MIGLIORE |
CASO MEDIO |
CASO PEGGIORE |
| Ordinamento Ingenuo |
O(n^2) |
O(n^2) |
O(n^2) |
| Selection Sort |
O(n) |
|
O(n^2) |
| Bubble Sort |
O(n) |
|
O(n^2) |
| Counting Sort |
O(n) |
O(n) |
O(n) |
| Quick Sort |
O(n log n) |
O(n log n) |
O(n^2) |
| Merge Sort |
O(n log n) |
O(n log n) |
O(n log n) |
CLASSI DI COMPLESSITA’
1) Complessità
costante: O(1)
È posseduta dagli algoritmi che eseguono sempre lo stesso numero di operazioni indipendentemente dalla dimensione dei dati.
Es.: inserimento o estrazione dalla testa di una lista concatenata, ecc.
2) Complessità
sottolineare: O(n ), con k<1
Es.:Ricerca binaria, o logaritmica, ecc.
3) Complessità
lineare: O(n)
È posseduta dagli algoritmi che eseguono un numero di operazioni sostanzialmente proporzionale ad n.
Es.: ricerca sequenziale, somma di numeri di n cifre, merge di due file, ecc.
4) Complessità
n log n: O(n log n)
E’ la più ottimale complessità che gli algoritmi di ordinamento possono raggiungere.
5) Complessità
quadratica n^ k , con k>=2: O(
n^k )
Es.: Bubblesort ( O(n^2) ), moltiplicazione di due 2 matrici ( O(n^3) ), ecc.
6) Complessità fattoriale
7) Complessità
esponenziale
Tutte le classi di complessità elencate precedentemente vengono genericamente considerate come polinomiali. Esse sono caratterizzate dal fatto che la dimensione n non compare mai come esponente in alcun modo. Quando ciò avviene si parla invece di complessità esponenziale.
Es.: un algoritmo che debba produrre tutte le possibili stringhe lunghe n di k simboli avrà complessità O(k^n) cioè esponenziale.
L'algoritmo della Torre di Hanoi ha complessità O(2^n) (sono necessarie 2^{n-1} mosse).
È necessario guardare con particolare diffidenza agli algoritmi dotati di complessità esponenziale, perché possono richiedere dei tempi di esecuzione proibitivi (se non addirittura astronomici) anche per valori relativamente piccoli di n ed indipendentemente dalla velocità dell'elaboratore.
Purtroppo esistono molti problemi, anche di interesse pratico, per i quali non si conoscono ancora algoritmi non esponenziali (problemi intrattabili). Es.: problema del commesso viaggiatore.
Un problema è computazionalmente
trattabile se esiste un algoritmo efficiente che lo risolve; altrimenti il problema è computazionalmente intrattabile.
Un algoritmo si dice
efficiente se il suo tempo di esecuzione è limitato superiormente da una funzione polinomiale (funzione limitata superiormente da
n^k per un opportuno fissato intero k).
Torna a Programmazione e Lab.
Non ci sono commenti in questa pagina. [Scrivi commento]