Bases de la complexité

Introduction

Le parcours séquentiel du cours précédent est en place. Les algorithmes qui suivent sont plus subtils, et la première question d'un informaticien devant un algorithme n'est pas « est-ce qu'il marche ? » mais « combien coûte-t-il ? ». Combien d'opérations effectue-t-il selon la taille des données ? Si l'entrée double, le temps double-t-il, quadruple-t-il, ou augmente-t-il à peine ? Ce cours pose le socle de cette analyse. Pas de théorème lourd : juste une intuition claire et une notation simple, qui servent dans tout le reste du chapitre.

Pourquoi mesurer ?

Deux programmes font la même chose : chercher un nom dans un annuaire de 10 millions d'entrées. Le premier met 3 secondes, le second met 3 minutes. Le premier est évidemment préférable. La complexité, c'est l'outil qui permet de prédire cette différence avant même d'exécuter le code, en analysant la structure de l'algorithme.

Taille de l'entrée

Avant de compter, il faut décider de ce qu'est la taille $n$. C'est en général évident :

• pour un tableau ou une liste : $n$ = le nombre d'éléments,
• pour une chaîne de caractères : $n$ = sa longueur,
• pour un entier $k$ : $n$ = sa valeur (parfois son nombre de chiffres).

Trois ordres de grandeur typiques

Coût constant : $\mathcal{O}(1)$

Le coût ne dépend pas de la taille. Que tableau ait 10 ou 10 millions d'éléments, l'opération prend le même temps.

def premier(tableau):
    return tableau[0]   # un seul accès, peu importe la taille

Coût linéaire : $\mathcal{O}(n)$

Le coût est proportionnel à $n$. Si on double la taille, le temps double. Tout parcours séquentiel du cours précédent est dans ce cas.

def somme(tableau):
    total = 0
    for v in tableau:   # exactement n tours
        total += v
    return total

Coût quadratique : $\mathcal{O}(n^2)$

Le coût est proportionnel à $n^2$. Si on double la taille, le temps est multiplié par 4. On l'obtient typiquement avec deux boucles imbriquées qui parcourent chacune le tableau.

def doublons(tableau):
    """Renvoie True si tableau contient au moins un doublon."""
    n = len(tableau)
    for i in range(n):
        for j in range(i + 1, n):
            if tableau[i] == tableau[j]:
                return True
    return False

Le nombre de comparaisons est de l'ordre de $n \times n / 2$, ce qui reste proportionnel à $n^2$.

La notation grand-O, en douceur

On a écrit $\mathcal{O}(n)$, $\mathcal{O}(n^2)$. Que signifie ce symbole ?

L'idée : on néglige les constantes et les détails de petite taille pour ne garder que l'ordre de grandeur quand $n$ devient grand. Par exemple, un algorithme qui fait $3n + 7$ opérations et un autre qui en fait $n - 1$ ont le même comportement asymptotique (c'est-à-dire la même allure quand $n$ devient grand) : tous deux sont en $\mathcal{O}(n)$. Quand $n$ atteint 1 million, le « +7 » et le « ×3 » sont sans importance face au grand $n$.

Le cours 4 (dichotomie) ajoute $\mathcal{O}(\log n)$ à cette liste, un coût encore plus petit que $\mathcal{O}(n)$, qui croît extrêmement lentement.

Comparer les ordres de grandeur

Pour un million d'éléments, un algorithme logarithmique finit en 20 étapes ; un algorithme linéaire en un million ; un algorithme quadratique en mille milliards, ce qui est irréalisable en pratique.

Cas pire, cas moyen

Tous les algorithmes n'effectuent pas le même nombre d'opérations sur toutes les entrées de même taille. La recherche linéaire peut :

• trouver dès la 1ère case (cas favorable, 1 comparaison) ;
• trouver à la dernière case ou ne rien trouver (cas pire, $n$ comparaisons).

On parle souvent du cas pire car c'est la garantie maximale offerte par l'algorithme. Quand on dit « la recherche linéaire est en $\mathcal{O}(n)$ », c'est au pire ; au mieux, elle est en $\mathcal{O}(1)$.

Pièges courants

• Compter en secondes au lieu de compter des opérations : trompeur, car dépendant de la machine.
• Garder les constantes dans la notation $\mathcal{O}$ : on écrit $\mathcal{O}(n)$, jamais $\mathcal{O}(3n + 5)$.
• Confondre cas pire et cas moyen : à l'oral, préciser quand c'est ambigu.

Pour aller plus loin

Ces ordres de grandeur se vérifient dans les cours suivants : les tris du cours 3 sont en $\mathcal{O}(n^2)$, la dichotomie du cours 4 est en $\mathcal{O}(\log n)$. La différence de performance entre les deux dernières est colossale : un algorithme dichotomique sur un milliard d'éléments tient en 30 étapes seulement.