Une introduction visuelle à la notation Big O

(samwho.dev)

2 points par GN⁺ 2025-08-26 | 1 commentaires | Partager sur WhatsApp

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é

1 commentaires

GN⁺ 2025-08-26

Avis Hacker News

Cet article, comme les commentaires HN, perpétue la tradition qui consiste à expliquer la notation Big O puis à débattre de ses usages réels et de ses détails techniques. À titre d’exemples utiles, il y a cet article explicatif et ce billet sur l’attitude des experts
- En lisant les commentaires de l’article précédent, on voyait qu’un utilisateur nommé Pyon avait une attitude acerbe et rigide. Mais la réponse de Ned n’est pas franchement remarquable non plus. Il n’explique pas précisément les détails techniques et donne plutôt l’impression de contourner le sujet en répétant simplement « certains détails ». C’est dommage qu’il n’ait pas expliqué pourquoi cette critique relevait du pinaillage, ni pourquoi il rejetait aussi le fond lui-même. Ned montre certes une bonne direction en matière de communication et d’empathie en ligne. Mais en tant qu’éducateur, j’aurais aimé qu’il prenne au moins une fois le temps d’expliquer pourquoi ce point technique était trop pointilleux ou relevait du pinaillage. Le fait qu’il dise seulement qu’il « ne le savait pas depuis des décennies » ne donne pas l’impression que cela suffise. Et en relisant le fil de commentaires original, Ned a en réalité débattu de façon assez diplomatique et sérieuse. Je me demande donc pourquoi cette analyse a disparu du billet de blog. Personnellement, je ne sais pas très bien quels sont ces détails techniques, mais j’aurais aimé au moins un bref résumé
- Je suis plutôt du côté des experts critiques. Si je suis toujours déçu par les tentatives d’enseigner des sujets complexes sur des blogs, c’est parce que, la plupart du temps, ce sont des non-spécialistes qui les expliquent en sacrifiant la précision. Résultat : 1) des informations inexactes sont copiées-collées partout sur Internet, et 2) les lecteurs s’arrêtent au niveau du blog, refusent d’aller plus loin, et consolident ainsi leur ignorance. Et, en plus, je n’aimais pas la mise en page. Avec mon TDAH et ma mauvaise mémoire, j’ai besoin d’un découpage clair (sous-titres, gras, couleurs de séparation, puces, etc.) pour suivre ; là, j’avais juste l’impression d’un mur de texte. Plus il me faut de temps pour identifier l’idée principale, plus je perds ma concentration. L’explication de Big O sur Simple Wikipedia est bien plus directe. À l’inverse, la page Wikipédia classique introduit soudainement des maths, et en la consultant on se rend compte que Big O est en fait un sujet bien plus complexe qu’on ne le croit, ce qui m’a amené à conclure que « simplifier à outrance n’est peut-être pas une bonne idée »
- Le deuxième lien ne parle pas de Big-O, et il n’y a pas lieu de prendre ce genre d’attitude pour modèle
- Ned m’a envoyé un e-mail il y a quelques jours, et je suis heureux, moi aussi, de contribuer à ce type de discussion
- La vraie leçon de ce genre d’articles, ce n’est pas qu’il faut arrêter de corriger les explications fausses ou trompeuses, mais qu’en ligne certains « experts » veulent simplement gagner une dispute. Vu l’attitude de Pyon, cela paraissait assez agressif, presque comme un troll d’Internet. Il ne faut surtout pas en conclure que « les détails techniques n’ont pas d’importance et qu’il est acceptable d’être inexact »
Un O(1) repose en pratique sur une fonction de hachage, ce qui n’est pas trivial mais représente un coût d’opération constant. Si les données sont très petites, un algorithme théoriquement pire comme O(n^2) peut malgré tout être plus rapide en temps réel
- C’est vrai, mais mieux vaut ne pas trop insister là-dessus. Dans le monde réel, c’est déjà difficile de faire comprendre qu’un n^2 peut mettre un ordinateur à genoux. Et selon les cas, on peut aussi utiliser une fonction de hachage parfaite comme mod
J’ai l’impression que l’importance moderne de Big-O n’est plus ce qu’elle était. Le matériel actuel a du multithreading, des pipelines, du NUMA, des caches complexes, etc. : certaines opérations se terminent parfois en moins d’un cycle, tandis que d’autres peuvent prendre des centaines ou des milliers de cycles. Si on essaie de décrire un algorithme uniquement par le nombre d’itérations de la boucle la plus interne, on finit au contraire par déformer la réalité. Et lorsqu’on parle de Big-O, il faudrait aussi mentionner d’autres notations comme Big-Omega. (Au passage, j’ai aussi beaucoup aimé l’animation sur le thème de Big-O)
- La théorie Big-O est justement née pour définir la quantité d’opérations indépendamment de ces facteurs matériels. En ce sens, c’est un outil qui ne vieillit pas. (Un bon intervenant précise d’ailleurs généralement que « des constantes comme C peuvent devenir très importantes lorsque N est petit »)
Ce qui est vraiment intéressant, c’est qu’en informatique quantique certaines opérations croissent en O(n^7) par rapport au nombre d’atomes, mais que les scientifiques n’ont pas peur d’exécuter ces calculs en pratique. Parce que N est suffisamment petit, que les ordinateurs et la mémoire continuent de s’améliorer, et que les résultats obtenus ont une valeur énorme. (Je ne suis pas spécialiste en informatique, donc pardonnez-moi si j’ai mal utilisé la notation O())
- Il suffit de dire que « cela augmente proportionnellement à n^7 ». La plupart des gens comprendront aussi O(n^7), mais en mathématiques O n’indique rigoureusement qu’une borne supérieure, donc ce n’est pas tout à fait exact. Si on veut être vraiment précis, il faudrait écrire quelque chose comme Ω(n^7)
J’aime vraiment beaucoup cette visualisation. Même en ayant appris les algorithmes autrefois, le fait de les voir visuellement reste très utile
J’ai fait des études de génie électrique, donc j’ai toujours eu l’impression que la notation Big O était traitée comme une notion qu’on survolait un peu. On la présentait toujours comme quelque chose d’évident que tout le monde connaissait déjà, et je n’ai jamais vraiment vu d’explication pédagogique. Je me demande à quel niveau, en maths ou en informatique, cette notion est introduite pour la première fois
- C’est en mathématiques discrètes, dans mon cursus d’informatique, que j’ai appris Big-O de la façon la plus structurée
- Dans mon école, on enseignait Big-O et plusieurs méthodes de démonstration en analyse d’algorithmes (cours obligatoire). Mais c’était un cours qu’on suivait surtout en 3e ou 4e année, avec l’hypothèse implicite qu’en pratique on avait déjà absorbé une bonne partie du concept dès la 1re année (probablement parce qu’on l’apprend un peu naturellement autour de soi)
- Mathématiquement, dire qu’une fonction f(x) est O(g(x)) signifie que f(x)/g(x) satisfait, pour une certaine constante C, la condition « pour tout x, f(x)/g(x) < C ». En informatique, f(x) représente souvent la complexité, par exemple le nombre d’opérations d’un algorithme donné
- La conception de la notation Big-O permet plusieurs interprétations. Par exemple, si l’on définit un algorithme par le nombre d’étapes sur une machine de Turing, alors il ne peut pas exister d’algorithme en temps logarithmique, et O(log n) est traité comme O(1)
- Je l’ai appris en cours obligatoire d’informatique dès la 1re année. Il n’y a rien de sorcier : c’est juste une manière de décrire comment la quantité d’opérations augmente lorsque la taille des données d’entrée grandit. En apparence c’est difficile, mais en réalité c’est très simple et limpide
Les visualisations dynamiques m’ont énormément aidé à comprendre. J’aimerais qu’il y ait plus de leçons et de ressources de ce genre
- Ce retour me fait vraiment plaisir, merci
Chaque fois qu’un fil sur la notation Big-O apparaît, j’espère toujours que quelqu’un expliquera enfin le lien entre ce concept et l’anime The Big O. Je ne comprends toujours pas vraiment de quoi parle cet anime
- (descend 4 bières d’un trait)Bon, écoute. Cet anime, c’est comme si on mélangeait successivement Pacific Rim, Dark City et The Matrix
Personnellement, je trouve que la façon la plus efficace de comprendre la notation Big O est de la relier à des situations du quotidien
Je trouve que c’est une magnifique ressource. J’ai envoyé un signal, j’espère qu’il est bien arrivé, et j’ai l’impression d’avoir reçu au passage une petite dose de dopamine
- C’est bien arrivé. Merci