Notation asymptotique
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\).
Définition : 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\).
Définition : La notation Ω (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\).
Définition : La notation Θ (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\).
Exemple : 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.
Exemple : 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)\).
Exemple : 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)\).
Remarque : Pourquoi ne pas utiliser Θ ?
Il n’est pas toujours possible de donner une borne exacte sur la complexité d’un algorithme. Dans certains cas, nous ne pouvons donner qu’une borne supérieure (en utilisant la notation \(O\)) ou une borne inférieure (en utilisant la notation \(\Omega\)). Dans ces cas, nous ne pouvons pas utiliser la notation \(\Theta\).
De plus, dans de nombreux cas, nous sommes principalement intéressés par la borne supérieure sur la complexité d’un algorithme, car cela nous donne une idée de la performance de l’algorithme dans le pire des cas. C’est pourquoi la notation \(O\) est souvent utilisée pour décrire la complexité des algorithmes.
Exemple : Et dans quels cas utiliser Ω ?
Prenons l’exemple de l’algorithme de tri par fusion (merge sort). C’est un algorithme de tri qui utilise la stratégie “diviser pour régner” pour trier un tableau.
def tri_fusion(tableau):
if len(tableau) <= 1:
return tableau
milieu = len(tableau) // 2
gauche = tri_fusion(tableau[:milieu])
droite = tri_fusion(tableau[milieu:])
return fusion(gauche, droite)
def fusion(gauche, droite):
resultat = []
index_gauche = index_droite = 0
while index_gauche < len(gauche) and index_droite < len(droite):
if gauche[index_gauche] <= droite[index_droite]:
resultat.append(gauche[index_gauche])
index_gauche += 1
else:resultat.append(droite[index_droite])
index_droite += 1
if gauche:
resultat.extend(gauche[index_gauche:])
if droite:
resultat.extend(droite[index_droite:])
return resultat
Dans cet algorithme, nous divisons le tableau en deux moitiés, nous trions chaque moitié séparément, puis nous fusionnons les deux moitiés triées. Le nombre d’opérations effectuées par cet algorithme est proportionnel à \(n\log_2n\), où n est la taille du tableau. Par conséquent, nous disons que la complexité temporelle de cet algorithme est de \(O(n\log_2n)\).
Cependant, même dans le meilleur des cas (lorsque le tableau est déjà trié), l’algorithme doit toujours diviser le tableau en deux moitiés et les fusionner, ce qui nécessite un nombre d’opérations proportionnel à \(n\log_2n\). Par conséquent, nous disons que la complexité temporelle dans le meilleur des cas de cet algorithme est de \(\Omega(n\log_2n)\).
Complément : Explications sur log
En mathématiques, le logarithme est la fonction inverse de l’exponentiation. Cela signifie que le logarithme d’un nombre \(x\) à la base \(b\) est l’exposant auquel \(b\) doit être élevé pour produire \(x\). Par exemple, puisque \(1000 = 10^3\), le logarithme de base \(10\) de \(1000\) est \(3\), ou \(\log_{10}(1000) = 3\). Le logarithme de \(x\) à la base \(b\) est noté \(\log_b(x)\), ou sans parenthèses, \(\log_b x\), ou même sans la base explicite, \(\log x\), lorsqu'il n’y a pas de confusion possible ou lorsque la base n’a pas d’importance.
Le nombre d’opérations effectuées par l’algorithme de tri par fusion est proportionnel à \(n\log_2n\) en raison de la façon dont l’algorithme fonctionne. L’algorithme utilise une stratégie “diviser pour régner” pour trier le tableau. Il divise récursivement le tableau en deux moitiés, trie chaque moitié séparément, puis fusionne les deux moitiés triées.
La division du tableau en deux moitiés peut être répétée \(\log_2n\) fois jusqu'à ce que nous obtenions des sous-tableaux de taille 1. À chaque niveau de récursion, nous effectuons un total de \(n\) opérations pour fusionner les sous-tableaux. Comme il y a \(\log_2n\) niveaux de récursion, le nombre total d’opérations effectuées par l’algorithme est proportionnel à \(n\log_2n\).