Notation Big-O : complexité spatiale

Optimiser son code en Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Qu'est-ce que la complexité spatiale ?

La complexité temporelle décrit comment la taille d'entrée affecte le temps d'exécution
La complexité spatiale décrit comment la taille d'entrée affecte l'utilisation mémoire

Comprendre la complexité spatiale est crucial pour créer des applications qui :

Utilisent juste la mémoire nécessaire, pas plus
Évitent les plantages avec des erreurs comme OutOfMemoryError

Notation Big-O

La notation est identique à la complexité temporelle.

Quelques classes courantes :

O(1) : constante – indépendante de la taille
O(n) : linéaire – croît avec la taille d'entrée
O(n²) : quadratique – croît au carré de la taille d'entrée

Une méthode pour trouver le maximum

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

Que notre tableau contienne 10 éléments ou 10 millions, on n'utilise de la mémoire que pour une seule variable, max
La complexité spatiale est O(1) (constante)

Une méthode de duplication

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;
}

Si l'entrée a n éléments, il faut de l'espace pour n éléments supplémentaires
La complexité spatiale est O(n) car la mémoire supplémentaire croît linéairement avec la taille d'entrée

Une méthode de table de multiplication

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;
}

Si n vaut 10, il faut 100 cases ; si n vaut 100, il faut 10 000 cases
On classe cela en O(n²)

Pourquoi la complexité spatiale est-elle importante ?

La mémoire est une ressource finie !

Nos exemples précédents avec une taille d'entrée de 10 000 éléments :

findMax, O(1) → quelques octets en plus
doubleValues, O(n) → environ 40 Ko de mémoire en plus
multiplicationTable, O(n²) → environ 400 Mo de mémoire en plus

Diagramme en barres montrant une augmentation de 8 octets pour findMax, 40 Ko pour doubleValues et 400 Mo pour multiplicationTable

Complexité spatiale vs complexité temporelle

À retenir :

Parfois on échange de l'espace contre du temps
Parfois on échange du temps contre de l'espace
Le bon choix dépend de vos contraintes

Graphique symbolisant le compromis entre temps et mémoire

Passons à la pratique !

Optimiser son code en Java