Une introduction visuelle à la notation Big O

• La notation Big O exprime les performances d’une fonction par sa croissance en fonction de la taille de l’entrée
• L’article explique avec des exemples les principales catégories de Big O : constante, logarithmique, linéaire et quadratique
• Selon la structure de données et l’algorithme, la complexité temporelle varie, notamment pour le tri ou la recherche dans un tableau
• Pour améliorer les performances réelles du code, l’essentiel est de choisir la bonne structure de données et d’éliminer les opérations inutiles dans les boucles
• Big O représente toujours de la façon la plus simplifiée possible la relation entre l’entrée et le temps d’exécution, et il reste important de mesurer directement le code lors d’une optimisation

---

Aperçu de la notation Big O

• La notation Big O est une manière de décrire la croissance du temps d’exécution en fonction de la taille de l’entrée (n), plutôt que de mesurer le temps brut
• Elle classe le temps d’exécution d’une fonction selon la taille de l’entrée ; les formes les plus analysées sont constante (O(1)), logarithmique (O(log n)), linéaire (O(n)) et quadratique (O(n²))
• Cet article les présente à l’aide de concepts accessibles, d’exemples visuels et de cas concrets dans du code, afin que les débutants puissent aussi les comprendre

Itération et algorithmes linéaires

• La fonction sum(n) illustre une structure itérative qui additionne de 1 à n ; plus la valeur d’entrée n augmente, plus le temps d’exécution augmente de manière proportionnelle
• En pratique, sum(1e9) prend environ 1 seconde et sum(2e9) environ 2 secondes : le temps réel (wall-clock time) croît donc selon un schéma en O(n)
• La complexité temporelle décrit la relation entre l’entrée d’une fonction et son temps d’exécution, relation que l’on exprime avec la notation Big O (O(n) — proportionnel à n)
• En remplaçant l’itération par la formule mathématique sum(n) = (n*(n+1))/2, le temps d’exécution devient constant, indépendamment de la valeur de n
• On parle alors de complexité temporelle constante O(1), caractérisée par l’absence de croissance du temps d’exécution lorsque l’entrée varie

Syntaxe de la notation Big O

• Le O de Big O vient de “Order” (ordre de croissance) et indique uniquement la forme de croissance
• Elle ne représente pas la valeur absolue du temps d’exécution, mais seulement le “motif” de croissance par rapport à l’entrée, de manière concise
• Par exemple, même pour une fonction en O(n), on n’écrit pas des formes plus compliquées comme O(2n) ou O(n+1) : on ne retient que le terme le plus simple et le plus dominant

Réduire le temps grâce à la structure de l’entrée

• Comme dans l’exemple de la formule sum(n), une amélioration d’algorithme peut faire passer la complexité temporelle de O(n) à O(1)
• Cela dit, une complexité constante n’est pas automatiquement plus rapide dans tous les cas, car le temps total dépend aussi de la nature des opérations effectuées
• Un algorithme en O(n) peut être plus rapide qu’un O(1) sur certaines petites entrées, mais à mesure que la taille augmente, l’approche O(1) finit toujours par l’emporter

Tri et algorithmes quadratiques : l’exemple du tri à bulles

• Le tri à bulles (Bubble Sort) est un exemple classique où l’on trie un tableau en échangeant de manière répétée des éléments adjacents
• Si le tableau est déjà trié, une seule passe suffit (O(n)) ; en ordre inverse, il faut parcourir le tableau n fois de manière répétée → dans le pire cas, le nombre total d’opérations est n²
• Les algorithmes en O(n²) voient leur temps d’exécution croître fortement sous forme quadratique lorsque l’entrée augmente
• En pratique, Big O se base toujours sur le pire cas (worst-case), même si l’on peut aussi parfois indiquer le cas moyen ou le meilleur cas
• Le nombre de passages peut diminuer selon l’état initial du tableau, mais comme on raisonne sur le pire cas, on classe toujours ce tri comme une complexité quadratique

Recherche et algorithmes logarithmiques : l’exemple de la recherche binaire

• La recherche binaire (Binary Search) consiste à estimer la valeur centrale d’un ensemble trié, puis à éliminer la moitié des candidats à chaque étape
• Par exemple, pour trouver un nombre entre 1 et 100, il faut au maximum 7 essais ; entre 1 et 1 milliard, moins de 31 essais suffisent
• Comme la liste des candidats est réduite de moitié à chaque étape, le temps d’exécution est en O(log n) (complexité logarithmique)
• Les algorithmes logarithmiques augmentent très lentement lorsque n grandit, ce qui les rend nettement plus efficaces que les approches linéaires ou quadratiques
• Sur un graphique, la différence de croissance entre log n, n et n² apparaît de manière très marquée

Application pratique : conseils pour améliorer la complexité temporelle

Rechercher un élément dans une liste

• Par défaut, une fonction qui cherche une valeur dans un tableau est en O(n)
• Si les recherches sont fréquentes, utiliser une structure comme Set permet de passer à O(1)
• En revanche, la conversion elle-même via new Set(array) est en O(n) ; elle n’est donc pertinente que pour des consultations répétées (en tenant compte du coût de conversion)
• Exemple : items.has("banana") offre une complexité temporelle constante

Écrire des boucles en exploitant l’index

• Le code ci-dessous, qui utilise .indexOf à l’intérieur d’une boucle, est une source fréquente de problèmes de performance

  function buildList(items) {
    const output = [];
    for (const item of items) {
      const index = items.indexOf(item);
      output.push(`Item ${index + 1}: ${item}`);
    }
    return output.join("\n");
  }
  

• Comme .indexOf est une opération en O(n) dans la boucle, on obtient au total un comportement en O(n^2)

• En utilisant une boucle basée sur l’index ou forEach((item, index) => ...), on peut revenir à O(n)

  function buildList(items) {
    const output = [];
    for (let i = 0; i < items.length; i++) {
      output.push(`Item ${i + 1}: ${items[i]}`);
    }
    return output.join("\n");
  }
  

Utiliser la mémoïsation (Memoization)

• Pour des calculs comme la factorielle, où des appels répétés entraînent des recalculs redondants, on peut améliorer les performances en mettant les résultats en cache (avec Map)

• Une consultation dans Map est en O(1), ce qui réduit les recalculs inutiles

• Le cache améliore surtout le temps moyen ; même si la complexité du pire cas ne change pas, on peut tout de même obtenir un gain d’efficacité significatif

  const cache = new Map();
  function factorial(n) {
    if (cache.has(n)) {
      return cache.get(n);
    }
    if (n === 0) {
      return 1;
    }
    const result = n * factorial(n - 1);
    cache.set(n, result);
    return result;
  }
  

Évaluation des performances et conclusion

• Lorsqu’on cherche à améliorer les performances d’un code, il faut vérifier les gains réels avec des tests d’exécution directs, en plus de la complexité théorique
• Big O exprime de la manière la plus essentielle et simplifiée la relation et le motif de croissance entre l’entrée et le temps d’exécution
• En choisissant de bons algorithmes et en optimisant les structures de données, on peut maximiser l’efficacité du code

Récapitulatif

• La notation Big O exprime la relation entre les entrées d’une fonction et son temps d’exécution
• Principaux niveaux de performance : O(1) (constante), O(log n) (logarithmique), O(n) (linéaire), O(n^2) (quadratique)
• Pour écrire du code efficace, le choix de l’algorithme et l’optimisation des boucles sont essentiels
• Les performances réelles doivent être vérifiées par des mesures directes
• Un graphique comparant les croissances permet de comprendre d’un coup d’œil les caractéristiques de chaque complexité