Notation grand O : complexité spatiale

Optimiser le 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 influence le temps d'exécution
La complexité spatiale décrit comment la taille d'entrée influence l'utilisation de la 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 pannes avec des erreurs comme OutOfMemoryError

Notation grand O

La notation est identique à la complexité temporelle.

Quelques classes courantes :

O(1) : temps constant – indépendant de la taille
O(n) : temps linéaire – croît avec la taille d'entrée
O(n²) : temps 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 d'entiers ait 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 doublement

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 compte n éléments, il faut de l'espace pour n éléments additionnels
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 pour la 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 en faut 10 000
On classe cela comme O(n²)

Pourquoi la complexité spatiale est-elle importante ?

La mémoire est une ressource finie !

Nos exemples précédents en action, pour une taille d'entrée de 10 000 éléments :

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

Diagramme à barres montrant une hausse 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 illustrant le compromis entre temps et espace

Passons à la pratique !

Optimiser le code en Java