Notation Big O
La notation Big O est une notation mathématique qui décrit le comportement limitant d'une fonction lorsque l’argument tend vers une valeur ou un infini particuliers. Elle fait partie d'une famille de notations inventées par Paul Bachmann, Edmu et Landau notamment, appelées collectivement notation de Bachmann-Landau ou notation asymptotique.
En informatique, la notation Big O est utilisée pour classer les algorithmes en fonction de la croissance de leur durée de fonctionnement ou de leurs besoins en espace au fur et à mesure que la taille de l’entrée augmente. Dans la théorie analytique des nombres, la grande notation O est souvent utilisée pour exprimer une borne sur la différence entre une fonction arithmétique et une approximation mieux comprise; Un exemple célèbre d'une telle différence est le terme restant dans le théorème des nombres premiers.
La notation Big O caractérise les fonctions en fonction de leur taux de croissance: différentes fonctions ayant le même taux de croissance peuvent être représentées à l'aide de la même notation.
La lettre O est utilisée car le taux de croissance d’une fonction est également appelé l’ordre de la fonction. La description d’une fonction en fonction de la notation big O ne fournit généralement qu’une limite supérieure du taux de croissance de la fonction. Plusieurs notations associées, associées aux symboles o, Ω, ω et Θ, sont associées à la notation big O pour décrire d'autres types de bornes sur les taux de croissance asymptotiques.
La notation Big O est également utilisée dans de nombreux autres domaines pour fournir des estimations similaires.
