Cos'è la notazione Big O?

La notazione Big O (Big O) è una notazione matematica utilizzata per descrivere il comportamento asintotico di una funzione e il suo limite superiore. Nel contesto dello sviluppo software, viene applicata per valutare le prestazioni degli algoritmi in termini di consumo di tempo (complessità temporale) e memoria (complessità spaziale) man mano che cresce la dimensione dei dati di input. Essa descrive lo scenario peggiore di esecuzione.

Le classi di complessità temporale più comuni:

• O(1): Tempo costante. Il tempo di esecuzione non dipende dalla dimensione dei dati di input.
• O(log n): Tempo logaritmico. Il tempo di esecuzione cresce lentamente con l'aumentare della dimensione dei dati di input (ad esempio, ricerca binaria).
• O(n): Tempo lineare. Il tempo di esecuzione è proporzionale alla dimensione dei dati di input (ad esempio, ricerca lineare).
• O(n log n): Tempo lineare-logaritmico. Spesso presente negli algoritmi di ordinamento efficienti (ad esempio, quicksort, mergesort).
• O(n^2): Tempo quadratico. Il tempo di esecuzione cresce proporzionalmente al quadrato della dimensione dei dati di input (ad esempio, ordinamento a bolle, ordinamento per selezione).
• O(2^n): Tempo esponenziale. Il tempo di esecuzione cresce molto rapidamente con l'aumentare della dimensione dei dati di input. Spesso presente nei problemi di ricerca esaustiva.

Esempi di codice e loro complessità temporale:

// O(1)
int primoElemento = array[0];

// O(n)
for (int i = 0; i < array.length; i++) {
    // qualche operazione
}

// O(n^2)
for (int i = 0; i < array.length; i++) {
    for (int j = 0; j < array.length; j++) {
        // qualche operazione
    }
}

La notazione Big O si concentra sul termine dominante nell'espressione e ignora le costanti e i termini meno significativi, poiché per grandi input il loro contributo diventa trascurabile. Ad esempio, un algoritmo con complessità O(2n^2 + 5n + 10) è considerato O(n^2).

Comprendere il Big O è importante per scegliere gli algoritmi e le strutture dati più efficienti durante lo sviluppo.