Complessità

Nella terminologia degli algoritmi di ordinamento, aumentare l'efficienza significa ridurre la complessità di un algoritmo. Meno è complesso l'algoritmo, più sarà efficiente.

Minore complessità -> Maggiore efficienza

Nella definizione di complessità, dobbiamo fare riferimento come sempre ai due componenti fondamentali di un sistema di elaborazione:

• processore (CPU)
• memoria primaria (RAM)

Ridurre la complessità relativa alla CPU significa riuscire ad arrivare allo stesso risultato (l'array ordinato) con meno operazioni, e quindi in meno tempo. Questo tipo di complessità viene quindi detta computazionale o temporale.

Ridurre la complessità relativa alla RAM significa occupare meno "spazio" in memoria RAM possibile, quindi viene detta anche complessità spaziale.

Misura della complessità

Quando calcoliamo la complessità temporale o spaziale, non ci interessa avere il numero esatto di operazioni o l'esatta quantità di memoria occupata, ma ci basta sapere "più o meno" quanto tempo ci metterà e quanta memoria occuperà. Questo valore approssimato viene detto ordine di grandezza. Esiste una simbologia specifica che serve ad indicare l'ordine di grandezza, ed è la notazione O-grande, che si scrive O(n).

Ad esempio, immaginiamo che, per un'attività didattica, al professore servano degli smartphone e li chieda agli studenti della classe. Quanti smartphone più o meno si può aspettare di trovare in classe? Possiamo ipotizzare che ogni studente avrà il proprio dispositivo (alcuni forse ne avranno due, alcuni nessuno), quindi l'ordine di grandezza del numero di smartphone è circa pari a quello degli studenti. Se gli studenti sono un numero n (es. 20), i dispositivi nella classe saranno anch'essi circa n. In questo caso si dice che il numero di smartphone nella classe è O(n) (si legge "o di enne"), dove n è il numero di studenti.

Immaginiamo ora di voler organizzare un torneo di ping pong tra gli studenti di una classe. Vogliamo che tutti gli studenti giochino contro tutti gli altri studenti. Quante partite dovremo pianificare, più o meno? Se ci sono n studenti ed ognuno deve fare circa n partite, il numero di partite è (circa) n * n = n². In notazione O grande, si dice che il numero di partite è O(n²). Anche qui il numero di partite non sarà esattamente n², ma a noi serve sapere una stima approssimativa.

Complessità computazionale (o temporale)

Tornando al grafico del selection sort, abbiamo visto che il tempo necessario per l'ordinamento va come il quadrato del numero di elementi da ordinare. Se indichiamo con n il numero di elementi della lista, possiamo quindi dire che:

tempo di ordinamento selection sort = O(n²)

con n = numero di elementi della lista.

Il nostro obiettivo sarà trovare degli algoritmi che abbiano una relazione tra tempo e numero di elementi più vantaggiosa.

Complessità spaziale

Con la nostra implementazione del selection sort, in memoria RAM ci serve l'array sorted_list della stessa grandezza dell'array di partenza. La complessità spaziale è quindi:

O(n)

Questa complessità è buona, e non possiamo ottenere ordini di grandezza migliori.

Ciò non toglie che possiamo comunque "limare" la nostra soluzione per guadagnare un po' di memoria. Lo vedremo nella prossima pagina.