-
AndreaDeDomenico+1
Like 
.User deleted
Nei giorni seguenti descriverò molti algoritmi interessanti, ma prima di farlo, è doverosa una guida per presentare le diverse classi di complessità che può avere un algoritmo (le più famose insieme ad alcuni esempi).
Con "classe di complessità" di un algoritmo, si intende in modo informale, di quanto cresce il tempo di esecuzione con l'aumento della dimensione dell'input (ordinare un array di 100 elementi è più veloce rispetto ad un ordinamento di 10000 elementi!)
Complessità sub-lineare
Algoritmi estremamente veloci, non daranno problemi di prestazioni anche con input molto grandi.
Complessità log(n) (logaritmica)
- L'algoritmo per la ricerca binaria ne è un esempio (in questo caso la base del logaritmo è 2). Non si specifica la base perché alla fine un logaritmo con base a è uguale ad un logaritmo con base b moltiplicato per una costante.
Complessità √(n)
- Ho visto pochi algoritmi con questa complessità, ad esempio l'algoritmo iterativo per sapere se un numero X appartiene all'insieme dei numeri primi.
Complessità polinomiale nk (k>=1)
Incontrerete spesso questi algoritmi nella vostra vita da programmatori
Complessità n (lineare)
- Tipica di algoritmi quali la ricerca lineare, algoritmi di ordinamento specializzati come il counting sort, ecc.
Complessità n*log(n) (pseudo-lineare)
- Si vede spesso studiando algoritmi risolvibili col paradigma Divide et impera, come nei celeberrimi Merge-sort e Quick-sort. Anche l'Heap-sort appartiene a questo livello di complessità.
Non a caso, gli algoritmi di ordinamento generici non possono avere una complessità minore di questa
Complessità n2 (quadratica)
- Spesso un algoritmo quadratico è sintomo di un algoritmo implementato male che potrebbe essere risolto con metodi più efficaci (si pensi ad esempio al Bubble-sort); hanno però il pregio di essere facili da capire ed implementare.
Alcuni algoritmi sui grafi hanno complessità (non migliorabile) quadratica, ma non è ancora il momento di parlarne
Complessità n3 (cubica)
- La moltiplicazione di due matrici quadrate usando un algoritmo intuitivo ha complessità cubica.
Ovviamente l'esponente di n non si limita a questi valori, un algoritmo migliore per moltiplicare due matrici quadrate per esempio ha complessità nlog27, anche se nella pratica è poco usato.
Complessità non polinomiale
I famigerati problemi NP, la cui soluzione ottima è troppo lenta, contro i quali spesso facciamo uso di algoritmi più veloci ma che spesso non ci danno la risposta migliore (euristici).
Complessità kn (esponenziale)
- Ogni algoritmo che risolve un problema NP; come il problema del commesso viaggiatore, colorazione vertici di un grafo, ecc.
Complessità n! (fattoriale)
- Complessità che di solito si ottiene cercando di risolvere un problema usando la forza bruta (talvolta per la forza bruta si ha anche complessità esponenziale)
Casi estremi
Vale la pena menzionare le operazioni superesponenziale e superlogaritmo (operazione inversa della prima).
un superesponenziale è una potenza applicata più volte. Esempi:
33 = 333 = 7625597484987
42 = 2222 = 65536
La crescita del superesponenziale/superlogaritmo come potete intuire è spaventosamente alta/bassa.
funzione di ackermann
Io la chiamo anche "il mostro".
La funzione è così definita:
Anche se la formula non vi dirà molto a prima vista, vi basti sapere che la sua crescita è infinitamente più alta della funzione superesponenziale.
Purtroppo non posso farvi vedere nessun grafico di questa funzione (lo stesso vale per superesponenziali e superlogaritmi); sappiate però che esiste un utilissimo algoritmo la cui complessità è collegata a questa funzione.
Per il momento non vi dico altro, spero di avervi chiarito le idee ed allo stesso tempo avervi fatto incuriosire, approfondirò l'argomento nei prossimi articoli, stay tuned
. -
.
Fai pena e pietà. .
Classi di complessità |
Offline