Notazione Big-O: complessità in spazio

Ottimizzazione del codice in Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Cos'è la complessità in spazio?

La complessità in tempo descrive come la dimensione dell'input influisce sul runtime
La complessità in spazio descrive come l'input influisce sull'uso di memoria

Capire la complessità in spazio è cruciale per creare applicazioni che:

Usano solo la memoria necessaria, non di più
Evitano crash con errori come OutOfMemoryError

Notazione Big-O

La notazione è identica a quella della complessità in tempo.

Classi comuni:

O(1): Costante — indipendente dalla dimensione
O(n): Lineare — cresce con l'input
O(n²): Quadratica — cresce quadraticamente con l'input

Un metodo per trovare il massimo

public int findMax(int[] array) {
    int max = Integer.MIN_VALUE;
    for (int value : array) {
        if (value > max) {
            max = value;
        }
    }
    return max;
}

Che l'array abbia 10 o 10 milioni di elementi, usiamo memoria solo per una variabile: max
La complessità in spazio è O(1), ovvero costante

Un metodo che raddoppia i valori

public int[] doubleValues(int[] array) {
    int[] result = new int[array.length];
    for (int i = 0; i < array.length; i++) {
        result[i] = array[i] * 2;
    }
    return result;
}

Se l'input ha n elementi, serve spazio per n elementi aggiuntivi
La complessità in spazio è O(n) perché la memoria extra cresce linearmente con l'input

Un metodo per la tabella di moltiplicazione

public int[][] multiplicationTable(int n) {
    int[][] table = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            table[i][j] = (i + 1) * (j + 1);
        }
    }
    return table;
}

Se n è 10, servono 100 celle; se n è 100, servono 10.000 celle
Lo classifichiamo come O(n²)

Perché la complessità in spazio è importante?

La memoria è limitata!

I nostri esempi con input di 10.000 elementi:

findMax, O(1) -> solo pochi byte extra
doubleValues, O(n) -> ~40 KB di memoria in più
multiplicationTable, O(n²) -> circa 400 MB in più

Grafico a barre che mostra +8 byte per findMax, 40KB per doubleValues e 400MB per multiplicationTable

Spazio vs. tempo

Non dimenticare:

A volte scambiamo spazio per tempo
A volte scambiamo tempo per spazio
La scelta giusta dipende dai vincoli specifici

Grafica che simboleggia il trade-off tra tempo e spazio

Passiamo alla pratica !

Ottimizzazione del codice in Java