Notazione Big O: concetti di base

2.1 Definizione della notazione Big O.

La notazione Big O è una notazione matematica usata per descrivere il limite superiore del tempo di esecuzione o del consumo di risorse di un algoritmo in base alla dimensione dell'ingresso. Aiuta a determinare quanto bene l'algoritmo si scala e come cambia la sua performance con l'aumentare del volume di dati.

La notazione Big O si concentra sugli aspetti più significativi dell'algoritmo, ignorando le costanti e i termini meno significativi, il che permette di concentrarsi sul comportamento a lungo termine dell'algoritmo.

Notazioni di base:

O(1) — Complessità costante:

• Il tempo di esecuzione dell'algoritmo non dipende dalla dimensione del dato in input.
• Esempio: accesso a un elemento di un array tramite indice.

O(n) — Complessità lineare:

• Il tempo di esecuzione dell'algoritmo dipende linearmente dalla dimensione del dato in input.
• Esempio: iterazione semplice di tutti gli elementi di un array.

O(log n) — Complessità logaritmica:

• Il tempo di esecuzione dell'algoritmo cresce logaritmicamente con l'aumentare della dimensione del dato in input.
• Esempio: ricerca binaria in un array ordinato.

O(n^2) — Complessità quadratica:

• Il tempo di esecuzione dell'algoritmo dipende quadraticamente dalla dimensione del dato in input.
• Esempio: ordinamento a bolle, ordinamento per inserzione.

O(2^n) — Complessità esponenziale:

• Il tempo di esecuzione dell'algoritmo dipende esponenzialmente dalla dimensione del dato in input.
• Esempio: risoluzione del problema dello zaino con ricerca esaustiva.

2.2 Interpretazione della notazione Big O.

Come interpretare e usare la notazione Big O?

Ignorare le costanti e i termini meno significativi:

Big O descrive l'ordine di crescita di una funzione ignorando le costanti e i termini meno significativi. Ad esempio, O(2n) e O(3n) sono interpretati come O(n).

Confronto degli algoritmi:

Big O permette di confrontare gli algoritmi in base alla loro efficienza asintotica. Ad esempio, un algoritmo con O(n log n) è più efficiente di un algoritmo con O(n^2) per volumi di dati molto grandi.

Analisi del caso peggiore:

Big O è usato di solito per analizzare il tempo di esecuzione nel caso peggiore di un algoritmo, permettendo di stimare la sua complessità massima.

Ignorare le costanti.

Ignorare le costanti e i termini meno significativi

Esempio 1:

Consideriamo due funzioni:

• f(n) = 3n + 2
• g(n) = 5n + 1

Entrambe le funzioni hanno una complessità lineare, poiché il termine dominante in ciascuna funzione è n. Pertanto, entrambe le funzioni sono interpretate come O(n), nonostante le differenze nei coefficienti e nei termini aggiuntivi.

Esempio 2:

Consideriamo due funzioni:

• f(n) = n^2 + 3n + 4
• g(n) = 2n^2 + n

Entrambe le funzioni hanno una complessità quadratica, poiché il termine dominante è n^2. Entrambe le espressioni sono interpretate come O(n^2), nonostante le differenze negli altri termini e coefficienti.

2.3. Confronto degli algoritmi

1. Confronto degli algoritmi su volumi di dati molto grandi

Esempio 1:

• L'algoritmo A ha una complessità temporale O(n^2).
• L'algoritmo B ha una complessità temporale O(n log n).

Per valori piccoli di n, l'algoritmo A potrebbe funzionare più velocemente a causa delle costanti minori, ma per valori grandi di n, l'algoritmo B sarà significativamente più veloce, poiché la sua crescita è logaritmica e non quadratica.

Esempio 2:

• L'algoritmo X ha una complessità temporale O(n).
• L'algoritmo Y ha una complessità temporale O(1).

L'algoritmo Y sarà sempre più veloce, indipendentemente dalla dimensione di n, perché O(1) significa che il tempo di esecuzione dell'algoritmo non dipende dalla dimensione del dato in input.

2. Analisi del caso peggiore

Esempio 1:

L'algoritmo di ordinamento a bolle ha una complessità temporale O(n^2) nel caso peggiore, quando l'array è ordinato in ordine inverso. Ciò significa che per ogni elemento nell'array è necessario fare confronti e, forse, scambi con ogni altro elemento.

Esempio 2:

La ricerca binaria ha una complessità temporale O(log n) nel caso peggiore. Ciò significa che anche nel caso peggiore, il numero di passaggi necessari per trovare un elemento dipenderà logaritmicamente dalla dimensione dell'array, il che è molto efficiente.

3. Impatto sulle prestazioni e scalabilità

Esempio 1:

Se abbiamo due algoritmi per elaborare dati, uno con complessità temporale O(n^2) e l'altro con O(n log n), e aumentiamo la dimensione dei dati da 1000 a 10.000 elementi, la differenza nelle prestazioni sarà notevolmente visibile.

• L'algoritmo con O(n^2) eseguirebbe approssimativamente 100.000.000 di operazioni per 10.000 elementi.
• L'algoritmo con O(n log n) eseguirebbe circa 40.000 operazioni per 10.000 elementi.

Esempio 2:

Consideriamo un algoritmo che funziona con O(2^n). Se aumentiamo la dimensione del dato in input da 10 a 20 elementi, il numero di operazioni cresce esponenzialmente.

• Per n = 10: 2^10 = 1024 operazioni.
• Per n = 20: 2^20 = 1.048.576 operazioni.

Questo mostra quanto rapidamente la complessità esponenziale diventi impraticabile per valori grandi di n.