Notation Grand O

O-notation, également connue sous le nom de notation Big O, est une notation mathématique utilisée en informatique pour décrire le comportement asymptotique des algorithmes. Elle représente la borne supérieure ou le pire scénario de la complexité temporelle d'un algorithme par rapport à la taille de l'entrée. En termes plus simples, la notation O exprime comment le temps d'exécution ou les exigences d'espace d'un algorithme augmentent par rapport à la taille de son entrée.

Remarque

Le comportement asymptotique des algorithmes se réfère à la façon dont leurs performances changent à mesure que la taille de leur entrée approche l'infini. En d'autres termes, il décrit le comportement de l'algorithme à mesure que la taille de l'entrée devient très grande.

Fonctions couramment utilisées dans la notation O

1. O(1): Temps constant. Le temps d'exécution de l'algorithme reste constant quelle que soit la taille de l'entrée. Exemple : Accéder à un élément dans un tableau par index;

2. O(log n): Temps logarithmique. Le temps d'exécution augmente logarithmiquement avec la taille de l'entrée. Exemple : Recherche binaire dans un tableau trié;

3. O(n): Temps linéaire. Le temps d'exécution augmente linéairement avec la taille de l'entrée. Exemple : Itération à travers tous les éléments d'un tableau;

4. O(n log n): Temps log-linéaire. Le temps d'exécution augmente proportionnellement à n multiplié par le logarithme de n. Exemple : Algorithmes de tri comme le tri par fusion et le tri rapide;

5. O(n^2): Temps quadratique. Le temps d'exécution augmente quadratiquement avec la taille de l'entrée. Exemple : Boucles imbriquées itérant à travers toutes les paires d'éléments dans un tableau;

6. O(2^n): Temps exponentiel. Le temps d'exécution augmente exponentiellement avec la taille de l'entrée. Exemple : Génération de tous les sous-ensembles d'un ensemble;

7. O(n!): Temps factoriel. Le temps d'exécution augmente de manière factorielle avec la taille de l'entrée. Exemple : Génération de toutes les permutations d'une séquence.