La notation grand O pour débutants : O(1), O(n), O(n au carré) et O(log n) expliqués

La croissance, pas le chronomètre

Le grand O ne parle pas du nombre de secondes que prend une tâche sur ton portable. Il décrit comment le travail évolue quand l'entrée grandit. Deux algorithmes peuvent tous deux être en O(n), et pourtant l'un s'exécute deux fois plus vite sur du matériel réel grâce à un facteur constant plus petit. Le grand O jette délibérément cette constante, car à n assez grand la forme de la courbe de croissance domine tout multiplicateur fixe.

La notation ne garde aussi que le terme qui croît le plus vite. Un algorithme qui effectue 3n au carré plus 5n plus 200 opérations est simplement en O(n au carré), car dès que n est grand le terme carré écrase le reste. Voilà pourquoi le grand O est une loupe grossière mais puissante : il te donne la classe de comportement, exactement ce qu'il faut pour décider si une solution survivra à cent fois plus de données.

Les quatre classes courantes

O(1) est le temps constant : lire un élément de tableau par index ou vérifier une clé de table de hachage demande le même effort que la collection contienne dix éléments ou dix millions. O(log n) est logarithmique : la recherche binaire divise par deux les données restantes à chaque étape, si bien que chercher dans une liste triée d'un milliard d'éléments ne prend qu'environ trente comparaisons. La division par deux est l'image miroir du doublement observé lors de la conversion de nombres entre bases.

O(n) est linéaire : additionner chaque élément ou parcourir une liste une fois touche chaque élément exactement une fois, si bien que le travail monte en ligne droite avec n. O(n au carré) est quadratique et provient généralement de boucles imbriquées, comme comparer chaque paire d'éléments. À n de 1 000 cela fait un million d'opérations ; à n de 1 000 000 cela fait mille milliards, et c'est là qu'un code quadratique naïf devient discrètement inutilisable.

Pourquoi la classe choisie compte

La complexité sépare un prototype qui marche sur ton fichier de test d'un logiciel qui survit aux données de production. Trier avec un algorithme en O(n au carré) paraît instantané sur cent lignes et gèle sur un million. Passer à un tri en O(n log n) garde la même tâche sous la seconde. L'algorithme que tu choisis, et non la vitesse de la machine, fixe le plafond de données que tu peux traiter.

Cela dit, le grand O est asymptotique : il décrit le comportement quand n tend vers l'infini. Pour de petites entrées, une routine plus simple en O(n au carré) peut battre une routine sophistiquée en O(n log n) au lourd surcoût. La règle pratique est de connaître la classe de chaque opération centrale, puis d'optimiser les parties qui verront vraiment un grand n, plutôt que de courir après les constantes d'un code qui ne traite que de minuscules entrées.

Questions fréquentes

Un grand O plus bas est-il toujours plus rapide ?

Pas pour de petites entrées. Le grand O ignore les facteurs constants, si bien qu'une méthode en O(n log n) à lourde mise en place peut perdre face à une simple boucle en O(n au carré) quand n est minuscule. La classe plus basse l'emporte dès que l'entrée est assez grande.

Quelle est la différence entre O(log n) et O(n log n) ?

O(log n) fait une seule passe logarithmique, comme une recherche binaire unique. O(n log n) effectue une quantité logarithmique de travail pour chacun des n éléments, ce qui correspond au coût des algorithmes de tri efficaces comme le tri fusion.

Le grand O couvre-t-il aussi la mémoire ?

Oui. La même notation décrit la complexité en espace, la mémoire supplémentaire qu'un algorithme requiert quand n grandit. Un tri en place peut utiliser O(1) d'espace supplémentaire, tandis qu'un tri qui copie les données utilise O(n).

Pourquoi ignore-t-on les constantes et les termes inférieurs ?

Parce qu'à grand n le terme qui croît le plus vite domine tout le reste, et les constantes dépendent d'un matériel que tu ne contrôles pas. Les supprimer donne une comparaison portable de la façon dont les algorithmes évoluent, indépendante de toute machine.