Dans ce didacticiel, vous apprendrez ce que sont les notations asymptotiques. En outre, vous apprendrez la notation Big-O, la notation Thêta et la notation Omega.
L'efficacité d'un algorithme dépend de la quantité de temps, de stockage et d'autres ressources nécessaires pour exécuter l'algorithme. L'efficacité est mesurée à l'aide de notations asymptotiques.
Un algorithme peut ne pas avoir les mêmes performances pour différents types d'entrées. Avec l'augmentation de la taille d'entrée, les performances changeront.
L'étude du changement de performance de l'algorithme avec le changement de l'ordre de la taille d'entrée est définie comme une analyse asymptotique.
Notations asymptotiques
Les notations asymptotiques sont les notations mathématiques utilisées pour décrire le temps d'exécution d'un algorithme lorsque l'entrée tend vers une valeur particulière ou une valeur limite.
Par exemple: en tri à bulles, lorsque le tableau d'entrée est déjà trié, le temps pris par l'algorithme est linéaire c'est-à-dire le meilleur des cas.
Mais, lorsque le tableau d'entrée est en condition inverse, l'algorithme prend le temps maximum (quadratique) pour trier les éléments c'est-à-dire le pire des cas.
Lorsque le tableau d'entrée n'est ni trié ni dans l'ordre inverse, cela prend un temps moyen. Ces durées sont désignées par des notations asymptotiques.
Il existe principalement trois notations asymptotiques:
- Notation Big-O
- Notation Omega
- Notation thêta
Notation Big-O (notation O)
La notation Big-O représente la limite supérieure du temps d'exécution d'un algorithme. Ainsi, il donne la complexité du pire des cas d'un algorithme.
Big-O donne la borne supérieure d'une fonction
O (g (n)) = (f (n): il existe des constantes positives c et n 0 telles que 0 ≦ f (n) ≦ cg (n) pour tout n ≧ n 0 )
L'expression ci-dessus peut être décrite comme une fonction f(n)appartenant à l'ensemble O(g(n))s'il existe une constante positive ctelle qu'elle se situe entre 0et cg(n), pour suffisamment grand n.
Pour toute valeur de n, le temps d'exécution d'un algorithme ne dépasse pas le temps fourni par O(g(n)).
Puisqu'il donne le temps d'exécution dans le pire des cas d'un algorithme, il est largement utilisé pour analyser un algorithme car nous sommes toujours intéressés par le pire des cas.
Notation Omega (notation Ω)
La notation Omega représente la limite inférieure du temps d'exécution d'un algorithme. Ainsi, il fournit la meilleure complexité de cas d'un algorithme.
Omega donne la borne inférieure d'une fonction
Ω (g (n)) = (f (n): il existe des constantes positives c et n 0 telles que 0 ≦ cg (n) ≦ f (n) pour tout n ≧ n 0 )
L'expression ci-dessus peut être décrite comme une fonction f(n)appartenant à l'ensemble Ω(g(n))s'il existe une constante positive ctelle qu'elle se trouve au cg(n)- dessus , pour suffisamment grande n.
Pour toute valeur de n, le temps minimum requis par l'algorithme est donné par Omega Ω(g(n)).
Notation thêta (notation Θ)
La notation thêta englobe la fonction d'en haut et d'en bas. Puisqu'il représente la limite supérieure et inférieure du temps d'exécution d'un algorithme, il est utilisé pour analyser la complexité de cas moyen d'un algorithme.
Thêta limite la fonction dans les facteurs constants
Pour une fonction g(n), Θ(g(n))est donnée par la relation:
Θ (g (n)) = (f (n): il existe des constantes positives c 1 , c 2 et n 0 telles que 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) pour tout n ≧ n 0 )
L'expression ci-dessus peut être décrite comme une fonction f(n)appartenant à l'ensemble Θ(g(n))s'il existe des constantes positives et telle qu'elle peut être prise en sandwich entre et , pour un n suffisamment grand.c1c2c1g(n)c2g(n)
Si une fonction f(n)se situe n'importe où entre et pour tous , on dit qu'elle est asymptotiquement liée.c1g(n)c2g(n)n ≧ n0f(n)
