La complexité algorithmique (Big-O) avec des exemples concrets

O(1), O(n), O(log n), O(n²) : ce que ça veut dire vraiment, et comment le reconnaître dans ton code.

La notation Big-O décrit comment le temps (ou la mémoire) d’un algorithme évolue quand la taille des données grandit. C’est un incontournable des certifications et des entretiens.

Lire le Big-O

O(1) — constant : le temps ne dépend pas de la taille. Ex. accéder à tab[i].
O(log n) — logarithmique : on divise le problème à chaque étape. Ex. recherche dichotomique.
O(n) — linéaire : on parcourt une fois. Ex. trouver un max.
O(n log n) — les bons tris (merge sort, quicksort moyen).
O(n²) — quadratique : deux boucles imbriquées. Ex. comparer toutes les paires.

Le même problème, deux complexités

Chercher un doublon dans une liste. Version naïve, O(n²) :

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (a[i] == a[j]) return true;

Version avec un ensemble de hachage, O(n) :

Set<Integer> vus = new HashSet<>();
for (int x : a) {
    if (!vus.add(x)) return true; // déjà vu
}

On échange du temps contre de la mémoire (O(n) d’espace) — un compromis classique.

L’intuition à garder

Une boucle = O(n). Une boucle dans une boucle = O(n²). Diviser par deux à chaque tour = O(log n). En certif, sache justifier ta complexité, pas seulement la citer. Et rappelle-toi : pour de petites données, le plus simple gagne souvent ; le Big-O compte quand n grandit.