Notations Asymptotiques: O, Ω et Θ

Bonjour. Dans la leçon précédente, nous avons exploré la nature de la récursivité et appris à visualiser l'exécution d'un algorithme via son arbre d'appels. Vous avez notamment observé que pour calculer fibonacci(4), l'appel à fibonacci(2) était effectué plusieurs fois, suggérant une certaine inefficacité. Cette observation intuitive nous amène à la question fondamentale de l'analyse d'algorithmes : comment mesurer et comparer rigoureusement l'efficacité d'un algorithme ?

Cette leçon constitue la deuxième étape de notre étude des fondements de l'analyse d'algorithmes. L'objectif est de maîtriser le vocabulaire mathématique essentiel pour cette discipline : les notations asymptotiques. Vous apprendrez à définir et distinguer les notations O, Ω et Θ avec des exemples formels. La maîtrise de ces notations n'est pas négociable pour l'Agrégation ; elle est le socle sur lequel repose toute discussion sérieuse sur la performance des algorithmes.

1. Comportement Asymptotique : L'Idée Générale

En analyse d'algorithmes, nous nous intéressons moins au temps d'exécution exact sur une machine donnée (qui dépend du processeur, du compilateur, etc.) qu'à l'ordre de grandeur de la croissance du nombre d'opérations en fonction de la taille de l'entrée, $n$ . Nous étudions le comportement de l'algorithme lorsque $n$ devient très grand. C'est ce qu'on appelle l'analyse asymptotique.

Pour ce faire, nous utilisons un ensemble de notations (O, Ω, Θ) qui nous permettent de classer les fonctions de complexité.

O (Grand O) : Fournit une borne supérieure asymptotique. "La complexité ne croît pas plus vite que..."
Ω (Grand Oméga) : Fournit une borne inférieure asymptotique. "La complexité ne croît pas moins vite que..."
Θ (Grand Thêta) : Fournit une borne étanche. "La complexité croît au même rythme que..."

La vidéo suivante de Abdul Bari introduit ces trois concepts de manière très claire.

1.8.1 Asymptotic Notations Big Oh - Omega - Theta #1

Cette vidéo est une excellente introduction conceptuelle. Elle présente les trois notations, explique leur rôle (borne supérieure, inférieure, moyenne/étanche) et utilise un exemple simple et cohérent pour les illustrer.

Regardez la vidéo du début jusqu'à 14:51. Concentrez-vous sur : La signification intuitive de chaque notation (upper bound, lower bound, average bound). La manière dont les définitions formelles traduisent ces intuitions. L'application à l'exemple f(n) = 2n + 3.

2. Définitions Formelles

Maintenant que vous avez l'intuition, passons aux définitions formelles, qui sont le cœur de ce que vous devez maîtriser. Soit $f (n)$ la fonction qui décrit la complexité de notre algorithme et $g (n)$ une fonction de référence plus simple (par ex. $n$ , $n^{2}$ , $lo g n$ ).

Asymptotic Notations: Big O, Theta, Omega Graphical Definitions — Cette image illustre les définitions formelles des notations asymptotiques. Pour Θ, f(n) est "prise en sandwich" entre c₁g(n) et c₂g(n). Pour O, f(n) est en dessous de cg(n). Pour Ω, f(n) est au-dessus de cg(n). Tout cela est valable pour n suffisamment grand (n ≥ n₀).

Notation O (Grand O)

On dit que $f (n)$ est en "Grand O" de $g (n)$ , noté $f (n) \in O (g (n))$ ou $f (n) = O (g (n))$ , si la croissance de $f$ est bornée supérieurement par celle de $g$ , à un facteur constant près.

Définition formelle :
$f (n) \in O (g (n))$ s'il existe une constante réelle $c > 0$ et un entier $n_{0} \geq 1$ tels que pour tout entier $n \geq n_{0}$ , on a :

0 \leq f (n) \leq c \cdot g (n)

Notation Ω (Grand Oméga)

On dit que $f (n)$ est en "Grand Oméga" de $g (n)$ , noté $f (n) \in Ω (g (n))$ , si la croissance de $f$ est bornée inférieurement par celle de $g$ , à un facteur constant près.

Définition formelle :
$f (n) \in Ω (g (n))$ s'il existe une constante réelle $c > 0$ et un entier $n_{0} \geq 1$ tels que pour tout entier $n \geq n_{0}$ , on a :

0 \leq c \cdot g (n) \leq f (n)

Notation Θ (Grand Thêta)

On dit que $f (n)$ est en "Grand Thêta" de $g (n)$ , noté $f (n) \in Θ (g (n))$ , si la croissance de $f$ est du même ordre que celle de $g$ .

Définition formelle :
$f (n) \in Θ (g (n))$ s'il existe des constantes réelles $c_{1} > 0$ , $c_{2} > 0$ et un entier $n_{0} \geq 1$ tels que pour tout entier $n \geq n_{0}$ , on a :

0 \leq c_{1} \cdot g (n) \leq f (n) \leq c_{2} \cdot g (n)

Une propriété fondamentale relie ces trois notations :

f (n) \in Θ (g (n)) ⟺ (f (n) \in O (g (n)) et f (n) \in Ω (g (n)))

Pour consolider ces définitions, je vous propose une lecture qui les formalise en français et aborde l'abus de notation courant qui consiste à écrire = au lieu de ∈.

Algorithmique IV - Notations asymptotiques

Ce document de cours de J.P. Zanotti présente les notations de manière rigoureuse et concise. Il est parfait pour fixer les définitions formelles.

Lisez les sections 'Généralités' et la définition de Θ(g) qui suit. Portez une attention particulière à la formalisation avec les quantificateurs (∃, ∀). Lisez également le court paragraphe sur le moyen mnémotechnique (O ≈ ≤, Ω ≈ ≥, Θ ≈ ≃).

3. La Méthodologie de la Preuve Formelle

Connaître les définitions est une chose, savoir les appliquer pour prouver qu'une fonction appartient à une classe de complexité en est une autre. Le jury de l'Agrégation attend de vous une parfaite maîtrise de cet exercice. L'objectif est de trouver des "témoins" (les constantes $c, c_{1}, c_{2}$ et le seuil $n_{0}$ ) qui satisfont la définition.

La vidéo suivante est un excellent tutoriel sur la manière de construire ces preuves pas à pas.

How to Prove or Disprove Big-O - Introduction to Computer Science

Cette vidéo de Quoc Dat Phung, bien qu'en anglais, est une démonstration pédagogique de la méthode pour prouver ou réfuter une appartenance à O. Elle montre comment choisir les constantes de manière systématique.

Regardez la première partie de la vidéo (00:00 - 02:38). Concentrez-vous sur la technique algébrique pour trouver les constantes c et n₀ pour prouver que 2n + 3 est O(n). La méthode consiste à majorer chaque terme par un multiple du terme dominant.

Exemple de preuve : Montrons que $f (n) = 4 n^{2} + 10 n + 5 \in Θ (n^{2})$ .

Pour cela, nous devons prouver que $f (n) \in O (n^{2})$ ET $f (n) \in Ω (n^{2})$ .

Preuve pour O(n²) (borne supérieure)
Nous cherchons $c_{2}$ et $n_{0}$ tels que $4 n^{2} + 10 n + 5 \leq c_{2} n^{2}$ pour $n \geq n_{0}$ .
L'astuce est de majorer les termes de plus bas degré par le terme de plus haut degré.
Pour $n \geq 1$ , on a $10 n \leq 10 n^{2}$ et $5 \leq 5 n^{2}$ .
Donc, pour $n \geq 1$ :
$4 n^{2} + 10 n + 5 \leq 4 n^{2} + 10 n^{2} + 5 n^{2} = 19 n^{2}$
Nous pouvons choisir $c_{2} = 19$ et $n_{0} = 1$ . La définition de O est satisfaite.
Preuve pour Ω(n²) (borne inférieure)
Nous cherchons $c_{1}$ et $n_{0}$ tels que $c_{1} n^{2} \leq 4 n^{2} + 10 n + 5$ pour $n \geq n_{0}$ .
Ici, il suffit d'ignorer les termes de plus bas degré qui sont positifs.
Pour tout $n \geq 1$ , on a $10 n > 0$ et $5 > 0$ .
Donc :
$4 n^{2} \leq 4 n^{2} + 10 n + 5$
Nous pouvons choisir $c_{1} = 4$ et $n_{0} = 1$ . La définition de Ω est satisfaite.

Conclusion :
Puisque $f (n) \in O (n^{2})$ et $f (n) \in Ω (n^{2})$ , nous pouvons conclure que $f (n) \in Θ (n^{2})$ . Nous avons trouvé les témoins $c_{1} = 4$ , $c_{2} = 19$ et $n_{0} = 1$ .

4. Distinctions et Classes de Complexité Courantes

Il est crucial de bien distinguer les notations :

$f (n) = 2 n \in O (n^{3})$ est vrai, mais c'est une borne lâche et peu informative.
$f (n) = 2 n \in Θ (n^{3})$ est faux, car $2 n$ ne croît pas aussi vite que $n^{3}$ .
$f (n) = 2 n \in Θ (n)$ est vrai et c'est la classification la plus précise.

En pratique, on cherche toujours la borne $Θ$ (la plus "étanche" possible). Si cela n'est pas possible ou si l'on s'intéresse uniquement au pire cas, on se contentera d'une borne $O$ .

Les fonctions $g (n)$ que nous utilisons pour la classification ne sont pas arbitraires. Elles appartiennent à un ensemble bien connu de classes de complexité.

Tableau des Types de Complexité en Notation Big O — Ce tableau présente les classes de complexité les plus courantes, de la plus efficace (O(1), constant) à la moins efficace (O(n!), factoriel). Mémoriser cet ordre de croissance est fondamental.

Exercice

À votre tour. Soit la fonction $f (n) = 7 n^{2} + 25 n + 12$ .

Prouvez formellement que $f (n) \in O (n^{2})$ en trouvant des constantes $c$ et $n_{0}$ valides.
Prouvez formellement que $f (n) \in Ω (n^{2})$ en trouvant des constantes $c$ et $n_{0}$ valides.
Sur la base de vos réponses, que pouvez-vous conclure concernant l'appartenance de $f (n)$ à $Θ (n^{2})$ ?

Conclusion

Cette leçon vous a équipé des outils formels pour raisonner sur l'efficacité des algorithmes. C'est un changement de perspective fondamental : nous ne comptons plus simplement les opérations, nous classifions la croissance de ce nombre d'opérations.

Points clés à retenir :

Les notations asymptotiques décrivent le comportement d'une fonction pour de grandes valeurs de $n$ .
O est une borne supérieure (croissance au plus aussi rapide que).
Ω est une borne inférieure (croissance au moins aussi rapide que).
Θ est une borne étanche (croissance de même ordre).
Prouver l'appartenance à une classe de complexité revient à un exercice formel de recherche de constantes $c, c_{1}, c_{2}$ et d'un seuil $n_{0}$ qui satisfont la définition.

Dans la prochaine leçon, nous mettrons ces nouvelles connaissances en pratique. Nous passerons de l'analyse de fonctions mathématiques pures à l'analyse d'algorithmes concrets. Vous apprendrez à calculer la complexité temporelle dans le pire des cas et la complexité spatiale d'un algorithme itératif, en appliquant systématiquement les notations O, Ω et Θ.

Recommended resources