Notazione Big O per calcolare la complessità di un algoritmo
Come fai a sapere se un algoritmo rappresenta la soluzione migliore ad un problema? Come fai a stabilire se un algoritmo è più veloce di un altro? Come fai a capire se una nuova implementazione migliora una implementazione precedente dell'algoritmo?
Per rispondere alle precedenti domande, la notazione Big O viene in tuo aiuto.
Quando si parla di efficienza degli algoritmi, si considera l'esecuzione degli stessi su un numero molto grande di dati in input. Prendendo come esempio dell'ordinamento dei numeri, non ha molto senso considerare l'efficienza degli algoritmi per un input di 10 numeri, poiché, in questo caso, le prestazioni saranno equivalenti ed impercettibili anche comparando algoritmi con diverse prestazioni. Tuttavia se aumentiamo il nostro input a un milione di elementi vedrai che un algoritmo efficiente può ordinare i numeri in un paio di secondi mentre un algoritmo mal progettato può metterci fino ad un paio d'ore!
La notazione Big O è utilizzata per quantificare le prestazioni degli algoritmi all'aumentare della dimensione dell'input. La notazione è una delle metodologie più utilizzate per condurre l'analisi del caso peggiore.
Complessità costante: O(1)
Un algoritmo che impiega la stessa quantità di tempo di esecuzione indipendentemente dalla dimensione dell'input, si dice che è eseguito a tempo costante. Un tale algoritmo è etichettato con la notazione O(1).
Prendiamo ad esempio l'accesso all'ennesimo elemento di una lista (o array). In questo caso, il tempo impiegato per accedere l'elemento è indipendente dalla dimensione della lista ed è costante. Se devo accedere il quinto elemento di una lista, non è importante il numero di elementi che compongono la lista stessa. Il tempo che impiego per prelevare l'elemento è lo stesso sia che la lista è composta da dieci elementi o da un milione di elementi.
La seguente funzione preleva l'elemento ennesimo, specificato dall'indice ricevuto come parametro:
def getElemento(elementi, indice):
return elementi[indice]
La funzione ha complessità O(1).
Complessità lineare: O(n)
Un algoritmo ha una complessità lineare O(n) quando il tempo di esecuzione è direttamente proporzionale alla dimensione dell'input.
Un esempio di tale algoritmo è rappresentato dalla somma dei numeri presenti all'interno di una lista. La seguente funzione consente la somma dei numeri della lista:
def somma_numeri(numeri):
somma = 0
for numero in numeri:
somma += numero
return somma
Nella precedente funzione puoi notare che il numero di cicli necessari per completare l'operazione dipende fortemente dal numero di elementi presenti nella lista e quindi cresce al crescere di n, per tale motivo la complessità è O(n).
Richiamando la funzione con una lista di 100 numeri:
somma_numeri([x for x in range(1,100)])
l'esecuzione dura 0,03 secondi.
Richiamando la funzione con una lista di 100 milioni di numeri:
somma_numeri([x for x in range(1,100000000)])
l'esecuzione dura 8,36 secondi.
Complessità quadratica: O(n²)
Un algorimo ha complessità quadratica quando il tempo di esecuzione è proporzionale al quadrato della dimensione dell'input.
Un esempio di algoritmo di questo tipo può essere rapprensentato dalla somma degli elementi di una matrice. Data quindi una matrice come la seguente:
Per ottenere la somma di tutti gli elementi devo sommare gli elementi della prima riga, poi quelli della seconda, poi quella della terza, e così via.
La seguente funzione prevede il calcolo della somma descritta:
def somma_numeri_matrice(matrice):
somma = 0
for riga in matrice:
for numero in riga:
somma += numero
return somma
L'esecuzione della funzione, considerando 100 righe, in base al numero delle colonne come segue:
- 10 colonne: 0.0483989715576171875000 ms
- 100 colonne: 0.4160404205322265625000 ms
- 1.000 colonne: 4.2369365692138671875000 ms
- 10.000 colonne: 46.0922718048095703125000 ms
- 100.000 colonne: 472.9101657867431640625000 ms
- 1.000.000 colonne: 4618.2262897491455078125000 ms
Come si nota la crescita è esponenziale al crescere dell'input.
Complessità logaritmica: O(log n)
Un algoritmo è definito di complessità logaritmica quando il tempo di esecuzione dell'algoritmo è proporzionale al logaritmo della dimensione dell'input. Negli algoritmi di questo tipo, ad ogni iterazione, la dimensione dell'input diminuisce di un fattore multiplo costante.
Un esempio di algoritmo di questo tipo è la ricerca binaria; l'algoritmo cerca all'interno di una struttura dati unidimensionale (una lista python) un determinato elemento. Gli elementi nella lista devono essere ordinati in ordine decrescente.
La seguente funzione implementa la ricerca binaria in Python su una lista:
def binary_search(elements, target):
first = 0
last = len(elements) - 1
found = False
while(first <= last and not found):
middle = (first + last) // 2
if elements[middle] == target:
found = True
else:
if target < elements[middle]:
last = middle - 1
else:
first = middle + 1
return found
Il precedente ciclo basa la sua logica sull'ordinamento della lista dimezzando il numero degli elementi di input ad ogni iterazione.
Per cercare il numero 10 all'interno di una lista di 100 elementi, esegue le seguenti iterazioni:
First:0 - Last:99 - Middle:49
First:0 - Last:48 - Middle:24
First:0 - Last:23 - Middle:11
First:0 - Last:10 - Middle:5
First:6 - Last:10 - Middle:8
First:9 - Last:10 - Middle:9
First:10 - Last:10 - Middle:10
Elemento trovato: True
Ad ogni iteazione si può vedere come l'intervallo dei numeri si dimezzi.
Comparazione delle prestazioni
Le quattro tipologie di notazioni indicate posso essere elencate su una scala che indica quale sia la migliore in termini di prestazioni e quale la peggiore.
Per quanto riguarda le prestazioni, la migliore è la notazione O(log n) mentre la peggiore è O(n²).
Conclusioni
La notazione Big O riveste grande importanza nel valutare le prestazioni in termini di tempo di un determinato algoritmo. Soprattutto se si lavora o si preventiva di dover lavorare con una grande quantità di dati, è opportuno che ci si soffermi a capire se l'algoritmo progettato ha un comportamento adeguato in termini di prestazioni. Per queste valutazioni possiamo fare riferimento alla notazione Big O.
