Comprendre Big-O par l'exemple de code
1. Vue d’ensemble
Big-O est une façon de décrire le taux de croissance du temps d’exécution (ou de la mémoire) lorsque la taille de l’entrée augmente. Au lieu de formules mathématiques rébarbatives, cet article passe en revue chaque niveau de complexité courant avec du vrai code Java, accompagné d’une analyse des lignes coûteuses. Après la lecture, vous pourrez regarder un morceau de code et deviner immédiatement s’il est O(1), O(n), O(n log n) ou O(n²) sans avoir besoin de compter manuellement.
2. Qu’est-ce que Big-O, et pourquoi c’est important
Big-O répond à la question : « Si l’entrée double, de combien augmente le temps d’exécution ? » Il ignore les constantes et les petits facteurs, ne gardant que la tendance de croissance lorsque n (la taille de l’entrée) tend vers l’infini.
n = 1.000 -> O(n) exécute ~1.000 étapes
n = 1.000.000 -> O(n) exécute ~1.000.000 étapes (croissance linéaire)
n = 1.000.000 -> O(n²) exécute ~10^12 étapes (croissance très rapide)Deux morceaux de code peuvent « sembler identiques à première vue » mais avoir une complexité très différente si l’un cache une boucle imbriquée à l’intérieur d’un appel de fonction. Comprendre Big-O vous aide à éviter du code qui fonctionne bien avec 100 enregistrements de test mais qui « gèle » en production avec 10 millions d’enregistrements.
Remarque : Big-O décrit le cas le plus mauvais (worst case) selon la convention la plus courante, sauf si best-case ou average-case est spécifié.
3. O(1) – Temps constant
Le temps d’exécution est constant, peu importe la taille de l’entrée.
public class InventoryCache {
private final Map<String, Integer> stockBySku = new HashMap<>();
public Integer getStock(String sku) {
return stockBySku.get(sku); // HashMap.get est O(1) en moyenne
}
}get() sur HashMap calcule le hash de la clé puis accède directement au bucket correspondant, indépendamment du nombre d’éléments dans la map. De même, l’accès à array[i] ou list.get(i) avec ArrayList est aussi O(1) car il suffit de calculer l’adresse décalée (offset).
4. O(n) – Temps linéaire
Le temps d’exécution augmente proportionnellement à la taille de l’entrée.
public class OrderValidator {
public boolean hasExpiredItem(List<Order> orders) {
for (Order order : orders) {
if (order.isExpired()) {
return true; // arrête tôt mais le pire cas traverse toujours la liste complète
}
}
return false;
}
}La boucle for parcourt au maximum n éléments de orders. Le pire cas se produit quand aucune commande n’est expirée, obligeant à vérifier toute la liste. Ceci est le modèle O(n) classique : une boucle unique, non imbriquée.
4.1. Pièges courants : contains() dans une boucle
public class DuplicateChecker {
// O(n²) car contains() sur une List est O(n), appelé n fois
public boolean hasDuplicateSlow(List<String> emails) {
List<String> seen = new ArrayList<>();
for (String email : emails) {
if (seen.contains(email)) {
return true;
}
seen.add(email);
}
return false;
}
}seen.contains(email) sur ArrayList est O(n) car il faut parcourir linéairement pour chercher. L’appeler à l’intérieur de la boucle for transforme toute la fonction en O(n²) — une erreur très facile à commettre si on ne fait pas attention à la structure de données interne.
public class DuplicateChecker {
// O(n) grâce à HashSet.add/contains qui est O(1)
public boolean hasDuplicateFast(List<String> emails) {
Set<String> seen = new HashSet<>();
for (String email : emails) {
if (!seen.add(email)) { // add() retourne false si l'élément existe déjà
return true;
}
}
return false;
}
}En changeant simplement de List à HashSet, la complexité diminue de O(n²) à O(n). C’est l’exemple le plus pratique montrant que choisir la bonne structure de données est plus important que « l’optimisation microscopique ».
5. O(log n) – Temps logarithmique
Chaque étape élimine la moitié de l’espace de recherche.
public class PriceLookup {
// sortedPrices doit être trié par ordre croissant au préalable
public int findIndex(int[] sortedPrices, int target) {
int low = 0;
int high = sortedPrices.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (sortedPrices[mid] == target) {
return mid;
} else if (sortedPrices[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
}La recherche binaire divise le tableau en deux à chaque itération while, donc avec n = 1.000.000 il suffit d’environ 20 étapes (log₂ 1.000.000 ≈ 20) pour trouver le résultat, au lieu de parcourir linéairement un million d’éléments.
class PriceLookupTest {
@Test
void shouldFindIndexInSortedArray() {
int[] prices = {10, 20, 30, 40, 50};
PriceLookup lookup = new PriceLookup();
int index = lookup.findIndex(prices, 40);
assertThat(index).isEqualTo(3);
}
@Test
void shouldReturnMinusOneWhenNotFound() {
PriceLookup lookup = new PriceLookup();
int index = lookup.findIndex(new int[] {1, 2, 3}, 99);
assertThat(index).isEqualTo(-1);
}
}Ce test confirme le comportement correct lorsque l’élément est trouvé (retour de l’index) et lorsqu’il n’est pas trouvé (retour de -1), les deux branches critiques de la recherche binaire.
6. O(n log n) – Combinaison linéaire et logarithmique
C’est la complexité des algorithmes de tri efficaces comme merge sort, quick sort (cas moyen), ou Collections.sort().
public class RevenueReport {
public List<Order> sortByAmountDescending(List<Order> orders) {
List<Order> copy = new ArrayList<>(orders);
copy.sort(Comparator.comparing(Order::amount).reversed()); // O(n log n)
return copy;
}
}Collections.sort()/List.sort() en Java utilise Timsort (une variante de merge sort), garantissant O(n log n) au pire cas. Si vous voyez du code appelant sort() à l’intérieur d’une boucle exécutée n fois, la complexité totale est multipliée par O(n² log n) — un signe que du refactoring est nécessaire.
7. O(n²) – Temps quadratique
Deux boucles imbriquées, chacune parcourant la totalité (ou presque) de l’entrée.
public class PairFinder {
// Trouver toutes les paires de produits dont la somme des prix égale target
public List<int[]> findPairsSlow(int[] prices, int target) {
List<int[]> result = new ArrayList<>();
for (int i = 0; i < prices.length; i++) {
for (int j = i + 1; j < prices.length; j++) {
if (prices[i] + prices[j] == target) {
result.add(new int[] {prices[i], prices[j]});
}
}
}
return result;
}
}La boucle externe s’exécute n fois, la boucle interne s’exécute au maximum n fois pour chaque itération externe — le nombre total de comparaisons est approximativement n²/2, donc la complexité est O(n²). Avec n = 10.000, cela représente 50 millions de comparaisons — cela fonctionne encore, mais le ralentissement est très apparent.
public class PairFinder {
// O(n) grâce à HashSet qui stocke les valeurs vues
public List<int[]> findPairsFast(int[] prices, int target) {
List<int[]> result = new ArrayList<>();
Set<Integer> seen = new HashSet<>();
for (int price : prices) {
int complement = target - price;
if (seen.contains(complement)) {
result.add(new int[] {complement, price});
}
seen.add(price);
}
return result;
}
}Au lieu de comparer chaque paire, nous utilisons une seule boucle et une recherche O(1) dans HashSet. C’est une technique « d’échange temps pour espace » très courante : cela coûte de la mémoire supplémentaire pour stocker seen, mais réduit la complexité de O(n²) à O(n).
8. O(2^n) – Temps exponentiel
Le temps d’exécution double chaque fois que l’entrée augmente d’une unité — généralement vu dans les fonctions récursives qui calculent tous les sous-ensembles.
public class SubsetGenerator {
public List<List<Integer>> generateAllSubsets(List<Integer> items) {
List<List<Integer>> result = new ArrayList<>();
backtrack(items, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(List<Integer> items, int index,
List<Integer> current, List<List<Integer>> result) {
if (index == items.size()) {
result.add(new ArrayList<>(current));
return;
}
// Branche 1 : ne pas choisir item[index]
backtrack(items, index + 1, current, result);
// Branche 2 : choisir item[index]
current.add(items.get(index));
backtrack(items, index + 1, current, result);
current.remove(current.size() - 1);
}
}Chaque élément crée 2 branches récursives (choisir ou non choisir), donc avec n éléments nous avons 2^n sous-ensembles. Avec n = 20, c’est déjà plus d’un million de sous-ensembles ; avec n = 40, aucune machine ne peut finir dans un temps raisonnable. C’est un signe à considérer la programmation dynamique si le problème le permet.
9. Comparaison rapide par benchmark réel
Un exemple de test simple pour « voir » la différence entre O(n) et O(n²) :
class DuplicateCheckerBenchmarkTest {
@Test
void fastVersionShouldHandleLargeInputQuickly() {
List<String> emails = new ArrayList<>();
for (int i = 0; i < 100_000; i++) {
emails.add("user" + i + "@example.com");
}
DuplicateChecker checker = new DuplicateChecker();
long start = System.nanoTime();
boolean hasDuplicate = checker.hasDuplicateFast(emails);
long elapsedMs = (System.nanoTime() - start) / 1_000_000;
assertThat(hasDuplicate).isFalse();
assertThat(elapsedMs).isLessThan(500); // O(n) donc toujours très rapide avec 100k éléments
}
}Si vous essayez de remplacer hasDuplicateFast par hasDuplicateSlow avec les mêmes 100.000 emails, le temps d’exécution dépassera largement le seuil de 500ms — une preuve concrète de la différence entre O(n) et O(n²) sur des données réelles.
10. Tableau de synthèse et règles d’identification rapide
| Big-O | Signe dans le code | Exemple |
|---|---|---|
| O(1) | Pas de boucle, accès direct (index de tableau, HashMap.get) | map.get(key) |
| O(log n) | Chaque étape élimine une partie de l’espace de recherche | Recherche binaire |
| O(n) | Une boucle unique parcourant l’entrée | for sur List |
| O(n log n) | Boucle combinée avec tri, ou diviser pour régner | Collections.sort() |
| O(n²) | Boucle imbriquée dans une boucle, parcourant l’entrée | Comparaison par paires |
| O(2^n) | Récursion avec 2 branches à chaque étape, sans élagage | Générer tous les sous-ensembles |
Règle d’énumération rapide : compter le nombre de boucles imbriquées parcourant l’entrée — chaque niveau de boucle ajoute une « puissance n ». Si la boucle appelle une fonction de bibliothèque (contains, sort, indexOf), recherchez la complexité de cette fonction avant de l’ajouter au total.
Remarque : Big-O ne dit rien sur les constantes réelles. Un algorithme O(n) avec une grande constante (par exemple, lire un fichier à chaque itération) peut être plus lent qu’un O(n log n) avec une petite constante quand
nn’est pas encore assez grand. Ne optimisez pas Big-O à l’aveugle sans profiler d’abord en pratique.
11. Conclusion
Big-O est un outil pour prédire les tendances, pas un nombre absolu — mais c’est précisément cette tendance qui détermine si votre code survit ou s’effondre à mesure que les données augmentent. Le conseil le plus pratique : chaque fois que vous écrivez une boucle, demandez-vous « y a-t-il un appel de fonction O(n) à l’intérieur de cette boucle ? » — c’est l’origine de la plupart des erreurs O(n²) involontaires dans la pratique. Maîtriser les 6 niveaux de complexité ci-dessus suffit à comprendre et critiquer la plupart du code d’algorithme que vous rencontrez au quotidien.
HoanTien.proCashback on Shopee, TikTok Shop and Lazada (Vietnam)iOS · Android · Web
Vous aimez ce genre d'explication ? Cris The Dev publie une courte vidéo chaque jour sur YouTube et TikTok.
Sur le même sujet
Recherche binaire: lower bound, tableau roté, recherche par réponse
Implémenter correctement la recherche binaire dès la première fois et appliquer les variantes lower/upper bound, tableau roté, recherche binaire par réponse en Java 21.
HashMap résout les problèmes de comptage en Java
Utilisez HashMap pour compter les fréquences, trouver l'élément le plus fréquent, compter les paires et regrouper les anagrammes — avec la complexité et les erreurs courantes.
Two Pointers et Sliding Window : optimisation pour tableaux
Découvrez les techniques two pointers et sliding window pour résoudre les problèmes de tableaux/chaînes en O(n), avec des exemples Java exécutables.