5. Introduction à la notation Big O (Le langage de l'efficacité)

La notation Big O (souvent écrite O()) est le langage mathématique que nous utilisons pour décrire la borne supérieure ou le scénario du pire cas de la performance d'un algorithme.

Elle se concentre sur la façon dont le temps d'exécution ou l'exigence d'espace augmente à mesure que la taille de l'entrée (N) augmente.

Ce que la notation Big O ignore

La notation Big O simplifie l'analyse en ignorant :

1. Les Constantes : O(2N) est simplifié en O(N). Si un algorithme prend deux fois plus de temps, cela ne change pas son modèle de croissance fondamental.
2. Les Termes d'Ordre Inférieur : Dans O(N^2 + N), nous nous concentrons sur le terme dominant (N^2), donc la complexité est O(N^2). Lorsque N devient très grand, N^2 submerge complètement N.

L'Analogie

Imaginez conduire une voiture : la notation Big O ne se soucie pas de la vitesse initiale ou des petites bosses ; elle décrit comment le temps de trajet change si la distance (N) triple.