04 — La complexité spatiale et le compromis temps/espace
Ce que tu vas apprendre
- Que la mémoire se mesure en Big-O comme le temps
- Comment compter l'espace utilisé par un algorithme
- Le compromis fondamental entre temps et espace
- Quand il vaut le coup d'échanger de la mémoire contre de la vitesse
Prérequis
On parle presque toujours de la complexité en temps, parce que c'est elle qui fait ramer une page. Mais il existe une deuxième dimension, tout aussi réelle : la complexité spatiale, soit la quantité de mémoire qu'un algorithme consomme en fonction de la taille de l'entrée. Un programme rapide qui sature la RAM plante aussi sûrement qu'un programme lent. Et très souvent, gagner en vitesse coûte de la mémoire, et inversement.
Mesurer l'espace en Big-O
La complexité spatiale se note avec la même notation Big-O, mais elle compte la mémoire supplémentaire allouée, pas le temps. On ne compte généralement pas l'entrée elle-même, mais l'espace de travail que l'algorithme crée en plus.
typescript// O(1) en espace : quelques variables, peu importe la taille de l'entrée
function somme(items: number[]): number {
let total = 0; // une variable
for (const x of items) total += x;
return total;
}
// O(n) en espace : on crée un nouveau tableau de la taille de l'entrée
function doubles(items: number[]): number[] {
return items.map((x) => x * 2); // alloue n nouvelles cases
}
La première fonction utilise une mémoire constante : une seule variable total, que l'entrée fasse 10 ou 10 millions d'éléments. C'est O(1) en espace. La seconde alloue un tableau aussi grand que l'entrée, donc O(n) en espace.
Les complexités spatiales courantes sont les mêmes formes qu'en temps :
- O(1) : quelques variables, indépendant de la taille
- O(n) : une copie ou une structure proportionnelle à l'entrée
- O(n²) : une matrice, un tableau de tableaux
Attention à un coût caché : la pile d'appels d'une fonction récursive. Chaque appel récursif occupe de la mémoire jusqu'à son retour. Une récursion de profondeur n consomme O(n) en espace, même si le corps de la fonction semble n'allouer rien.
pythondef factorielle(n: int) -> int:
if n <= 1:
return 1
return n * factorielle(n - 1) # n appels empilés : O(n) en espace
Sur de grandes valeurs, cette récursion atteint la limite de la pile et lève une erreur de débordement (RecursionError en Python, Maximum call stack size exceeded en JavaScript). Une version itérative ferait le même calcul en O(1) d'espace.
Le compromis temps/espace
Voici le compromis le plus important du métier : on peut souvent rendre un algorithme plus rapide en lui donnant plus de mémoire, ou réduire sa mémoire au prix de plus de calcul. Les deux ressources s'échangent.
L'exemple canonique est la mémoïsation. Reprenons le Fibonacci exponentiel de l'article 01 :
typescript// O(2ⁿ) en temps, O(n) en espace (la pile)
function fibLent(n: number): number {
if (n <= 1) return n;
return fibLent(n - 1) + fibLent(n - 2);
}
// O(n) en temps, O(n) en espace : on stocke les résultats déjà calculés
function fibRapide(n: number, cache = new Map<number, number>()): number {
if (n <= 1) return n;
if (cache.has(n)) return cache.get(n)!;
const result = fibRapide(n - 1, cache) + fibRapide(n - 2, cache);
cache.set(n, result);
return result;
}
La version lente recalcule sans cesse les mêmes valeurs : fib(5) recalcule fib(3) plusieurs fois. La version rapide les stocke dans un cache. On dépense O(n) de mémoire pour passer de O(2ⁿ) à O(n) en temps. Sur fib(50), c'est la différence entre des minutes de calcul et une réponse immédiate. Échanger un peu de mémoire contre un facteur exponentiel de vitesse est une affaire qu'on prend sans hésiter.
L'autre sens : le Set qui accélère
L'exemple de déduplication des articles précédents illustre le même compromis. La version naïve compare chaque élément à tous les autres : O(n²) en temps, mais O(1) en espace, car elle ne crée rien. La version avec Set est O(n) en temps, mais O(n) en espace, car le Set stocke tous les éléments vus.
pythondef dedup(items: list[int]) -> list[int]:
vus = set() # O(n) en espace
result = []
for x in items:
if x not in vus: # O(1) au lieu de O(n)
vus.add(x)
result.append(x)
return result
On accepte de consommer une mémoire proportionnelle au nombre d'éléments pour gagner un facteur n en temps. Sur de gros volumes, c'est presque toujours le bon choix. La mémoire est abondante et bon marché ; le temps de réponse d'une requête utilisateur ne l'est pas.
Quand le compromis ne vaut pas le coup
Échanger de la mémoire contre du temps n'est pas systématiquement gagnant. Quelques cas où il faut réfléchir :
- Données massives qui ne tiennent pas en RAM. Si ton entrée fait déjà 50 Go, doubler la mémoire pour un cache n'est pas une option. Là, on préfère parfois un algorithme plus lent mais qui travaille en flux, avec une mémoire constante.
- Environnements contraints. Sur un appareil embarqué ou une fonction serverless avec peu de RAM, la mémoire est le facteur limitant, pas le temps.
- Caches qui grossissent sans limite. Un cache O(n) qui ne se vide jamais finit par tout garder en mémoire et provoque une fuite. Si tu mémoïses, prévois une stratégie d'éviction.
La bonne réflexion n'est pas « la mémoire est gratuite, je cache tout ». C'est « combien de mémoire suis-je prêt à dépenser, et pour quel gain de temps ? ». Le compromis se décide en connaissant les deux coûts.
L'article suivant rassemble les pièges concrets qui transforment du code d'apparence propre en O(n²) silencieux. Ce sont les erreurs que tu verras le plus souvent en revue de code.
Sources
- Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Chapitre 15 "Dynamic Programming" (mémoïsation). MIT Press.
- Bentley, J. (2000). Programming Pearls (2nd ed.), Colonne 1 "Cracking the Oyster" et Colonne 10 "Squeezing Space". Addison-Wesley.
- Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed.), Section 8.1 "Caching vs. Computation". Springer.