Big O Notation

La notation grand O décrit la borne supérieure asymptotique d'une fonction, utilisée pour analyser la complexité temporelle/spatiale des algorithmes en ignorant les constantes et les termes d'ordre inférieur.

Objectif

Abstraire le taux de croissance asymptotique de l'efficacité d'un algorithme afin de comparer et de choisir des algorithmes.

Mécanisme

f(n)=O(g(n)) signifie qu'il existe des constantes C et n0 telles que |f(n)|≤C|g(n)| pour tout n>n0. Ordres courants : O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!). L'accent est mis sur les bornes supérieures du pire cas.

Cas d’usage

Analyse de complexité des algorithmes
Choix de structures de données
Décisions d'optimisation des performances
Entretiens et enseignement

Exemples

entrée
```
Binary search
```
Output
```
O(log n)
```
Halves each time

Erreurs courantes

Ignoring constant factors misjudges real-world performance: Big O is asymptotic; benchmark for real behavior

Termes associés

Sorting Algorithm

Les algorithmes de tri arrangent les éléments en ordre — tri rapide, tri fusion et tri par tas sont courants — avec des complexités allant de O(n log n) à O(n²).

La recherche dichotomique compare avec l'élément central d'un tableau trié et divise l'intervalle par deux à chaque étape, localisant une cible en O(log n) ; c'est l'algorithme de recherche efficace fondateur.

Une table de hachage associe des clés à un tableau de compartiments via une fonction de hachage, offrant recherche/insertion/suppression en O(1) en moyenne ; c'est l'une des structures de données les plus utilisées.

References