Notation asymptotique
Notations
La notation asymptotique est un outil utilisé en informatique pour décrire la complexité des algorithmes. Elle permet de donner une estimation de la performance d’un algorithme en fonction de la taille de ses données d’entrée, sans se préoccuper des détails de mise en œuvre ou des constantes de proportionnalité.
Il existe trois notations asymptotiques principales : \(O\), \(\Omega\) et \(\Theta\).
La notation \(O\) (grand O)
Elle donne une borne supérieure sur la complexité d’un algorithme. Si nous disons que la complexité d’un algorithme est \(O(f(n))\), cela signifie que le nombre d’opérations effectuées par l’algorithme est au plus proportionnel à \(f(n)\) pour des valeurs suffisamment grandes de \(n\).
La notation \(\Omega\) (grand Oméga)
Elle donne une borne inférieure sur la complexité d’un algorithme. Si nous disons que la complexité d’un algorithme est \(\Omega(g(n))\), cela signifie que le nombre d’opérations effectuées par l’algorithme est au moins proportionnel à \(g(n)\) pour des valeurs suffisamment grandes de \(n\).
La notation \(\Theta\) (Theta)
Elle donne une borne exacte sur la complexité d’un algorithme. Si nous disons que la complexité d’un algorithme est \(\Theta(h(n))\), cela signifie que le nombre d’opérations effectuées par l’algorithme est proportionnel à \(h(n)\) pour des valeurs suffisamment grandes de \(n\).
Exemples
Recherche linéaire
L’algorithme de recherche linéaire parcourt un tableau pour trouver un élément spécifique. Le nombre d’opérations effectuées par cet algorithme est proportionnel à la taille du tableau. Par conséquent, nous disons que la complexité temporelle de cet algorithme est de \(O(n)\), où \(n\) est la taille du tableau.
Tri par insertion
Le tri par insertion est un algorithme de tri qui parcourt un tableau et insère chaque élément à sa place dans le tableau trié. Le nombre d’opérations effectuées par cet algorithme est proportionnel à \(n^2\), où \(n\) est la taille du tableau. Par conséquent, nous disons que la complexité temporelle de cet algorithme est de \(O(n^2)\).
Recherche binaire
La recherche binaire est un algorithme de recherche qui utilise la stratégie diviser pour régner pour trouver un élément dans un tableau trié. Le nombre d’opérations effectuées par cet algorithme est proportionnel à \(\log_2n\), où \(n\) est la taille du tableau. Par conséquent, nous disons que la complexité temporelle de cet algorithme est de \(O(\log_2n)\).