Deux morceaux de code peuvent produire des résultats identiques sur un petit cas de test et se comporter de façon totalement différente une fois que de vraies données arrivent. La notation Big O est la façon dont les informaticiens décrivent précisément cette différence — en décrivant mathématiquement comment le nombre d'opérations croît à mesure que la taille de l'entrée augmente.
Approfondissement A-Level
Ce que signifie vraiment le « O »
Le Big O décrit le taux de croissance d'un algorithme — comment le nombre d'opérations croît à mesure que la taille de l'entrée, traditionnellement appelée n, augmente. Il ignore délibérément les facteurs constants et les petits termes, car la question à laquelle il est censé répondre est « comment cela croît-il », une question dont la réponse ne dépend pas de l'ordinateur sur lequel vous l'exécutez.
Les taux de croissance qui comptent vraiment
Une poignée de taux de croissance couvre presque tous les algorithmes que vous rencontrerez, du meilleur au pire à mesure que les données augmentent :
- O(1) — constant. Le même nombre d'étapes quelle que soit la taille de l'entrée, comme vérifier si une liste est vide.
- O(log n) — logarithmique. Les opérations croissent très lentement quand n augmente — par exemple, la recherche binaire dans une liste triée.
- O(n) — linéaire. Doublez l'entrée, doublez le travail — comme parcourir chaque élément d'une liste non triée une fois.
- O(n²) — quadratique. Doublez l'entrée, le travail quadruple — typique de comparer chaque élément à chaque autre élément.
Pour un petit n, ces courbes se ressemblent — la différence qui détermine quel algorithme survit réellement aux données du monde réel n'apparaît que lorsque n devient grand, et c'est exactement ce domaine que le Big O est conçu pour décrire.
Try it yourself — drag the slider to change the input size (n), and watch how many operations each growth rate actually needs.
Input size: n = 10
At n = 10, an O(n²) approach needs 100 operations — 10× more than the O(n) approach doing the exact same job.
Un algorithme quadratique, O(n²), qui effectue 100 opérations pour 10 éléments en effectue 1 000 000 pour 1 000 éléments — pas 100 fois plus de travail pour 100 fois plus de données, mais 10 000 fois plus.
Question type examen
Un algorithme prend 8 opérations pour 4 éléments, 32 opérations pour 8 éléments, et 128 opérations pour 16 éléments. Déterminez son taux de croissance Big O, en montrant votre raisonnement. [3 points]
Afficher la réponse modèle et le barème
- Comparez les cas consécutifs où n double : 4 → 8, et 8 → 16 (1 point)
- Le nombre d'opérations quadruple à chaque fois : 8 → 32 (×4), et 32 → 128 (×4) (1 point)
- Quand doubler n fait quadrupler le nombre d'opérations (×4 = ×2²), c'est la signature d'une croissance quadratique : O(n²) (1 point)
Ce que vérifie l'examinateur : identifiez le motif précis entre les doublements de n et le multiplicateur résultant sur les opérations — ce rapport (ici, ×4 par doublement) est ce qui identifie réellement le taux de croissance, pas les chiffres bruts pris isolément.
Erreur fréquente : supposer une croissance linéaire simplement parce que les nombres « augmentent de façon régulière », sans vérifier la relation de doublement qui distingue O(n) (×2 par doublement de n) de O(n²) (×4 par doublement).
Pourquoi la différence entre taux de croissance compte en pratique
Avec de petites données de test, un algorithme O(n²) et un algorithme O(n log n) peuvent tous deux se terminer en une fraction de seconde — la différence est invisible. Faites grandir la même entrée jusqu'à la taille qu'un vrai produit gère réellement, et l'approche O(n²) peut prendre de véritables heures là où l'approche O(n log n) prend des secondes.
Pourquoi cela compte au-delà d'écrire du code correct
N'importe quel programmeur peut écrire du code qui produit la bonne réponse. Si l'informatique est quelque chose que vous ou votre enfant devriez comprendre en expliquant pourquoi une approche est meilleure qu'une autre, pas seulement la syntaxe, c'est exactement ce que propose notre tutorat d'informatique GCSE et A-Level, et vous pouvez voir le parcours d'apprentissage complet ici.
Questions fréquentes
Pourquoi ignorons-nous les constantes et les petits termes — cela ne fait-il pas perdre des informations utiles ?
Le Big O est délibérément conçu pour répondre à une question spécifique — comment le temps d'exécution croît-il quand l'entrée devient très grande — et plus n est grand, moins les constantes comptent. Le Big O ne raconte pas toute l'histoire des performances, mais il prédit correctement quel algorithme l'emporte une fois que les données sont suffisamment grandes.
Un Big O plus faible est-il toujours le meilleur choix en pratique ?
Pas automatiquement — pour de petites entrées, un algorithme avec un moins bon Big O mais un facteur constant bien plus petit peut réellement s'exécuter plus vite en pratique, car le point de croisement où le « meilleur » algorithme commence à gagner peut n'arriver qu'à un n bien plus grand.
Comment le Big O est-il réellement utilisé au quotidien par les programmeurs, pas seulement en entretien ?
C'est la façon dont un développeur prédit si une approche fonctionnera encore une fois que de vraies (très grandes) données arriveront. Chercher dans une liste non triée est en O(n) ; la recherche binaire dans une liste triée est en O(log n) — une différence invisible avec 10 éléments et immense avec 10 millions.
Notes et avis des lecteurs
Notez cet article sur plusieurs aspects — votre avis aide les autres lecteurs, et nous aide à nous améliorer.
Cet article vous a-t-il été utile ?
Dites-nous ce que vous en pensez — une correction, une question restée sans réponse, ou un sujet que vous aimeriez voir traité ensuite.
Vous préférez en parler ? Réservez un appel vidéo gratuit au moment qui vous convient : 15 minutes pour une question rapide, 30 pour le reste. Les horaires s'affichent dans votre fuseau horaire.
À propos de l'auteur
Sudershan Soni
Fondateur et tuteur principal chez Mostak Services — tuteur de mathématiques, sciences, informatique et STEM titulaire d'un Master, avec plus de 20 ans d'expérience professionnelle, enseignant à des élèves du 11+ et du GCSE jusqu'à l'A-Level et au-delà, en ligne dans le monde entier.
Lire le profil complet