Big O Notation est une notation mathématique utilisée pour décrire la complexité d'un algorithme ou d'une fonction calculable. En informatique, il est utilisé pour mesurer l'efficacité d'un algorithme, c'est-à-dire le temps et/ou l'espace utilisé par sa mise en œuvre.
La notation Big O est un outil permettant de mesurer la complexité des algorithmes, calculant souvent le pire ou le meilleur des scénarios, c'est pourquoi elle est parfois appelée « Big Os » (ou Big Order). La notation Big O, cependant, ne mesure pas avec précision une mesure de complexité particulière, mais constitue plutôt un outil permettant d'approcher la complexité.
La notation Big O donne une mesure de complexité temporelle dans le pire des cas et fournit une indication générale de la façon dont l'algorithme peut fonctionner en termes de temps et d'espace. En utilisant la notation Big O, on peut déterminer la complexité temporelle d'un algorithme donné, ce qui donne une indication sur la façon dont l'algorithme s'exécute à mesure que la taille d'entrée augmente.
La notation Big O est exprimée par O(f(n)), où f(n) est la complexité temporelle d'un algorithme. Les complexités temporelles courantes exprimées avec la notation Big O incluent O(1) pour une complexité temporelle constante, O(log n) pour une complexité temporelle logarithmique, O(n) pour une complexité temporelle linéaire, O(n2) pour une complexité temporelle quadratique et O. (2n) pour une complexité temporelle exponentielle.
La notation Big O peut être utilisée pour comparer différents algorithmes, permettant ainsi d'identifier l'algorithme le plus efficace pour un problème donné. En utilisant la notation Big O, on peut déterminer les algorithmes les mieux adaptés pour résoudre certains problèmes tout en tenant compte des ressources et du temps.
