Complexité

Nous avons maintenant ce qui manquait aux sept premières leçons : deux algorithmes de recherche et deux algorithmes de tri, tous corrects, dont certains sont manifestement meilleurs que d'autres. Reste à dire en quoi, et à le dire autrement que par « il a l'air plus rapide ».

Compter, plutôt que chronométrer

Le réflexe naturel est de mesurer un temps d'exécution. C'est une mauvaise mesure, pour trois raisons.

Elle dépend de la machine : le même algorithme est dix fois plus rapide sur un ordinateur récent, sans avoir changé d'une ligne. Elle dépend du langage et du contexte : compilateur, autres programmes en cours, mémoire disponible. Et surtout, elle ne dit rien de ce qui compte vraiment — comment le coût évolue quand les données grandissent.

On compte donc les opérations élémentaires : comparaisons, affectations, accès à une case de tableau. Le résultat est un nombre en fonction de n, la taille des données. Il est indépendant de la machine, et il se calcule sur le papier, sans exécuter le programme.

Reprenons nos algorithmes.

L'ordre de grandeur

Le tri par sélection fait exactement $n(n-1)/2$ comparaisons, soit $n^2/2 - n/2$. Pour n = 1000, cela fait 499 500. Le terme $n^2/2$ en vaut 500 000 : le second terme ne pèse que 0,1 % du total, et son poids relatif diminue encore quand n grandit.

D'où la convention centrale de cette leçon. On ne garde que le terme dominant, et on oublie les constantes multiplicatives. $n^2/2 - n/2$ devient $n^2$, et on écrit :

Cela se lit « est en grand O de n carré » et signifie : quand n devient grand, le coût croît comme le carré de n. La notation ne prétend pas donner le nombre exact d'opérations — elle donne la forme de la croissance, qui est la seule chose qui survive au changement de machine.

Jeter les constantes peut sembler cavalier. C'est un choix assumé : un algorithme deux fois plus lent le reste toujours, alors qu'un algorithme d'une classe supérieure devient arbitrairement pire à mesure que les données grandissent. La classe l'emporte toujours, pourvu que n soit assez grand.

Les cinq classes à connaître

La colonne de droite est la plus utile en pratique. Elle donne un test mental immédiat : si je double mes données, qu'arrive-t-il à mon temps de calcul ?

Voici ce que ces classes donnent sur des données réelles, à raison d'un million d'opérations par seconde.

Un million de valeurs à trier, ce n'est pas beaucoup : c'est un carnet d'adresses d'entreprise. Onze jours contre vingt secondes, c'est toute la différence entre les tris de la leçon 7 et ceux que vous rencontrerez en L2.

Deviner la classe en lisant le code

Pour les algorithmes de ce cours, quatre règles suffisent.

Une suite d'instructions simples, sans boucle, coûte $O(1)$ — quel que soit leur nombre. Dix affectations restent une constante.

Une boucle qui parcourt les données une fois coûte $O(n)$.

Deux boucles imbriquées parcourant chacune les données coûtent $O(n^2)$ : pour chacun des n tours de la boucle externe, la boucle interne en fait n. C'est la signature visuelle des deux tris de la leçon 7.

Une boucle qui divise par deux à chaque tour coûte $O(\log n)$ : c'est la dichotomie. Le critère n'est pas la forme de la boucle mais ce qu'elle fait à la quantité de travail restante — la réduire d'un élément donne $O(n)$, la réduire de moitié donne $O(\log n)$.

Attention à une nuance : deux boucles imbriquées ne sont pas deux boucles successives. Deux parcours l'un après l'autre coûtent $n + n = 2n$, soit $O(n)$ — pas $O(n^2)$. C'est l'imbrication qui multiplie, la succession additionne.

Mesurer pour vérifier

La théorie annonce $O(n^2)$ pour le tri par sélection. Vérifions-le en comptant réellement, plutôt qu'en le croyant sur parole.

// Ne chronométrez pas : comptez.
// Placez l'incrément du compteur au bon endroit, puis lisez le tableau
// de résultats : quand n est multiplié par 10, par combien le nombre de
// comparaisons est-il multiplié ?
function comparaisonsTriSelection(n) {
  const a = Array.from({ length: n }, (_, k) => n - k); // tableau à l'envers
  let comparaisons = 0;

  for (let i = 0; i < a.length - 1; i++) {
    let indiceMin = i;
    for (let j = i + 1; j < a.length; j++) {
      // à compléter : une comparaison a lieu ici, à chaque tour
      if (a[j] < a[indiceMin]) indiceMin = j;
    }
    const tmp = a[i];
    a[i] = a[indiceMin];
    a[indiceMin] = tmp;
  }

  return comparaisons;
}

console.log("n\tmesuré\tn(n-1)/2");
for (const n of [10, 100, 1000]) {
  console.log(n, comparaisonsTriSelection(n), (n * (n - 1)) / 2);
}

Multipliez n par 10 et observez : le nombre de comparaisons est multiplié par environ 100. C'est la signature de $O(n^2)$, obtenue sans chronomètre et sans dépendre de votre machine.

Ce que vous savez faire maintenant

Le parcours de ces huit leçons a une logique. Les leçons 1 à 4 ont installé les trois briques dont tout algorithme est fait : un état (les variables), des choix (les conditions), des répétitions (les boucles). Les leçons 5 à 7 les ont appliquées à une vraie structure de données, le tableau, en résolvant deux problèmes concrets : chercher et trier. La leçon 8 est revenue sur ces algorithmes pour les mesurer.

Cet ordre était délibéré. La notation $O(n)$ placée en ouverture d'un cours reste un formalisme creux ; placée ici, elle répond à une question que vous vous posiez déjà depuis la leçon 6, quand la dichotomie a écrasé la recherche séquentielle sans qu'on sache encore comment nommer cet écart.

Trois réflexes à emporter. Tracer avant de conclure : dérouler un algorithme à la main sur un petit exemple reste le seul moyen fiable de savoir ce qu'il fait vraiment. Compter avant de comparer : deux algorithmes corrects ne se valent pas, et l'intuition se trompe souvent sur lequel est le meilleur. Regarder les boucles imbriquées : c'est là que se cache le coût.

À retenir