AnalyseNotion · Glossaire
Grand O
La notation grand O (ou notation de Landau O) est un outil d'analyse asymptotique décrivant le comportement d'une fonction au voisinage d'un point ou à l'infini. On dit que f(x) = O(g(x)) lorsque x tend vers un point a s'il existe deux constantes C > 0 et δ > 0 telles que, pour tout x du domaine commun de définition vérifiant 0 < |x − a| < δ, on ait |f(x)| ≤ C·|g(x)|. Cette notation permet de comparer les vitesses de croissance des fonctions et est fondamentale en analyse, en théorie des nombres et en informatique pour exprimer la complexité des algorithmes.
Sommaire
Ce que vous allez apprendre
- Interpréter le grand O comme une majoration asymptotique à constante fixe.
- Vérifier pas à pas que 3n² + 2n + 7 est grand O de n².
- Distinguer grand O, petit o et équivalence.
- Repérer les erreurs liées au seuil, à la constante et aux valeurs absolues.
En clair
Imaginez que le nombre n d’éléments à traiter augmente. Une quantité comme 3n2 + 2n + 7 finit par être contrôlée par un multiple de n2. Le grand O exprime précisément cette idée de plafond, valable à partir d’un certain seuil.
Il ne donne ni la valeur exacte ni le meilleur plafond possible. Il retient une échelle de croissance : ici, le terme quadratique gouverne le comportement lorsque n devient grand.
Définition
Le grand O, aussi appelé notation de Landau O, décrit une domination asymptotique. Soient une fonction f à majorer et une fonction de comparaison g. Lorsque la variable x tend vers un point a, écrire signifie qu’il existe deux constantes réelles C et strictement positives telles que, pour tout x du domaine commun de définition vérifiant , on ait .
La même lecture s’applique à l’infini : l’inégalité doit alors être vraie à partir d’un certain seuil. La constante C reste fixe tandis que x varie. Les valeurs absolues rendent la comparaison indépendante du signe des deux fonctions.
Cette écriture compare des vitesses de croissance sans affirmer que les fonctions sont égales ni qu’elles ont exactement le même ordre. Elle sert en analyse, en théorie des nombres et en informatique, notamment pour exprimer une borne de complexité algorithmique.
Un exemple, pas à pas
On veut établir une borne pour la quantité f définie par .
Données : la fonction de comparaison est ; la variable n est un entier positif ; le seuil choisi est .
Données : la fonction de comparaison est ; la variable n est un entier positif ; le seuil choisi est .
1. Pour tout entier n supérieur ou égal à 1, on a n ≤ n2. Donc 2n ≤ 2n2.
2. Toujours pour n ≥ 1, on a 1 ≤ n2. Donc 7 ≤ 7n2.
3. En additionnant les trois majorations, on obtient :
4. La constante C peut donc valoir 12. Avec le seuil n0 = 1, la définition donne .
Le contrôle au seuil est refaisable : f(1) = 3 + 2 + 7 = 12 et 12 × 12 = 12. L’égalité au premier rang respecte bien la borne, puis le graphique rend visible son maintien.
En pratique
Pour comparer la croissance de deux fonctions, on cherche une constante et un voisinage où l’une reste sous un multiple de l’autre. Si le quotient tend au contraire vers zéro, le petit O décrit plus précisément cette domination stricte.
Pour étudier un algorithme, le grand O fournit une borne de la quantité de ressources quand la taille des données augmente. Si l’on doit connaître un coût exact pour une petite taille, on conserve plutôt la formule complète et ses constantes.
Pour encadrer un reste ou une erreur près d’un point, on vérifie l’inégalité dans un voisinage annoncé. Si l’on cherche un rapport qui tend vers 1, une équivalence est l’information adaptée.
À ne pas confondre
Petit O. Lorsque g est non nulle au voisinage considéré, écrire impose que tende vers zéro dans la limite étudiée, alors que le grand O demande seulement que ce quotient reste borné. Ainsi, lorsque n tend vers l’infini, n2 est grand O de n2, mais pas petit O de n2.
Équivalence. Lorsque g est non nulle au voisinage considéré, dire que f est équivalente à g exige que tende vers 1 dans la limite étudiée. La fonction 3n2 + 2n + 7 est grand O de n2, mais elle n’est pas équivalente à n2 puisque le quotient tend vers 3 lorsque n tend vers l’infini.
Limites et pièges
Oublier le seuil. Une borne asymptotique n’a pas à être vraie partout. Si une inégalité échoue pour quelques petites valeurs mais devient vraie après un rang n0, il faut annoncer ce seuil au lieu de rejeter la relation.
Faire varier la constante. Le nombre C doit être choisi une fois pour toutes dans le voisinage considéré. Une « constante » qui dépend de n ne prouve rien ; dans l’exemple, C = 12 fonctionne pour chaque entier n ≥ 1.
Ignorer les valeurs absolues. Comparer directement des valeurs signées peut masquer une amplitude trop grande. Il faut contrôler |f(x)| par C|g(x)|, notamment lorsque l’une des fonctions change de signe.
Lire une estimation exacte. La relation fournit une majoration, pas le coefficient dominant ni une égalité. Pour une valeur précise, il faut revenir à f(n) = 3n2 + 2n + 7.
Pour aller plus loin
Petit O — Pour reconnaître quand une fonction devient négligeable devant une autre, au lieu d’être seulement dominée par un multiple.
notation de Landau — Pour replacer le grand O dans la famille de notations qui comparent les comportements asymptotiques.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres