Programmation · concepts · algorithmes
Qu'est-ce que la notation Big O ?
La notation Big O est une façon de décrire comment le temps d'exécution (ou l'utilisation mémoire) d'un algorithme croît à mesure que son entrée grandit. Elle répond à une question : quand la quantité de données double, ou grandit mille fois, est-ce que votre code reste rapide, ralentit un peu, ou se bloque complètement ? Elle ignore délibérément les secondes exactes et la vitesse de la machine, et se concentre sur la forme de la croissance, parce que c'est ce qui décide si un code qui fonctionne sur 100 éléments fonctionne encore sur 100 millions.
Pourquoi ne pas simplement mesurer le temps ?
Parce que les secondes dépendent de la machine, du langage, du compilateur et de ce qui tourne par ailleurs. Exécutez le même code sur un ordinateur portable et sur un serveur et vous obtenez des chiffres différents. Le Big O met tout cela de côté et mesure quelque chose de plus durable : comment le travail évolue avec la taille de l'entrée, généralement appelée n. Deux algorithmes peuvent tous deux prendre « quelques millisecondes » sur une petite entrée, et pourtant l'un reste rapide à grande échelle tandis que l'autre devient inutilisable. Le Big O est la façon dont on les distingue avant de heurter ce mur.
Les complexités courantes, de la meilleure à la pire
Voici les taux de croissance que vous rencontrerez le plus souvent, du plus rapide à l'échelle au plus dangereux :
| Notation | Nom | Idée générale |
|---|---|---|
| O(1) | Constant | Le même travail quelle que soit la taille de l'entrée - par exemple lire array[5]. |
| O(log n) | Logarithmique | Divise le problème par deux à chaque étape - par exemple la recherche binaire. |
| O(n) | Linéaire | Le travail croît au même rythme que l'entrée - par exemple parcourir une liste une fois. |
| O(n log n) | Linéarithmique | Le mieux possible pour un tri général - par exemple mergesort. |
| O(n²) | Quadratique | Une boucle dans une boucle - correct pour 100 éléments, pénible pour un million. |
| O(2ⁿ) | Exponentielle | Double à chaque élément ajouté - utilisable uniquement pour de toutes petites entrées. |
| O(n!) | Factorielle | Chaque ordre possible de l'entrée - praticable seulement pour un très petit n. |
Pourquoi on abandonne les constantes et les petits termes
Le Big O s'intéresse à la croissance, pas aux comptes exacts, il simplifie donc. Si un algorithme effectue 2n + 3 étapes, cela s'écrit O(n) : le 2 et le 3 ne changent pas la forme de la courbe quand n devient grand. De même n² + n devient O(n²), parce que le terme quadratique domine dès que n est grand. C'est pourquoi le Big O concerne le terme dominant - la partie qui décide du comportement à grande échelle - et non une lecture précise au chronomètre.
Un exemple concret
Supposons que vous vouliez vérifier si une liste contient un doublon. Une approche compare chaque élément avec tous les autres - deux boucles imbriquées, à peu près n × n comparaisons, donc O(n²). Une autre approche ajoute chaque élément à un hash set et vérifie l'appartenance au fur et à mesure - un seul passage, donc O(n). Sur 1 000 éléments, la version quadratique effectue environ un million de comparaisons ; sur 100 000 éléments elle en effectue dix milliards, tandis que la version linéaire en effectue 100 000. Même tâche, destin radicalement différent à grande échelle. Cet écart est exactement ce que le Big O est conçu pour révéler.
Pire cas, cas moyen et meilleur cas
À proprement parler, le Big O décrit une borne supérieure - généralement le pire cas, le maximum de travail que l'algorithme pourrait effectuer. Vous verrez aussi deux notions apparentées : Big Omega (Ω) pour le meilleur cas, une borne inférieure, et Big Theta (Θ) quand le meilleur et le pire cas croissent au même rythme, donnant une borne serrée. Dans l'usage courant, on dit « Big O » de façon lâche pour désigner la croissance dans le pire cas, parce que c'est ce autour de quoi on planifie : on veut savoir à quel point ça peut mal tourner, pas à quel point on pourrait parfois avoir de la chance.
La complexité en espace aussi
La même notation décrit la mémoire, pas seulement le temps. Un algorithme qui copie toute l'entrée dans une nouvelle structure utilise O(n) d'espace supplémentaire ; un algorithme qui réarrange l'entrée sur place utilise O(1) d'espace supplémentaire. Sur de grandes données, la mémoire peut être la vraie limite, il vaut donc la peine de se demander à la fois « comment le temps croît-il ? » et « comment la mémoire croît-elle ? »
Comment raisonner sur votre propre code
- Comptez les boucles sur l'entrée. Un seul passage est généralement O(n) ; une boucle dans une boucle sur les mêmes données est généralement O(n²).
- Diviser par deux, c'est un logarithme. Si chaque étape écarte la moitié des données restantes (comme la recherche binaire), c'est O(log n).
- Les recherches dans un hash map/set sont ~O(1). Remplacer un parcours imbriqué par une recherche par hachage est la façon classique de transformer un O(n²) en O(n).
- Abandonnez les constantes. Trois passages simples séparés restent O(n), pas O(3n) - c'est la forme qui compte.
FAQ
Un Big O plus faible est-il toujours plus rapide ? À grande échelle, oui - mais pas toujours pour de petites entrées. Les constantes et le surcoût que le Big O ignore peuvent faire qu'une méthode O(n²) batte une méthode O(n log n) sur une poignée d'éléments. Le Big O vous dit qui l'emporte à mesure que les données grandissent, ce qui est généralement ce qui compte.
Quelle est la meilleure complexité possible ? O(1), le temps constant - le travail ne croît pas du tout avec l'entrée. Ensuite vient O(log n). Pour les problèmes qui doivent examiner chaque élément au moins une fois, O(n) est le plancher.
Pourquoi O(n log n) est-il spécial pour le tri ? C'est la borne inférieure prouvée pour le tri général par comparaisons, donc mergesort, heapsort et les bonnes implémentations de quicksort visent toutes cette borne. On ne peut généralement pas trier des données arbitraires plus vite par des comparaisons seules.
Ai-je besoin du Big O pour coder au quotidien ? Vous n'avez pas besoin des maths formelles, mais l'intuition est précieuse : reconnaître quand une boucle imbriquée va exploser sur une grande entrée, ou quand une recherche par hachage vous sauve, évite des classes entières de bugs de performance.