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²) et les relier aux structures de code ;
• estimer le coût d'un algorithme à partir de ses boucles, y compris les appels coûteux cachés ;
• 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 répondant « ce tableau contient-il 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 — mêmes réponses sur toutes les entrées. Mais comptons leur travail :

• Version A : chaque élément comparé à tous les suivants → environ n²/2 comparaisons. Sur 10 000 éléments : ~50 millions.
• Version B : un parcours principal de n tours ; chaque includes parcourt au pire vus... donc aussi jusqu'à ~n²/2 au pire absolu, mais en pratique elle s'arrête très tôt (les doublons proches sont détectés vite) et son cas typique est de quelques dizaines de milliers d'opérations.

Même contrat, écarts de coût gigantesques. La complexité est précisément l'outil qui décrit cette différence — non pas en secondes (ça dépend de la machine), mais en évolution du travail quand les données grossissent.

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
const taille = liste.length;  // lecture d'une propriété : directe

Millier ou million d'éléments : même coût. C'est l'idéal — et c'est pour cela que l'accès par index est si précieux comparé à la recherche linéaire (includes, O(n)) vue hier.

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, comptages, minima/maxima, recherches linéaires : O(n). Vous en avez écrit une douzaine dans ce chapitre sans le savoir.

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 (~n²/2 comparaisons) vit ici, ainsi que la version A ci-dessus.

Ce que ça donne concrètement

Tableau du nombre d'étapes selon la taille, pour se faire une intuition chiffrée :

Taille n	O(1)	O(n)	O(n²)
10	1	10	100
1 000	1	1 000	1 000 000
10 000	1	10 000	100 000 000
100 000	1	100 000	10 000 000 000

Lecture verticale, la plus parlante : quand n devient cent fois plus grand, le O(n) devient cent fois plus lent (supportable), le O(n²) dix mille fois (catastrophe). C'est tout l'intérêt de raisonner en ordres plutôt qu'en millisecondes mesurées aujourd'hui : prévoir le comportement à l'échelle, pas seulement sur sa machine.

Repérer l'ordre d'un algorithme

Règles rapides de lecture, applicables dès maintenant à votre propre code :

pas de boucle sur les données                  → O(1)
une seule 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 les coûts

La dernière règle est la plus subtile, car la boucle interne peut être cachée dans une méthode. Relisez aUnDoublonB avec ces lunettes : la boucle principale est O(n), mais chaque includes parcourt vus — un appel potentiellement O(n) par tour. Boucle dans la boucle, même déguisée. En pratique elle s'arrête tôt (sortie anticipée dès qu'un doublon apparaît), ce qui rend son cas moyen bien meilleur que la version A ; retenez surtout la méthode de repérage : « que fait-on à CHAQUE tour ? ».

Autres exemples de coûts cachés à connaître :

liste.includes(x);       // O(n) : parcourt jusqu'à trouver
liste.slice();           // O(n) : copie tout
`${a}${b}` sur textes énormes ; // O(longueur totale) : nouvelle chaîne fabriquée

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 pour comparer deux versions :

1. mêmes données pour les deux (générez-les une fois, partagez-les) ;
2. tailles croissantes : 1 000, puis 5 000, puis 10 000 ;
3. plusieurs exécutions chacune (le premier essai inclut des réglages internes).

Vous verrez alors la courbe quadratique exploser pendant que la version linéaire reste quasi plate. Cette expérience vaut tous les discours — faites-la une fois, vous n'oublierez jamais ce que « quadratique » veut dire en secondes.

La règle du métier

Ne pas optimiser prématurément : un O(n²) sur dix éléments est parfait — souvent plus lisible que son alternative rusée. Mais connaître ces ordres permet, dès la conception, d'éviter les structures qui ne passeront pas à l'échelle. L'ordre des priorités professionnel :

1. Correct        (il marche, cas limites compris)
2. Clair          (quelqu'un d'autre peut le lire)
3. Mesuré         (on a vérifié là où ça compte)
4. Optimisé       (seulement si la mesure l'exige)

Exercice

Donnez l'ordre de complexité (O(1), O(n) ou O(n²)) de chaque extrait, en justifiant par sa structure :

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 verifierTous(liste, candidats) {
  let ok = true;
  for (const c of candidats) {
    if (!liste.includes(c)) {   // regardez ce qui se passe DANS la boucle
      ok = false;
    }
  }
  return ok;
}

5. Avec la version A de aUnDoublon (~n²/2 comparaisons), combien d'opérations approximativement pour 1 000 éléments ? Et pour 2 000 ? Que remarquez-vous ?

6. Reliez au défi précédent : quel est l'ordre de trierCroissant ? Justifiez avec la structure de ses deux boucles.

Résumé

• Complexité = évolution du travail quand n grossit ; indépendante de la machine.
• O(1) accès direct ; O(n) une passe ; O(n²) boucles imbriquées.
• Un appel coûteux répété dans une boucle multiplie les coûts — même s'il est caché dans une méthode.
• console.time/timeEnd + tailles croissantes : toujours mesurer avant d'optimiser.
• Ordre des priorités : correct, clair, mesuré, optimisé.