Complexité algorithmique : la notation grand O

Deux programmes donnent le même résultat : l'un répond en une seconde, l'autre tourne encore une heure plus tard. La différence n'est presque jamais la machine, c'est l'algorithme. La complexité algorithmique est l'outil qui permet de prédire ce genre d'écart avant même d'exécuter le code, en comptant comment le travail à faire grandit avec la taille des données.

Cet article te donne tout ce qu'il faut pour être solide en informatique de prépa (tronc commun et option info) : pourquoi et comment on mesure le coût d'un programme, le comptage des opérations élémentaires, la notation de Landau grand $O$ avec son intuition, les classes usuelles de $O(1)$ à $O(2^n)$ dans un tableau comparatif, la distinction meilleur / pire / moyen cas, l'analyse des boucles imbriquées, une mention de la complexité amortie, et une méthode pas à pas pour analyser un code, avec 3 exercices corrigés. Nos profs Hadamard, anciens de MP2I et de MPSI option info passés par l'X, l'ENS et CentraleSupélec, voient revenir les mêmes maladresses sur les copies, on les liste pour que tu les évites.

Pourquoi mesurer la complexité

On pourrait croire qu'il suffit de chronométrer un programme. Mauvaise idée : le temps en secondes dépend de la machine, du langage, de la charge du processeur, de la taille exacte du jeu de test. Un même code paraîtra rapide sur ton ordinateur et lent sur une vieille calculatrice, sans que l'algorithme ait changé. Ce qu'on veut, c'est une mesure intrinsèque à l'algorithme.

L'idée est de compter le nombre d'opérations élémentaires exécutées, en fonction de la taille des données, notée $n$ (le nombre d'éléments d'un tableau, la longueur d'une chaîne, la valeur d'un entier à traiter). On ne cherche pas le nombre exact, mais la façon dont il grandit quand $n$ augmente. C'est ce comportement, dit asymptotique, qui décide si un programme passe à l'échelle ou s'effondre sur de grosses entrées.

Compter les opérations élémentaires

Une opération élémentaire est une action au coût supposé constant, indépendant de $n$ : une affectation, une comparaison, une addition, un accès à une case de tableau tab[i]. On lui attribue un coût $O(1)$. Analyser un algorithme, c'est additionner ces coûts en suivant le déroulement du code.

Prenons la somme des éléments d'un tableau de taille $n$ :

def somme(tab):
    total = 0            # 1 operation
    for x in tab:        # la boucle tourne n fois
        total += x       # 1 operation par tour
    return total         # 1 operation

L'initialisation et le return coûtent $O(1)$ chacun. La boucle exécute $n$ fois une opération à $O(1)$, soit un coût $n$. Le total est $1 + n + 1 = n + 2$ opérations. Quand $n$ devient grand, le $+2$ ne pèse plus rien face au $n$ : on retient que cet algorithme est linéaire, en $O(n)$.

C'est le premier réflexe : on ne garde ni les constantes additives, ni les facteurs multiplicatifs. Un algorithme en $3n + 5$ et un algorithme en $n$ sont tous les deux en $O(n)$, car ils grandissent à la même vitesse. Ce qui compte, c'est l'ordre de grandeur.

La notation de Landau, grand O

La notation grand $O$ (notation de Landau) formalise cette idée d'ordre de grandeur. Soit $T(n)$ le nombre d'opérations d'un algorithme et $f$ une fonction de référence (par exemple $n$, $n^2$, $\log n$). On dit que $T$ est un $O(f(n))$ lorsqu'il existe une constante $C > 0$ et un rang $n_0$ tels que :

Autrement dit, à partir d'une certaine taille, $T(n)$ reste en dessous de $f(n)$ à une constante multiplicative près. Le grand $O$ est donc une borne supérieure sur la vitesse de croissance : il dit « ça ne grandit pas plus vite que $f$ ».

Deux règles pratiques découlent de la définition. On supprime les constantes : $O(5n) = O(n)$. Et dans une somme, on ne garde que le terme dominant : $O(n^2 + n) = O(n^2)$, car pour $n$ grand, $n^2$ écrase $n$. Ces deux réflexes suffisent à simplifier la quasi-totalité des calculs de complexité en prépa.

Les classes de complexité usuelles

Quelques fonctions de référence reviennent en permanence. Les voici de la plus rapide à la plus lente, avec un exemple typique et l'ordre de grandeur du nombre d'opérations.

La colonne $n = 1000$ dit tout. Un algorithme en $O(n^2)$ demande un million d'opérations là où un $O(n \log n)$ en demande dix mille : cent fois moins. Et l'$O(2^n)$ pour $n = 1000$ dépasse le nombre d'atomes de l'univers observable, aucune machine ne le terminera jamais. C'est pourquoi passer d'un algorithme quadratique à un algorithme quasi-linéaire change concrètement ce qui est calculable, comme on le voit sur les algorithmes de tri et de recherche au programme de prépa.

Meilleur cas, pire cas, cas moyen

Pour une même taille $n$, un algorithme n'exécute pas toujours le même nombre d'opérations : cela dépend des données précises qu'on lui donne. On distingue donc trois analyses.

• Meilleur cas : la situation la plus favorable, le plus petit nombre d'opérations possible.
• Pire cas : la situation la plus défavorable, le plus grand nombre d'opérations. C'est une garantie : l'algorithme ne sera jamais plus lent.
• Cas moyen : la moyenne sur toutes les entrées possibles, souvent plus délicate à calculer car elle suppose un modèle de probabilité sur les données.

Exemple classique, la recherche d'une valeur par parcours simple : si l'élément cherché est en première position, on s'arrête tout de suite, c'est $O(1)$ au meilleur cas. S'il est absent ou en dernière position, on parcourt tout, c'est $O(n)$ au pire cas. La recherche dichotomique, elle, est $O(1)$ au meilleur cas (on tombe pile au milieu) mais $O(\log n)$ au pire cas.

Complexité des boucles imbriquées

Les boucles sont le principal moteur de la complexité. La règle est simple : une boucle qui tourne $k$ fois multiplie par $k$ le coût de son corps. Deux boucles imbriquées multiplient donc leurs nombres d'itérations.

Le cas le plus courant, deux boucles indépendantes de $n$ tours chacune :

def compte_doublons(tab):
    n = len(tab)
    c = 0
    for i in range(n):          # n tours
        for j in range(n):      # n tours a chaque fois
            if tab[i] == tab[j]:
                c += 1
    return c

Le corps interne est en $O(1)$, exécuté $n \times n = n^2$ fois : l'algorithme est en $O(n^2)$. Attention toutefois, il ne faut pas conclure « deux boucles imbriquées donc $O(n^2)$ » de façon automatique. Tout dépend du nombre réel de tours de la boucle interne. Regardons une variante où la boucle interne démarre à i + 1 :

def compte_paires(tab):
    n = len(tab)
    c = 0
    for i in range(n):              # i de 0 a n-1
        for j in range(i + 1, n):   # n-1-i tours
            if tab[i] == tab[j]:
                c += 1
    return c

Ici la boucle interne fait $n - 1 - i$ tours. Le nombre total d'itérations est :

On trouve $\dfrac{n^2 - n}{2}$, dont le terme dominant est $\dfrac{n^2}{2}$. En supprimant la constante $\dfrac12$, cet algorithme est aussi en $O(n^2)$. Faire deux fois moins de travail ne change pas la classe de complexité : c'est un facteur constant. En revanche, une boucle interne qui ne dépend pas de $n$ (nombre fixe de tours) laisse la complexité en $O(n)$.

Le facteur $\log n$ apparaît quand une boucle divise la taille par deux à chaque tour, sans la parcourir. Une boucle while qui fait n = n // 2 jusqu'à atteindre $1$ s'exécute environ $\log_2 n$ fois : c'est exactement le mécanisme de la recherche dichotomique. Combinée à un parcours linéaire imbriqué, elle donne du $O(n \log n)$, la complexité des bons tris.

Un mot sur la complexité amortie

Certaines opérations sont coûteuses de temps en temps, mais bon marché la plupart du temps. La complexité amortie répond à cette situation : au lieu de regarder le pire cas d'une seule opération, on regarde le coût moyen d'une opération sur une longue suite d'opérations.

L'exemple canonique est l'ajout en fin de liste dynamique, le append de Python. La plupart du temps il coûte $O(1)$. Mais quand le tableau interne est plein, il faut le recopier dans un tableau plus grand, ce qui coûte $O(n)$. Comme ce doublement de capacité est rare (il se produit de moins en moins souvent à mesure que la liste grossit), le coût amorti d'un append reste $O(1)$. Sans cette analyse, on surestimerait le coût d'une suite d'ajouts.

Méthode pour analyser un code

Face à un code dont on cherche la complexité, une procédure fiable évite les erreurs. On la déroule de l'intérieur vers l'extérieur.

1. Identifier la taille $n$. C'est la longueur du tableau, de la chaîne, ou la valeur de l'entier traité. Toute la complexité s'exprime en fonction d'elle.
2. Coter chaque instruction simple à $O(1)$. Affectations, comparaisons, opérations arithmétiques, accès à une case : coût constant.
3. Additionner les blocs successifs. Deux morceaux de code exécutés l'un après l'autre : on somme leurs coûts, puis on garde le plus grand ($O(n) + O(n^2) = O(n^2)$).
4. Multiplier pour les boucles. Une boucle de $k$ tours multiplie par $k$ le coût de son corps. On imbrique en multipliant, sans oublier de vérifier le vrai nombre de tours de chaque boucle.
5. Repérer les divisions par deux. Une taille divisée par deux à chaque tour donne un facteur $\log n$.
6. Simplifier. On supprime les constantes et on ne garde que le terme dominant.

Cette lecture « de l'intérieur vers l'extérieur » se généralise aux fonctions récursives, où l'on écrit une relation de récurrence sur le coût. Elle est aussi le point de départ de la programmation dynamique, dont tout l'intérêt est de transformer une récursivité exponentielle en un calcul polynomial. Le choix de la bonne structure de données joue le même rôle : il fait souvent chuter la complexité d'une classe entière.

3 exercices corrigés · déterminer la complexité

Exercice 1, blocs successifs

Énoncé. Déterminer la complexité en temps, au pire cas, de la fonction suivante en fonction de $n =$ len(tab).

def resume(tab):
    n = len(tab)
    total = 0
    for x in tab:            # bloc 1
        total += x
    maxi = tab[0]            # bloc 2
    for x in tab:
        if x > maxi:
            maxi = x
    return total, maxi

Solution. Il y a deux boucles successives, pas imbriquées. Chacune parcourt le tableau une fois avec un corps en $O(1)$, donc chacune est en $O(n)$. Les instructions hors boucle sont en $O(1)$. On additionne les blocs :

La fonction est linéaire, en $O(n)$. Le piège serait de croire que deux boucles donnent $O(n^2)$ : c'est faux, seules des boucles imbriquées se multiplient. Des boucles successives s'additionnent.

Exercice 2, boucles imbriquées

Énoncé. Déterminer la complexité au pire cas de cette recherche de triplets, avec $n =$ len(tab).

def contient_zero_somme(tab):
    n = len(tab)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if tab[i] + tab[j] + tab[k] == 0:
                    return True
    return False

Solution. Trois boucles imbriquées, chacune parcourant une part du tableau. Le nombre de triplets $(i, j, k)$ avec $i < j < k$ examinés dans le pire cas (aucun triplet trouvé, on va jusqu'au bout) est le nombre de combinaisons de $3$ éléments parmi $n$ :

Le terme dominant de ce polynôme est $\dfrac{n^3}{6}$. Le corps de la boucle interne (une addition et une comparaison) est en $O(1)$. En supprimant la constante $\dfrac16$, la complexité est cubique, en $O(n^3)$. La règle générale se lit ici : $p$ boucles imbriquées de ce type donnent une complexité en $O(n^p)$.

Exercice 3, division par deux et terme dominant

Énoncé. Déterminer la complexité au pire cas de la fonction suivante, où tab n'est pas trié au départ, avec $n =$ len(tab).

def presence_triee(tab, cible):
    t = sorted(tab)                 # etape 1 : tri
    g, d = 0, len(t) - 1
    while g <= d:                    # etape 2 : dichotomie
        m = (g + d) // 2
        if t[m] == cible:
            return True
        elif t[m] < cible:
            g = m + 1
        else:
            d = m - 1
    return False

Solution. On analyse les deux étapes séparément, puis on additionne. L'étape 1, le tri par sorted, est en $O(n \log n)$ (c'est la complexité des tris efficaces de Python). L'étape 2 est une recherche dichotomique : à chaque tour, la boucle while divise par deux la largeur de l'intervalle $[g, d]$, elle fait donc environ $\log_2 n$ tours, chacun en $O(1)$, soit $O(\log n)$. On additionne les deux étapes successives :

On ne garde que le terme dominant : $n \log n$ écrase $\log n$. La complexité totale est $O(n \log n)$, dictée par le tri. C'est un enseignement récurrent : la dichotomie est très rapide, mais le prix à payer est le tri préalable, et c'est lui qui fixe la complexité globale. Si le tableau était déjà trié en entrée, on tomberait à $O(\log n)$.

Ce qu'il faut retenir

• La complexité mesure comment le nombre d'opérations grandit avec la taille $n$, indépendamment de la machine, en temps et en espace.
• La notation grand $O$ : $T(n) = O(f(n))$ si $T(n) \leq C f(n)$ à partir d'un certain rang. On supprime les constantes et on garde le terme dominant.
• Les classes usuelles : $O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)$.
• Meilleur / pire / moyen cas : par défaut, on raisonne au pire cas, qui donne une garantie.
• Les boucles : successives, on additionne ; imbriquées, on multiplie, en vérifiant le vrai nombre de tours. Une division par deux donne un $\log n$.
• La complexité amortie lisse le coût d'opérations parfois chères (comme append) sur une longue séquence.

L'analyse de complexité est un fil rouge de toute l'informatique de prépa : elle décide quel algorithme de tri ou de recherche utiliser, justifie les structures de données, et fonde la programmation dynamique. C'est aussi un attendu direct à l'écrit comme à l'oral d'informatique aux concours. Si tu hésites entre suivre l'option informatique en MPSI ou viser une filière où l'informatique est centrale comme la MP2I, la place qu'y tient ce raisonnement sur le coût des algorithmes est un bon indicateur de ce qui t'attend.