Bases de la complexité

Introduction

Vous savez maintenant écrire un parcours séquentiel. Mais vous écrirez bientôt des algorithmes plus subtils, et la première question d'un informaticien devant un algorithme n'est pas « est-ce qu'il marche ? » — c'est « combien coûte-t-il ? ». Combien d'opérations effectue-t-il selon la taille des données ? Si je double l'entrée, 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 vous serviront dans tout le reste du chapitre.

Pourquoi mesurer ?

Imaginez deux programmes qui 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. Vous préférerez le premier, évidemment. 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$.

Vous rencontrerez aussi $\mathcal{O}(\log n)$ au cours 4 (dichotomie) — c'est 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 — 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

Vous allez vérifier ces ordres de grandeur 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.