Notazione Big-O: complessità temporale

Ottimizzazione del codice in Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Cos'è la complessità temporale?

Complessità temporale: misura di come il runtime cresce con l'input
Aiuta a rispondere: "Cosa succede quando i dati diventano 10× più grandi?"
Non si concentra sul tempo assoluto

Notazione Big-O

Notazione matematica per descrivere il caso peggiore.

Alcune classi di complessità comuni:

O(1): Tempo costante - indipendente dalla dimensione

Capire O(1)

Un esempio di operazione O(1) è get() di ArrayList

Implementazione interna (semplificata) di un ArrayList di String:

public class ArrayList {}
    private String[] data; // Array interno
    private int size;

    // Operazione get - accesso diretto all'array
    public String get(int index) {
        return data[index]; // O(1)
    }
}

Notazione Big-O

Notazione matematica per descrivere il caso peggiore

Classi di complessità comuni:

O(1): Tempo costante - indipendente dalla dimensione
O(n): Tempo lineare - cresce con l'input

Capire O(n)

Un esempio simile, ma per contains() di ArrayList

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    // Ricerca lineare nell'array
    for (int i = 0; i < size; i++) {
        if (o.equals(elementData[i])) {
            return i;
        }
    }
    return -1; // Non trovato
}

Notazione Big-O

Notazione matematica per descrivere il caso peggiore

Classi di complessità comuni:

O(1): Tempo costante - indipendente dalla dimensione
O(n): Tempo lineare - cresce con l'input
O(n²): Tempo quadratico - cresce quadraticamente con l'input

Un esempio pratico con complessità quadratica

// Trovare una coppia di numeri che somma a un valore target
// Complessità temporale: O(n²)

public int[] findPairWithSum(ArrayList<Integer> numbers, int targetSum) {
    for (int i = 0; i < numbers.size(); i++) {
        for (int j = i + 1; j < numbers.size(); j++) {
            if (numbers.get(i) + numbers.get(j) == targetSum) {
                console.log("Found them!")
            }
        }
    }
}

Perché la complessità temporale conta

Impatto della dimensione dell'input:

O(1): da 1.000 a 1.000.000 elementi = Stesso tempo!
O(n): da 1.000 a 1.000.000 elementi = 1.000× più lento
O(n²): da 1.000 a 1.000.000 elementi = 1.000.000× più lento

Screenshot 2025-05-10 at 2.27.06 PM.png

Ayo berlatih!

Ottimizzazione del codice in Java