Deux programmes peuvent résoudre exactement le même problème et pourtant, l’un répondre en une fraction de seconde tandis que l’autre tourne pendant des heures. La différence vient rarement du langage ou de la machine : elle vient presque toujours de l’algorithme. Pour comparer des algorithmes de manière objective, les développeurs utilisent un outil appelé notation grand O (ou « Big O »). Dans cet article, vous allez découvrir ce qu’elle signifie, quelles sont les complexités les plus courantes, comment les repérer dans le code et pourquoi cette notion est si importante en programmation.
Qu’est-ce que la notation grand O ?
La notation grand O décrit la façon dont le temps d’exécution (ou la mémoire utilisée) d’un algorithme augmente lorsque la taille des données d’entrée augmente. On note cette taille n. La notation ne donne pas un nombre de secondes, mais une tendance de croissance. Elle répond à une question simple : si je double la quantité de données, que devient le travail effectué par l’algorithme ?
Par convention, on utilise surtout la notation grand O pour décrire le pire cas, c’est-à-dire la situation où l’algorithme doit fournir le plus d’effort. On obtient ainsi une borne supérieure : on sait qu’au maximum, l’algorithme croîtra à ce rythme.
Deux règles de simplification
Comme la notation s’intéresse au comportement pour de grandes entrées, on applique deux simplifications :
- On ignore les constantes. Un algorithme qui effectue 3n opérations et un autre qui en effectue n sont tous deux en O(n). Avec des données très volumineuses, ce qui compte, c’est que les deux croissent de manière linéaire.
- On garde uniquement le terme dominant. Si un algorithme effectue n² + 5n + 10 opérations, on écrit O(n²), car lorsque n devient grand, le terme n² écrase tous les autres.
Les complexités les plus courantes
O(1) : temps constant
Le travail ne dépend pas de la taille de l’entrée. Accéder à un élément d’un tableau par son indice, par exemple tableau[5], prend le même temps que le tableau contienne dix ou dix millions d’éléments.
O(log n) : temps logarithmique
À chaque étape, le problème est divisé par deux. L’exemple classique est la recherche dichotomique dans une liste triée : on regarde l’élément du milieu, on élimine la moitié qui ne peut pas contenir la valeur cherchée, puis on recommence. Pour mille éléments, une dizaine de comparaisons suffisent ; pour un million, une vingtaine.
O(n) : temps linéaire
Le travail augmente proportionnellement à l’entrée. Parcourir une liste pour trouver sa valeur maximale ou chercher un élément dans une liste non triée sont des opérations linéaires : si la liste double, le temps double aussi.
O(n log n) : temps quasi linéaire
C’est la complexité typique des algorithmes de tri efficaces, comme le tri fusion, ainsi que du tri rapide dans le cas moyen. Elle croît un peu plus vite que O(n), mais beaucoup moins vite que O(n²).
O(n²) : temps quadratique
On la rencontre souvent avec deux boucles imbriquées qui parcourent la même collection, par exemple pour comparer chaque élément à tous les autres. Les tris simples, comme le tri à bulles, le tri par sélection et le tri par insertion, sont en O(n²) dans le pire cas.
O(2ⁿ) : temps exponentiel
Le travail double à chaque élément ajouté. Tester tous les sous-ensembles possibles d’un ensemble en est un exemple. Ces algorithmes deviennent impraticables très rapidement, même avec des entrées modestes.
Comparer la croissance
Le tableau suivant donne un ordre de grandeur du nombre d’opérations pour différentes tailles d’entrée (logarithme en base 2) :
| Complexité | n = 10 | n = 1 000 | n = 1 000 000 |
|---|---|---|---|
| O(1) | 1 | 1 | 1 |
| O(log n) | ~3 | ~10 | ~20 |
| O(n) | 10 | 1 000 | 1 000 000 |
| O(n log n) | ~33 | ~10 000 | ~20 000 000 |
| O(n²) | 100 | 1 000 000 | 1 000 000 000 000 |
Regardez la dernière ligne : avec un million d’éléments, un algorithme quadratique demanderait mille milliards d’opérations, alors qu’un algorithme en O(n log n) en demanderait environ vingt millions. C’est toute la différence entre une réponse immédiate et un programme qui semble bloqué.
Repérer la complexité dans le code
- Une boucle qui parcourt les n éléments indique généralement O(n).
- Deux boucles imbriquées sur les mêmes données indiquent généralement O(n²).
- Des boucles successives s’additionnent : O(n) + O(n) reste O(n).
- Une boucle qui divise le problème par deux à chaque tour indique généralement O(log n).
- Les fonctions de bibliothèque comptent aussi : trier une liste à l’intérieur d’une boucle peut multiplier la complexité.
Prenons un exemple concret : pour vérifier si une liste contient des doublons, on peut comparer chaque paire d’éléments avec deux boucles imbriquées, ce qui donne O(n²). Une autre approche consiste à parcourir la liste une seule fois en mémorisant les valeurs déjà vues dans un ensemble (set), dont la recherche est en O(1) en moyenne. On obtient alors O(n) en temps, au prix de O(n) de mémoire supplémentaire.
Temps et mémoire : un compromis
L’exemple précédent illustre un point essentiel : la notation grand O ne concerne pas seulement le temps, mais aussi l’espace mémoire. De nombreuses optimisations consistent à utiliser plus de mémoire pour gagner du temps, ou l’inverse. Le bon choix dépend du contexte : un système embarqué avec peu de mémoire et un serveur puissant ne privilégieront pas forcément la même solution.
Il faut aussi garder à l’esprit que la notation décrit le comportement pour de grandes entrées. Sur de petites listes, un algorithme simple en O(n²) peut parfois être plus rapide en pratique qu’un algorithme sophistiqué, car les constantes ignorées par la notation pèsent davantage quand n est petit.
Conclusion
La notation grand O offre un langage commun pour parler d’efficacité. Savoir distinguer O(1), O(log n), O(n), O(n log n) et O(n²) permet d’anticiper si une solution tiendra la route quand les données augmenteront, et de choisir des structures de données et des algorithmes adaptés. Pas besoin de formules compliquées : il suffit d’observer comment le travail se répète dans le code. Pour consolider ces bases, découvrez les cours gratuits de logique de programmation et d’algorithmique proposés sur Cursa.










