Notations asymptotiques
Lorsqu'on analyse un algorithme, on cherche à connaître son comportement pour des entrées de grande taille.
Au lieu de mesurer le temps exact d'exécution (qui dépend des machines), on utilise des notations asymptotiques qui permettent de donner une estimation générale de la croissance de la fonction de complexité.
Ces notations donnent une idée de l'ordre de grandeur de la complexité : elles ignorent les constantes et les termes de moindre importance.
Exemple introductif
\[ f(n) = 5n^2 + 3n + 10 \quad \text{se note en } O(n^2) \]
Notation Grand \(O\)
On dit que \(f(n) = O(g(n))\) quand il existe une constante \(c > 0\) et un entier \(n_0 > 0\) tels que : \[ f(n) \le c \cdot g(n) \quad \text{pour tout } n \ge n_0 \]
La notation \(O\) exprime la vitesse maximale de croissance d'un algorithme : elle indique que le temps d'exécution ne dépassera jamais une certaine fonction (à un facteur constant près).
Exemple 1
Soit \(f(n) = 3n^2 + 2n + 1\) et \(g(n) = n^2\).
Pour \(n \ge 1\) :
\[ f(n) = 3n^2 + 2n + 1 \le 3n^2 + 2n^2 + n^2 = 6n^2 \]
On peut choisir \(c = 6\) et \(n_0 = 1\).
Donc \(f(n) = O(n^2)\).
Exemple 2
Soit \(f(n) = 7n\log n + 20n\) et \(g(n) = n \log n\).
Pour \(n \ge 2\), \(\log n \ge 1\), donc :
\[ f(n) = 7n\log n + 20n \le 7n\log n + 20n\log n = 27 n \log n \]
On peut choisir \(c = 27\) et \(n_0 = 2\).
Donc \(f(n) = O(n \log n)\).
Notation Grand \(\Omega\)
On dit que \(f(n) = \Omega(g(n))\) quand il existe une constante \(c > 0\) et un entier \(n_0 > 0\) tels que : \[ f(n) \ge c \cdot g(n) \quad \text{pour tout } n \ge n_0 \]
La notation \(\Omega\) fixe une limite minimale : elle garantit qu'un algorithme prendra au moins autant de temps qu'une certaine fonction (à un facteur constant près).
Exemple 1
Soit \(f(n) = 3n^2 + 2n + 1\) et \(g(n) = n^2\).
Pour \(n \ge 1\) :
\[ f(n) = 3n^2 + 2n + 1 \ge 3n^2 \]
On peut choisir \(c = 3\) et \(n_0 = 1\).
Donc \(f(n) = \Omega(n^2)\).
Exemple 2
Soit \(f(n) = n\log n + n\) et \(g(n) = n \log n\).
Pour \(n \ge 2\), on a \(\log n \ge 1\), donc :
\[ f(n) = n\log n + n \ge n\log n \]
On peut choisir \(c = 1\) et \(n_0 = 2\).
Donc \(f(n) = \Omega(n \log n)\).
Notation Grand \(\Theta\)
On dit que \(f(n) = \Theta(g(n))\) quand il existe des constantes \(c_1 > 0\), \(c_2 > 0\) et un entier \(n_0 > 0\) tels que : \[ c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) \quad \text{pour tout } n \ge n_0 \]
La notation \(\Theta\) encadre la croissance d'un algorithme : elle affirme que l'algorithme croît au même rythme qu'une certaine fonction, ni plus vite ni moins vite (à des facteurs constants près).
Exemple 1
Soit \(f(n) = 3n^2 + 2n + 1\) et \(g(n) = n^2\).
Pour \(n \ge 1\) :
\[ 3n^2 \le f(n) \le 6n^2 \]
On peut choisir \(c_1 = 3\), \(c_2 = 6\) et \(n_0 = 1\).
Donc \(f(n) = \Theta(n^2)\).
Exemple 2
Soit \(f(n) = 4n\log n + 7n\) et \(g(n) = n \log n\).
Pour \(n \ge 2\) :
\[ 4n \log n \le f(n) \le 4n\log n + 7n\log n = 11n \log n \]
On peut choisir \(c_1 = 4\), \(c_2 = 11\) et \(n_0 = 2\).
Donc \(f(n) = \Theta(n \log n)\).
Exemple 3
Soit \(f(n) = 2n^3 + 5n^2\) et \(g(n) = n^3\).
Pour \(n \ge 1\) :
\[ 2n^3 \le f(n) \le 2n^3 + 5n^3 = 7n^3 \]
On peut choisir \(c_1 = 2\), \(c_2 = 7\) et \(n_0 = 1\).
Donc \(f(n) = \Theta(n^3)\).
Tableau récapitulatif
| Notation | Signification | Inégalité | Interprétation |
|---|---|---|---|
| \(O(g(n))\) | Grand O | \(f(n) \le c \cdot g(n)\) | Borne supérieure (au plus) |
| \(\Omega(g(n))\) | Grand Omega | \(f(n) \ge c \cdot g(n)\) | Borne inférieure (au moins) |
| \(\Theta(g(n))\) | Grand Theta | \(c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)\) | Encadrement (ordre exact) |
Exemples supplémentaires
Exemple : Comparaison de croissances
Considérons les fonctions suivantes :
- \(f_1(n) = 100n + 5\)
- \(f_2(n) = n^2 - 10n\)
- \(f_3(n) = 2^n + n^{10}\)
- \(f_4(n) = 5n\log n + 3n\)
| Fonction | \(O\) | \(\Omega\) | \(\Theta\) |
|---|---|---|---|
| \(f_1(n) = 100n + 5\) | \(O(n)\) | \(\Omega(n)\) | \(\Theta(n)\) |
| \(f_2(n) = n^2 - 10n\) | \(O(n^2)\) | \(\Omega(n^2)\) | \(\Theta(n^2)\) |
| \(f_3(n) = 2^n + n^{10}\) | \(O(2^n)\) | \(\Omega(2^n)\) | \(\Theta(2^n)\) |
| \(f_4(n) = 5n\log n + 3n\) | \(O(n\log n)\) | \(\Omega(n\log n)\) | \(\Theta(n\log n)\) |
Hiérarchie des croissances courantes
Ordre de croissance des fonctions les plus courantes (du plus lent au plus rapide) :
\[ O(1) \subset O(\log n) \subset O(n) \subset O(n\log n) \subset O(n^2) \subset O(n^3) \subset O(2^n) \subset O(n!) \]
- \(O(1)\) : temps constant
- \(O(\log n)\) : temps logarithmique (recherche dichotomique)
- \(O(n)\) : temps linéaire (recherche simple)
- \(O(n\log n)\) : temps quasi-linéaire (tri fusion, tri rapide)
- \(O(n^2)\) : temps quadratique (tri à bulles)
- \(O(2^n)\) : temps exponentiel (problèmes NP-difficiles)
- Les notations asymptotiques ignorent les constantes multiplicatives et les termes de plus faible ordre.
- \(O\) est la notation la plus utilisée car elle donne une garantie sur le comportement dans le pire cas.
- Pour prouver qu'un algorithme est optimal, on utilise \(\Omega\) pour montrer qu'aucun algorithme ne peut faire mieux.
- \(\Theta\) est la notation la plus précise : elle indique que l'algorithme a exactement cet ordre de croissance.
- Une même fonction peut avoir plusieurs notations selon le contexte :
- \(f(n) = n^2\) est à la fois \(O(n^2)\), \(O(n^3)\), \(\Omega(n)\), etc.
- Mais la notation \(\Theta\) est plus restrictive : \(n^2 = \Theta(n^2)\) mais \(n^2 \neq \Theta(n^3)\).
Les notations asymptotiques sont essentielles pour comparer l'efficacité des algorithmes indépendamment des détails d'implémentation.
- Grand O (\(O\)) : borne supérieure (pire cas) - l'algorithme ne sera pas plus mauvais que ça.
- Grand Omega (\(\Omega\)) : borne inférieure (meilleur cas) - l'algorithme ne sera pas meilleur que ça.
- Grand Theta (\(\Theta\)) : ordre exact - l'algorithme croît exactement comme cette fonction.
Ces notations permettent de classifier les algorithmes selon leur ordre de croissance et de choisir le plus adapté en fonction des contraintes.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.