Requisiti

• Pazienza
• Conoscenze matematiche medie
• Aver programmato
• Tanto tempo da perdere :P

Introduzione

Il mondo della programmazione è pieno di sfide che danno vita ad algoritmi più o meno efficienti.
Ma come si fa a stabilire quando un algoritmo è ottimale? Cercherò di spiegarlo rendendo il tutorial il più comprensibile e facile possibile.

Cos'è un algoritmo?

Un algoritmo è composto da una serie di passi (righe di codice) che risolvono un qualsiasi problema computazionale.
Che problema computazionale? Ordinamento di dati, gestione degli ordini di un sito di e-commerce, conversione di dati, ecc...
Ogni volta che sbattiamo la testa contro un problema esso sarà risolvibile tramite un algoritmo (più o meno banale).

1,2,3 via...

Uno dei problemi storici riguarda come ordinare n numeri memorizzati in un array o vettore.
Quando giochiamo a carte siamo abituati ad ordinare le carte che abbiamo in mano seguendo un determinato procedimento: ogni carta nuova che prendiamo con la mano destra, la inseriamo nella posizione corretta nel ventaglio di carte (che è già ordinato) che teniamo nell'altra mano.
Se decontestualizziamo questa nostra conoscenza abbiamo appena creato l'Insertion Sort (che usa appunto un approccio incrementale).
Il codice lo scriverò in Actionscript 1 perchè risulta molto simile allo pseudo-codice con cui andrebbero scritti gli algoritmi.

Se esaminate attentamente il codice noterete come segue alla lettera il procedimento di ordinamento delle carte.
L'indice i punta alla carta corrente (mano destra) che va messa nelle posizione giusta tra le carte già ordinate che vanno da 0 a i-1 (mano sinistra).
Le carte che sono ancora sul tavolo sono invece rappresentate dai numeri compresi tra i+1 e n.
Ogni algoritmo andrebbe studiato pensando a 3 diversi casi:

• Caso migliore
• Caso medio
• Caso peggiore

Tra questi 3 casi il più importante è quello peggiore che ci darà un indicazione precisa di come l'algoritmo se la caverà nella situazione meno conveniente (potendo quindi affermare che l'algoritmo non sarà più lento di così).
Limitatamente a questo algoritmo il caso peggiore l'abbiamo quando i numeri sono ordinati in maniera decrescente perchè il ciclo while interno eseguirà il massimo numero di iterazioni possibili (mentre quelle del ciclo for sono indipendenti dall'ordine dei numeri in input).
Se ad esempio prendiamo la sequenza 5,4,3,2,1 e la ordiniamo con Insertion Sort avremo 4 iterazioni del ciclo for e 10 totali (1+2+3+4) del ciclo while, mentre con la sequenza inversa (il caso migliore) avremo rispettivamente 4 e 0 iterazioni; una bella differenza no?
Vi anticipo quindi che l'algoritmo InsertionSort nel caso peggiore ha una complessità quadratica (n^2), mentre nel caso migliore sarà lineare (n).
EH, cosa?!?

Studio di complessità

Per studiare la complessità di un algoritmo viene associato un peso a ciascuna riga che viene poi moltiplicato per il numero di volte che essa viene eseguita.
Nella figura sottostante sono indicati i costi e il numero di iterazioni di ciascuna riga (da notare come nella testa di ogni ciclo ci sia un iterazione in più dovuta al controllo della guardia):

Non preoccupatevi, dopo aver visto una cosa simile mi era venuto l'istinto suicida anche a me ;)
Il costo complessivo dell'algoritmo è la somma del prodotto tra le costanti di riga e il numero di volte che la riga interessata viene eseguita, ottenendo quindi:

Per non appesantire il tutorial mi limito a dire che le costanti si possono tranquillamente ridurre ad una costante di massima, mentre la sommatoria, come alcuni di voi avranno notato, è la sommatoria aritmetica che trova la sua risoluzione nella formula (n^2-n)/2.
Nel caso peggiore avremo che Tj sarà proprio uguale a j (perchè ogni volta che inseriamo la carta nuova, dobbiamo traslarle tutte) portando l'algoritmo ad avere una complessità quadratica; mentre nel caso migliore il ciclo while interno non esegue alcuna iterazione rendendo la complessità lineare.
Dicendo "complessità quadratica" o "complessità lineare" indico la complessità in termini asintotici permettendo di valutare gli algoritmi indipendentemente dalla piattaforma di esecuzione (grazie alle costanti).

Morale

Lo scopo di questo tutorial non è quello di insegnare il calcolo della complessità di qualsiasi algoritmo (ci mancherebbe! mancano il 99,99% di cose da sapere:P) ma di portare alla luce aspetti che molto spesso sono ignorati: dietro a 11 semplici righe di codice a volte si possono nascondere calcoli matematici, studi, ottimizzazioni ed è buona cosa saperlo :)
Esistono una miriade di algoritmi di ordinamento (e con varie proprietà tipo in-place, stabile, ecc...) come ad esempio il Selection Sort (si spazzola ogni volta l'array per trovare il minimo inserendolo nella posizione corretta e rifacendo lo stesso procedimento n volte escludendo la parte già ordinata) che può essere scritto sia in versione iterativa che ricorsiva (dove la chiamata ricorsiva viene fatta su n-1 elementi).
Altri algoritmi di ordinamento possono far uso di strutture dati diverse come heap, alberi di ricerca bilanciati o meno, ecc...
Non esistono sono algoritmi basati sul confronto, ad esempio troviamo il Counting Sort, Radix Sort, Bucket Sort, ecc...
Insomma di algoritmi ne esistono a tonnellate (...di ordinamento, e gli altri? o_O) ognuno diverso dall'altro non solo in termini di complessità ma anche di implementazione e di spazio e sta a noi decidere quale sia il più adatto alle nostre esigenze.