À quelle vitesse ? La notation grand O

À un milliard d'étapes par seconde, une méthode en n² sur un million de valeurs prend environ 17 minutes ; une méthode en n log n prend 0.02 seconde.

La croissance compte plus que le nombre exact

Jusqu'ici, nous avons compté les étapes exactement : 45 comparaisons, 4 échanges, 20 vérifications. Les comptes exacts sont utiles pour de petits exemples, mais ils dépendent de détails, comme le fait que le tri à bulles s'arrête plus tôt ou la façon de choisir un pivot. Quand l'entrée devient grande, une chose domine tout le reste : la façon dont le compte augmente quand n augmente. Un algorithme dont le nombre d'étapes croît comme n² finira toujours par perdre face à un algorithme qui croît comme n log n, quel que soit le soin apporté au réglage du premier.

La notation grand O est le raccourci qui décrit cette croissance. Écrire qu'un algorithme est en O(n²), qu'on lit « grand O de n au carré », signifie que pour n grand son nombre d'étapes est au plus une certaine constante fois n². Deux règles la rendent facile à utiliser. On supprime les facteurs constants : 3n et n/2 sont tous deux en O(n). On ne garde que le terme qui croît le plus vite : n²/2 − n/2, les comparaisons du tri par sélection, est en O(n²), car pour n grand la partie n² représente presque tout. Le cours 6.006 du MIT utilise la même idée quand il compare des structures de données et des tris par leur temps d'exécution asymptotique.

Les ordres de croissance courants

• O(1), constant. Le travail ne dépend pas de n : lire la première valeur d'une liste, ou une valeur à une position connue.
• O(log n), logarithmique. Chaque étape coupe le problème en deux : la recherche dichotomique. Un million de valeurs, environ 20 étapes.
• O(n), linéaire. Chaque valeur est traitée une fois : la recherche linéaire, trouver la plus grande valeur, additionner une liste.
• O(n log n). Le tri fusion, et le tri rapide en moyenne. Le mieux que puisse faire un tri par comparaisons.
• O(n²), quadratique. Chaque paire est examinée : le tri à bulles, par sélection et par insertion dans le pire cas, ou deux boucles imbriquées l'une dans l'autre.
• O(2ⁿ), exponentiel. Le travail double à chaque valeur supplémentaire : essayer tous les sous-ensembles de n objets, ou déplacer n disques dans les tours de Hanoï.

Ce que les nombres signifient en secondes

Imagine un ordinateur qui effectue un milliard (10⁹) d'étapes élémentaires par seconde, un chiffre rond raisonnable pour un cœur de processeur. Voici ce que chaque ordre de croissance signifie pour un million de valeurs. O(log n) représente environ 20 étapes, bien moins d'une microseconde. O(n) représente un million d'étapes, une milliseconde. O(n log n) représente environ 20 millions d'étapes, 0.02 seconde. O(n²) représente 10¹² étapes, mille secondes, soit environ 17 minutes. O(2ⁿ) ne peut pas être terminé : 2 puissance un million est un nombre de plus de 300 000 chiffres. C'est pourquoi choisir le bon algorithme compte en général bien plus qu'acheter un ordinateur plus rapide. Une machine dix fois plus rapide transforme 17 minutes en 1.7 minute ; passer de O(n²) à O(n log n) les transforme en un cinquantième de seconde.

Lire le grand O dans le code

On peut souvent lire l'ordre de croissance directement dans la forme du code. Une seule boucle sur la liste est en O(n). Deux boucles, l'une dans l'autre, toutes deux sur la liste, sont en O(n²) : pour chacun des n tours extérieurs, la boucle intérieure fait jusqu'à n tours. Une boucle qui divise un nombre par deux à chaque fois, comme while (n > 1) n = Math.floor(n / 2), est en O(log n) : en partant de 1000, elle tourne 9 fois, en partant d'un million, 19 fois. Les étapes qui se suivent s'additionnent, et c'est le plus grand terme qui l'emporte : une boucle en O(n) suivie d'une boucle en O(n²) donne O(n²) au total.

// O(n) : un seul passage
let total = 0;
for (const x of list) total += x;

// O(n²) : toutes les paires
for (let i = 0; i < list.length; i++)
  for (let j = i + 1; j < list.length; j++)
    if (list[i] === list[j]) console.log("duplicate", list[i]);

// O(log n) : divisions par deux
let k = list.length, rounds = 0;
while (k > 1) { k = Math.floor(k / 2); rounds++; }

Meilleur cas, cas moyen et pire cas

Un même algorithme peut se comporter très différemment selon les entrées. Le tri par insertion est en O(n) sur une liste déjà triée et en O(n²) sur une liste inversée. Le tri rapide est en O(n log n) en moyenne et en O(n²) avec des pivots toujours mauvais. Quand on cite un seul grand O sans préciser le cas, on parle en général du pire cas, car c'est une garantie : l'algorithme ne fera jamais pire. Le grand O laisse aussi des choses de côté. Il ignore les facteurs constants : pour de petites entrées, une méthode en O(n²) aux étapes très simples peut battre une méthode en O(n log n). C'est pourquoi beaucoup de vraies fonctions de tri passent au tri par insertion pour les petits morceaux de la liste.