Notation grand O — la complexité temporelle expliquée simplement

La notation grand O indique à quelle vitesse le temps d’exécution ou l’utilisation mémoire d’un algorithme peut augmenter lorsque la taille de l’entrée augmente. Si vous vous demandez : « Que se passe-t-il quand le problème devient beaucoup plus grand ? », grand O est la manière standard d’y répondre.

C’est pour cela qu’on dit que la recherche linéaire est en $O(n)$ et la recherche binaire en $O(\log n)$. Le but n’est pas de prédire un nombre exact de millisecondes sur une machine donnée. Le but est de comparer des tendances de croissance.

Ce que signifie le grand O

Si un algorithme prend un temps $T(n)$ sur une entrée de taille $n$, alors

$$T(n) = O(f(n))$$

signifie que pour certaines constantes $C > 0$ et $n_0$,

$$T(n) \le C f(n) \quad \text{for all } n \ge n_0$$

Cela veut dire que le grand O est une affirmation de majoration sur la croissance pour des entrées suffisamment grandes.

En langage simple : une fois que $n$ est assez grand, le temps d’exécution ne croît pas plus vite qu’un multiple constant de $f(n)$.

Pourquoi le grand O est utile

Le grand O donne une manière indépendante de la machine de comparer des algorithmes. Un programme peut s’exécuter plus vite sur un ordinateur portable que sur un autre, mais la tendance de croissance reste importante.

Cette tendance compte surtout lorsque la taille de l’entrée varie beaucoup. Un algorithme acceptable pour $100$ éléments peut devenir impraticable pour $10^6$ éléments si son taux de croissance est mauvais.

Complexités temporelles courantes en un coup d’œil

• $O(1)$ : le travail reste borné lorsque $n$ augmente.
• $O(\log n)$ : le travail augmente lentement, souvent lorsque la taille du problème est réduite de façon répétée.
• $O(n)$ : le travail augmente à peu près proportionnellement à la taille de l’entrée.
• $O(n \log n)$ : légèrement plus que linéaire, fréquent dans les tris efficaces.
• $O(n^2)$ : le travail augmente comme le carré de la taille de l’entrée, souvent à cause de boucles imbriquées sur les mêmes données.

Ces étiquettes comparent des croissances, pas des vitesses exactes. Un algorithme en $O(n)$ peut quand même être plus lent qu’un algorithme en $O(n^2)$ pour de petites entrées si ses facteurs constants sont grands.

Exemple détaillé : pourquoi la recherche linéaire est en $O(n)$

Supposons que vous parcouriez une liste de gauche à droite pour chercher une valeur cible. Dans le pire des cas, la valeur est absente ou se trouve tout à la fin, donc vous devrez peut-être vérifier chaque élément une fois.

Si la liste contient $n$ éléments, le nombre de vérifications peut être au plus $n$. C’est pourquoi le temps dans le pire des cas est

$$O(n)$$

L’idée utile à retenir est simple : si la taille de la liste double, le nombre maximal de vérifications peut lui aussi à peu près doubler. C’est ce type de comportement que la notation grand O capture.

Ce que le grand O laisse de côté

Le grand O ignore volontairement les facteurs constants et les termes d’ordre inférieur lorsqu’on compare la croissance pour de grandes entrées.

Par exemple, si

$$T(n) = 3n + 2$$

alors $T(n)$ est quand même en $O(n)$. La constante $3$ et le $2$ supplémentaire comptent pour un temps exact, mais ils ne changent pas la tendance principale de croissance.

Cela ne veut pas dire que les constantes n’ont jamais d’importance en pratique. Cela signifie que le grand O répond à une question plus précise : comment le coût change d’échelle lorsque $n$ devient grand.

Erreurs fréquentes avec le grand O

Erreur 1 : traiter le grand O comme un temps d’exécution exact

$O(n)$ ne signifie pas que le temps d’exécution est exactement de $n$ étapes. Cela signifie que la croissance est majorée par un multiple constant de $n$ une fois que $n$ est assez grand.

Erreur 2 : oublier la condition sur les grandes valeurs de $n$

La définition formelle doit seulement être vraie pour tout $n \ge n_0$. Le grand O concerne le comportement asymptotique, pas chaque toute petite entrée.

Erreur 3 : supposer que le grand O signifie toujours le temps d’exécution typique

Dans les discussions sur les algorithmes, le grand O décrit souvent le temps dans le pire des cas, mais c’est une convention liée au contexte. La complexité moyenne et la complexité dans le meilleur des cas sont des questions différentes et doivent être indiquées clairement.

Erreur 4 : comparer les algorithmes uniquement avec le grand O

Le grand O est important, mais l’utilisation mémoire, le coût d’implémentation et les facteurs constants peuvent aussi beaucoup compter dans les systèmes réels.

Où l’on rencontre la notation grand O

Le grand O apparaît en informatique, en mathématiques discrètes et en analyse de performance. Il est particulièrement utile pour comparer des algorithmes de recherche, de tri, de parcours de graphe et de programmation dynamique.

Plus largement, on l’utilise chaque fois qu’on s’intéresse à la manière dont un processus change d’échelle, plutôt qu’à son comportement pour une seule taille fixe.

Essayez un exemple similaire

Prenez une boucle imbriquée simple qui parcourt une grille de taille $n \times n$. Comptez combien de fois l’action intérieure s’exécute. Si le travail total augmente comme $n^2$, vous avez un exemple concret de la raison pour laquelle des boucles répétées sur les mêmes données conduisent souvent à un comportement en $O(n^2)$.