Notazione Big O

11.1 Definizione della notazione Big O

La notazione Big O è una notazione matematica utilizzata per descrivere il limite superiore del tempo di esecuzione o del consumo di risorse di un algoritmo in relazione alla dimensione dei dati di input. Aiuta a determinare come l'algoritmo si scala bene e come la sua performance cambia con l'aumento del volume dei dati.

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

Notazioni principali:

O(1) — Complessità costante:

• Il tempo di esecuzione dell'algoritmo non dipende dalla dimensione dei dati di input.
• Esempio: accesso a un elemento di un array per indice.

O(n) — Complessità lineare:

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

O(log n) — Complessità logaritmica:

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

O(n^2) — Complessità quadratica:

• Il tempo di esecuzione dell'algoritmo dipende quadraticamente dalla dimensione dei dati di input.
• Esempio: ordinamento a bolle, ordinamento per inserimento.

O(2^n) — Complessità esponenziale:

• Il tempo di esecuzione dell'algoritmo dipende esponenzialmente dalla dimensione dei dati di input.
• Esempio: risoluzione del problema dello zaino con brute force.

Nota. Approfondirai la ricerca binaria, l'ordinamento a bolle e il "problema dello zaino" nelle prossime lezioni.

11.2 Interpretazione della notazione Big O

Come interpretare e utilizzare la notazione Big O?

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

Confronto tra algoritmi: Big O consente 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 è generalmente utilizzato per analizzare il caso peggiore del tempo di esecuzione di un algoritmo, consentendo di valutare la sua complessità massima.

Ignorare le costanti

Consideriamo degli esempi di ignorare costanti e termini meno significativi:

Esempio 1. Consideriamo due funzioni:

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

Entrambe le funzioni hanno complessità lineare, poiché il termine dominante in ciascuna funzione è n. Quindi, 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 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.

11.3. Confronto tra algoritmi

1. Confronto tra 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 piccoli valori di n l'algoritmo A può funzionare più velocemente a causa di 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, poiché O(1) significa che il tempo di esecuzione dell'algoritmo non dipende dalla dimensione dei dati di 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 sarà necessario un confronto e, possibilmente, uno scambio 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 passi necessari per trovare un elemento dipenderà logaritmicamente dalla dimensione dell'array, il che è molto efficiente.

3. Impatto su performance e scalabilità

Esempio 1:

Se abbiamo due algoritmi per elaborare i dati, uno con complessità temporale O(n^2) e l'altro con O(n log n), e aumentiamo la dimensione dei dati da 1000 elementi a 10 000 elementi, la differenza di performance sarà significativamente evidente.

• L'algoritmo con O(n^2) eseguirà circa 100 000 000 operazioni per 10 000 elementi.
• L'algoritmo con O(n log n) eseguirà circa 40 000 operazioni per 10 000 elementi.

Esempio 2:

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

• Per n = 10: 2^10 = 1024 operazioni.
• Per n = 20: 2^20 = 1 048 576 operazioni.

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

1

Опрос

Strutture dati,  52 уровень,  4 лекция

недоступен

Strutture dati

Strutture dati

Открыть