La Notation Grand O : Comprendre la Complexité des Algorithmes Simplement

Comprenez la notation grand O avec des exemples simples : O(1), O(log n), O(n), O(n log n), O(n²), et apprenez à estimer l’efficacité d’un algorithme.

Partager sur Linkedin Partager sur WhatsApp

Temps de lecture estimé : 8 minutes

Image de l'article La Notation Grand O : Comprendre la Complexité des Algorithmes Simplement

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 = 10n = 1 000n = 1 000 000
O(1)111
O(log n)~3~10~20
O(n)101 0001 000 000
O(n log n)~33~10 000~20 000 000
O(n²)1001 000 0001 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

  1. Une boucle qui parcourt les n éléments indique généralement O(n).
  2. Deux boucles imbriquées sur les mêmes données indiquent généralement O(n²).
  3. Des boucles successives s’additionnent : O(n) + O(n) reste O(n).
  4. Une boucle qui divise le problème par deux à chaque tour indique généralement O(log n).
  5. 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.

Flexbox ou CSS Grid : Quand Utiliser l’Un ou l’Autre

Flexbox gère une dimension, Grid en gère deux. Comprenez la différence, les propriétés clés et comment combiner les deux dans un vrai projet.

RECHERCHEV et RECHERCHEX : Retrouver une Donnée dans un Tableau Excel

Apprenez à utiliser RECHERCHEV et RECHERCHEX dans Excel : syntaxe, différences, erreurs fréquentes et astuces pour des recherches fiables.

Comment un Modèle de Langage Génère du Texte : Tokens, Probabilités et Contexte

Découvrez comment fonctionne un modèle de langage : découpage en tokens, prédiction du mot suivant, fenêtre de contexte, hallucinations et bonnes pratiques.

Mémoire Virtuelle et Fichier d’Échange : Ce Qui Se Passe Quand la RAM Est Pleine

Comment un système d’exploitation fait tenir plus de programmes que la RAM ne peut en contenir, et pourquoi la machine ralentit.

Qu’est-ce qu’une API REST ? Le langage commun des applications

Comprendre les API REST : ressources, méthodes HTTP, codes de statut et bonnes pratiques, expliqués simplement.

Clés Primaires et Clés Étrangères : Comprendre les Relations entre Tables

Clé primaire, clé étrangère, intégrité référentielle : les notions de base pour organiser correctement une base de données relationnelle.

Git et le Contrôle de Version : Comprendre les Bases

Découvrez à quoi sert un système de contrôle de version, les commandes essentielles de Git et les bonnes pratiques pour travailler en équipe.

Qu’est-ce que le phishing et comment s’en protéger ?

Découvrez ce qu’est le phishing, comment reconnaître ces tentatives d’arnaque en ligne et quels réflexes adopter pour protéger vos données.