En bref
La complexité d’un algorithme mesure comment son coût — le nombre d’opérations, donc le temps — grandit quand la taille des données grandit. Deux méthodes justes peuvent différer d’un facteur un million : chercher un nom dans l’annuaire en le lisant ligne à ligne, ou en l’ouvrant au milieu pour éliminer une moitié à chaque coup — les deux trouvent, la seconde en une poignée d’étapes là où la première en demande des milliers. On note cette croissance avec le grand O : O(1) pour le coût constant (l’accès direct à une case), O(log n) pour le coût qui grandit à peine (la dichotomie de l’annuaire), O(n) pour le coût proportionnel (lire toute la liste), O(n²) pour le coût qui explose (la double boucle qui compare tout à tout). Nul besoin de mathématiques : compter les boucles donne l’intuition — et cette intuition sépare le code qui tient dix éléments de celui qui tient dix millions.
Ton algorithme fonctionne — parfait. Nouvelle question, celle des grands : fonctionnera-t-il encore quand la liste passera de dix éléments à dix millions ? Comprendre la complexité d’un algorithme — l’art d’évaluer comment le coût grandit avec les données — est la boussole qui sépare les méthodes qui tiennent la charge de celles qui s’effondrent ; ce guide la met en main sans une ligne de mathématiques, dans la lignée de notre guide complet pour apprendre à coder.
La complexité, expliquée avec les mains
Mission : trouver « Martin » dans un annuaire papier de 10 000 noms. Méthode 1 : lire ligne à ligne depuis la première page — ça marche, et dans le pire des cas, 10 000 lectures. Méthode 2 : ouvrir au milieu — « Lambert »… Martin vient après : toute la première moitié disparaît d’un geste ; rouvrir au milieu de ce qui reste, recommencer. Chaque coup divise le problème par deux : 10 000, 5 000, 2 500… en 14 ouvertures, c’est réglé. Deux méthodes justes, même résultat — et un rapport de coût de 10 000 contre 14. Voilà toute la complexité : non pas « ma machine est-elle rapide ? », mais « comment le nombre d’étapes de MA MÉTHODE grandit-il quand les données grandissent ? » — la question qui ne dépend ni du processeur ni du langage, seulement de la pensée.
Et pourquoi l’annuaire autorise-t-il la méthode magique ? Parce qu’il est trié — sur une pile de noms en vrac, impossible d’éliminer une moitié : il faudrait tout lire. Tu viens de toucher la grande leçon du domaine : la performance se prépare — organiser ses données (trier, indexer) coûte une fois et rend toutes les recherches suivantes fulgurantes ; c’est exactement ainsi que les moteurs de recherche répondent en une fraction de seconde, et la raison d’être des index que tu croiseras des bases de données aux bibliothèques. La complexité n’est pas une matière d’examen : c’est l’art de choisir sa méthode avant que les données ne grossissent.
À quoi ça ressemble dans le code
Les informaticiens notent la croissance avec le grand O — lis-le « de l’ordre de ». Quatre paliers couvrent l’essentiel du quotidien, et tu sais déjà les reconnaître en comptant les boucles. O(1), le coût constant : aucune boucle — nombres[3] saute directement à la case du tableau, que la liste ait dix ou dix millions d’éléments : une opération. O(n), le coût proportionnel : une boucle qui visite tout — for n in nombres: pour trouver le maximum : deux fois plus de données, deux fois plus de tours ; honnête, très fréquent, parfaitement sain.
O(n²), le coût qui explose : une boucle dans une boucle — comparer chaque élément à tous les autres (le double for des doublons, les tris naïfs) : 10 éléments, 100 opérations ; 10 000 éléments, 100 millions — la courbe qui transforme un clic en café. O(log n), le coût de l’annuaire enfin : la division par deux à chaque étape — la recherche dichotomique sur une liste triée, quelques dizaines d’opérations pour des millions d’éléments, souvent écrite avec la récursivité qui lui va comme un gant. Le réflexe pratique qui découle de tout cela tient en une phrase d’atelier : une boucle = proportionnel, deux boucles imbriquées = danger sur les grandes données, division par deux = luxe — et les outils intégrés des langages (le tri de Python, les recherches des bibliothèques) embarquent les méthodes raffinées : les utiliser, c’est hériter de cinquante ans d’optimisation, comme tu le pratiques depuis les bases.
Les pièges classiques (et comment les éviter)
Piège 1 : optimiser trop tôt. Tordre un script de cinquante lignes pour gagner des microsecondes est le contresens du débutant pressé — sur dix éléments, tout est instantané, et la lisibilité vaut plus que la vitesse. Le remède, règle d’or du métier : d’abord juste, ensuite clair, enfin rapide — si nécessaire. La complexité sert à choisir la méthode quand les données sont (ou seront) grandes, pas à torturer les petites. Piège 2 : la double boucle invisible. Une boucle qui contient « chercher dans la liste » cache un O(n²) — la recherche EST une boucle déguisée ; le remède : se demander, pour chaque opération dans une boucle, « et elle, combien coûte-t-elle ? ».
Piège 3 : confondre vitesse de machine et complexité de méthode. Un ordinateur deux fois plus rapide divise le temps par deux — face à un O(n²) qui explose, c’est un seau d’eau sur un incendie : la méthode prime toujours sur le matériel, à grande échelle. Piège 4 : réciter les O sans intuition. Le grand O s’apprend avec les mains, pas par cœur : chronomètre toi-même la double boucle des doublons sur 100, puis 10 000 éléments — la courbe vécue vaut tous les tableaux. La boussole est en main — et elle t’accompagnera longtemps : des choix de structures aux entretiens d’embauche (où la question « quelle est la complexité ? » est un grand classique), en passant par tous les exercices où deux solutions justes ne se valent pas. La langue du métier compte peu de mots plus rentables que ce grand O — tu viens de l’apprendre par l’annuaire, la meilleure porte qui soit.
Questions fréquentes
C’est quoi la complexité d’un algorithme, en une phrase ?
La façon dont son nombre d’opérations grandit quand la taille des données grandit : proportionnellement (une boucle, O(n)), au carré (deux boucles imbriquées, O(n²)), à peine (division par deux à chaque étape, O(log n)) ou pas du tout (accès direct, O(1)). C’est la mesure qui prédit si le code tiendra la charge.
Que signifie la notation O(n) ?
« De l’ordre de n » : le coût grandit proportionnellement à la taille n des données — deux fois plus d’éléments, environ deux fois plus d’opérations. C’est le profil d’une boucle simple qui visite chaque élément une fois, comme la recherche du maximum d’une liste.
Pourquoi une double boucle est-elle dangereuse ?
Parce que son coût grandit au carré — O(n²) : comparer chaque élément à tous les autres demande 100 opérations pour 10 éléments, mais 100 millions pour 10 000. Anodine sur de petites données, la double boucle imbriquée devient le premier suspect quand un programme rame sur de grandes listes.
C’est quoi la recherche dichotomique ?
La méthode de l’annuaire : sur des données triées, on regarde le milieu et on élimine une moitié à chaque étape — quatorze étapes suffisent pour 10 000 éléments, une trentaine pour un milliard. Son coût O(log n) illustre la grande leçon : organiser ses données (les trier) rend les recherches fulgurantes.
Sources
- Python.org — la documentation officielle du langage
- MDN Web Docs — la référence JavaScript en français
Cet article a une vocation informative et pédagogique. Les plateformes, outils et formations éventuellement cités le sont à titre d’exemple ; compare plusieurs options avant de t’engager ou de payer.