Introduction à la complexité

Objectifs

À la fin de cette leçon, vous saurez :

• expliquer pourquoi deux algorithmes justes peuvent avoir des performances très différentes ;
• reconnaître les ordres de grandeur O(1), O(n) et O(n²) ;
• estimer le coût d'un algorithme à partir de ses boucles ;
• mesurer au lieu de deviner, avec console.time.

🔗 Pour vous rafraîchir la mémoire : le tri sans sort()

Le même résultat, deux coûts

Deux fonctions qui répondent « contient un doublon ? » :

// Version A : comparer toutes les paires
function aUnDoublonA(valeurs) {
  for (let i = 0; i < valeurs.length; i++) {
    for (let j = i + 1; j < valeurs.length; j++) {
      if (valeurs[i] === valeurs[j]) {
        return true;
      }
    }
  }
  return false;
}

// Version B : mémoriser ce qu'on a déjà vu
function aUnDoublonB(valeurs) {
  const vus = [];
  for (const v of valeurs) {
    if (vus.includes(v)) {
      return true;
    }
    vus.push(v);
  }
  return false;
}

Les deux sont correctes. Mais sur 10 000 éléments, la version A fait jusqu'à ~50 millions de comparaisons quand la version B en fait quelques dizaines de milliers. C'est cette différence que mesure la complexité.

Les trois ordres à connaître

O(1) : temps constant

Le travail ne dépend pas de la taille des données.

const premier = liste[0];        // accès par index : direct
liste.push(valeur);              // ajout en fin : direct

Millier ou million d'éléments : même coût. C'est l'idéal.

O(n) : proportionnel à n

Une seule passe sur les données.

let total = 0;
for (const v of liste) {
  total += v;                    // chaque élément visité une fois
}

Doubler les données double le travail. Sommes, minima, recherches linéaires : O(n).

O(n²) : proportionnel au carré de n

Pour chaque élément, on reparcourt les éléments : boucles imbriquées.

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    // n × n tours
  }
}

Doubler les données quadruple le travail. Le tri par sélection du défi précédent et la version A ci-dessus sont dans ce cas.

Repérer l'ordre d'un algorithme

Règles rapides de lecture :

pas de boucle (ou boucle de taille fixe)     → O(1)
une boucle sur les données                   → O(n)
boucle imbriquée dans une boucle sur n       → O(n²)
appel coûteux répété dans une boucle         → multiplier

La dernière règle explique aUnDoublonB : la boucle est O(n), mais includes parcourt vus — donc O(n) par tour, soit O(n × n) au pire. En réalité elle s'arrête tôt et son cas moyen est bien meilleur que la version A ; retenez surtout la méthode : repérez la boucle dans la boucle.

Mesurer plutôt que deviner

Node fournit un chronomètre intégré :

console.time("doublon");
aUnDoublonA(grandeListe);
console.timeEnd("doublon");   // doublon: 842.311ms

Protocole honnête : mêmes données pour les deux versions, plusieurs exécutions, tailles croissantes (1 000, 10 000…). Vous verrez alors la courbe quadratique s'effondrer pendant que la version linéaire reste plate.

La règle du métier

Ne pas optimiser prématurément : un O(n²) sur dix éléments est parfait. Mais connaître ces ordres permet, dès la conception, d'éviter les structures qui ne passeront pas à l'échelle. D'abord correct, ensuite mesuré, enfin optimisé si nécessaire.

Exercice

Donnez l'ordre de complexité (O(1), O(n) ou O(n²)) de chaque extrait :

function milieu(liste) {
  return liste[Math.floor(liste.length / 2)];
}

function somme(liste) {
  let total = 0;
  for (const v of liste) {
    total += v;
  }
  return total;
}

function paires(liste) {
  const resultat = [];
  for (const a of liste) {
    for (const b of liste) {
      resultat.push([a, b]);
    }
  }
  return resultat;
}

function contient(liste, cible) {   // recherche linéaire
  return liste.includes(cible);
}

function verifierTous(liste, candidats) {
  let ok = true;
  for (const c of candidats) {
    if (!contient(liste, c)) {
      ok = false;
    }
  }
  return ok;
}

(indice : regardez ce qui se passe dans la boucle)

5. Avec la version A de aUnDoublon, combien de comparaisons approximativement pour 1 000 éléments ? Et pour 2 000 ?

Résumé

• Complexité = évolution du travail quand les données grossissent.
• O(1) indépendant, O(n) une passe, O(n²) boucles imbriquées.
• Un appel coûteux répété dans une boucle multiplie les coûts.
• console.time / console.timeEnd : toujours mesurer avant d'optimiser.