L'analyse d'algorithmes (Big O)

Les algorithmes sont la part la plus importante et la plus durable de l'informatique parce qu'on peut les étudier indépendamment d'un langage ou d'une machine. Pour en tirer parti, il faut savoir comparer l'efficacité de deux algorithmes sans les implémenter ni sortir le chronomètre. Skiena nous arme de deux outils : le modèle RAM de calcul, et l'analyse asymptotique de la complexité au pire cas — la fameuse notation « grand O ».

C'est la partie la plus mathématique du livre, mais aussi la plus rentable. Une fois l'intuition acquise, le formalisme devient un réflexe : vous saurez regarder une boucle imbriquée et annoncer « ça, c'est quadratique » avant même d'avoir fini de la lire. Les exemples du livre sont en C ; nous les traduisons en TypeScript idiomatique, avec la complexité annotée à chaque fois.

Le modèle RAM : compter les pas

La conception d'algorithmes indépendante de la machine repose sur un ordinateur hypothétique : la machine à accès aléatoire (Random Access Machine, RAM). Ce modèle pose trois règles simples :

• Chaque opération simple (+, *, -, =, if, appel de fonction) coûte exactement un pas de temps.
• Les boucles et sous-programmes ne sont pas des opérations simples : ce sont des compositions de pas élémentaires. Trier 1 000 000 d'éléments prend forcément plus de temps que trier 10 éléments ; le coût dépend du nombre d'itérations.
• Chaque accès mémoire coûte un pas, et l'on dispose d'autant de mémoire qu'on veut. Le modèle RAM ignore si la donnée est en cache ou sur disque.

Sous le modèle RAM, on mesure le temps d'exécution en comptant le nombre de pas que prend l'algorithme sur une instance donnée. Si la machine exécute un nombre fixe de pas par seconde, ce décompte se convertit naturellement en temps réel.

Est-ce trop simpliste ? Sur un vrai processeur, multiplier coûte plus cher qu'additionner, le loop unrolling du compilateur viole l'idée de pas élémentaire, et les temps d'accès mémoire varient énormément. Trois hypothèses, trois fois fausses. Et pourtant le modèle RAM reste excellent en pratique : il capture le comportement essentiel des ordinateurs tout en restant facile à manipuler.

Pire cas, meilleur cas, cas moyen

Compter les pas sur une instance ne suffit pas : pour juger un algorithme « en général », il faut savoir comment il se comporte sur toutes les instances. Imaginez tracer un point par instance, l'axe horizontal étant la taille du problème (le nombre d'éléments à trier, par exemple) et l'axe vertical le nombre de pas. Les points s'alignent en colonnes (seules les tailles entières existent), et l'on définit trois courbes :

• La complexité au pire cas (worst-case complexity) : le maximum de pas sur une instance de taille n. C'est la courbe qui passe par le point le plus haut de chaque colonne.
• La complexité au meilleur cas (best-case complexity) : le minimum de pas sur une instance de taille n.
• La complexité en moyenne (average-case complexity) : la moyenne sur toutes les instances de taille n.

C'est le pire cas qui se révèle le plus utile en pratique, ce qui surprend souvent. L'analogie de Skiena : vous entrez au casino avec n dollars. Le meilleur cas — repartir propriétaire des lieux — est possible mais si improbable qu'il ne mérite pas une pensée. Le pire cas — tout perdre — est facile à calculer et désespérément probable. Le cas moyen, lui, est difficile à établir et son sens prête à débat : la moyenne sur quel public ? On évite toutes ces subtilités en se contentant du pire cas, et l'on obtient un résultat très utile.

La notation grand O

Les complexités au pire, meilleur et moyen cas sont des fonctions numériques de la taille du problème. Mais elles sont pénibles à manier précisément, pour deux raisons. D'abord elles ont trop de bosses : la recherche dichotomique tourne un peu plus vite quand n = 2^k − 1, parce que les partitions tombent juste — un détail sans importance, mais qui rend la fonction exacte chaotique. Ensuite elles exigent trop de détails : écrire T(n) = 12754·n² + 4353·n + 834·lg²n + 13546 serait un travail considérable qui n'apporte rien de plus que l'observation « le temps croît de façon quadratique ».

La notation grand O simplifie l'analyse en ignorant les niveaux de détail qui n'influencent pas la comparaison :

• f(n) = O(g(n)) signifie que c·g(n) est une borne supérieure sur f(n) : il existe une constante c telle que f(n) ≤ c·g(n) pour n assez grand (n ≥ n₀).
• f(n) = Ω(g(n)) signifie que c·g(n) est une borne inférieure : f(n) ≥ c·g(n) pour n ≥ n₀.
• f(n) = Θ(g(n)) signifie que g(n) borne f(n) des deux côtés à des constantes près — c'est une borne serrée.

Deux choses sont volontairement jetées par-dessus bord. Les constantes multiplicatives d'abord : f(n) = 2n et g(n) = n sont identiques en grand O. Si un programme C tourne deux fois plus vite que le même algorithme en Java, ce facteur 2 ne dit rien sur l'algorithme lui-même. Les petites entrées ensuite : on ne se soucie pas de ce qui se passe à gauche de n₀. Peu importe lequel de deux tris est plus rapide sur six éléments ; on veut savoir lequel gagne sur 10 000 ou 1 000 000.

Le signe « = » est ici trompeur : n² = O(n³) se lit « n² est l'une des fonctions qui sont en O(n³) ». Il ne s'agit pas d'une égalité au sens habituel, mais d'une appartenance à une classe.

Les classes de croissance dominantes

Le grand O range les fonctions en classes ; toutes les fonctions d'une même classe sont équivalentes. On dit qu'une fonction à croissance plus rapide domine une fonction plus lente — g domine f quand f(n) = O(g(n)) sans réciproque, ce qu'on note g ≫ f. La bonne nouvelle : seules quelques classes apparaissent dans l'analyse courante. Les voici par ordre de domination croissante.

Classe	Notation	Origine typique
Constante	O(1)	Additionner deux nombres ; min(n, 100).
Logarithmique	O(log n)	Recherche dichotomique ; hauteur d'arbre.
Linéaire	O(n)	Parcourir chaque élément une fois (max, min, moyenne).
Superlinéaire	O(n log n)	Quicksort, mergesort.
Quadratique	O(n²)	Examiner toutes les paires (tri par sélection, par insertion).
Cubique	O(n³)	Énumérer tous les triplets (produit de matrices, certains DP).
Exponentielle	O(2ⁿ)	Énumérer tous les sous-ensembles de n éléments.
Factorielle	O(n!)	Générer toutes les permutations de n éléments.

Tout ce qu'il faut retenir tient sur une ligne, du plus lent au plus rapide à croître :

1 ≪ log n ≪ n ≪ n·log n ≪ n² ≪ n³ ≪ 2ⁿ ≪ n!

Pourquoi le grand O grossier suffit

La raison d'être de cette analyse « grossière » apparaît dès qu'on chiffre les temps. Le tableau ci-dessous suppose une machine qui exécute une opération par nanoseconde, et donne le temps de calcul pour différentes tailles.

f(n)	n = 10⁶	n = 10⁹
log n	0,02 µs	0,03 µs
n	1 ms	1 s
n log n	≈ 20 ms	≈ 30 s
n²	16,7 min	31,7 années
2ⁿ	hors d'atteinte	hors d'atteinte
n!	hors d'atteinte	hors d'atteinte

Les conclusions que Skiena en tire sont nettes :

• Pour n = 10, tous ces algorithmes prennent à peu près le même temps.
• Un algorithme en n! devient inutilisable dès n ≥ 20 ; un algorithme en 2ⁿ tient un peu plus longtemps mais cale au-delà de n > 40.
• Le quadratique n² reste utilisable jusqu'à n ≈ 10 000, puis se dégrade vite — sans espoir pour n > 1 000 000.
• Le linéaire et le n log n restent praticables sur un milliard d'éléments.
• Un algorithme O(log n) ne transpire jamais, quelle que soit la valeur imaginable de n.

Travailler avec le grand O

Manipuler le grand O ressemble à simplifier des expressions algébriques du lycée, avec deux règles d'or.

La somme est gouvernée par le terme dominant : O(f(n)) + O(g(n)) → O(max(f(n), g(n))). C'est ce qui permet d'écrire n³ + n² + n + 1 = O(n³) — tout le reste est broutille à côté du terme dominant. L'intuition : au moins la moitié de f(n) + g(n) provient de la plus grande des deux fonctions, donc supprimer la plus petite divise la valeur par 2 au plus, soit une simple constante.

Le produit conserve les deux facteurs : O(f(n)) · O(g(n)) → O(f(n)·g(n)). Multiplier par une constante positive c > 0 ne change rien (O(c·f(n)) → O(f(n))), mais quand les deux facteurs croissent, les deux comptent : O(n! · log n) domine bien n!.

Raisonner sur des boucles

Le raisonnement « grossier » donne presque toujours le bon résultat : le temps au pire cas découle du produit du nombre maximal d'itérations de chaque boucle imbriquée. Voyons-le sur le tri par sélection (selection sort), qui cherche répétitivement le plus petit élément restant et le place en fin de zone triée.

// Tri par sélection — O(n²) au pire, au meilleur et en moyenne.
function selectionSort(s: number[]): void {
  const n = s.length;
  for (let i = 0; i < n; i++) {
    let min = i;
    for (let j = i + 1; j < n; j++) {
      if (s[j] < s[min]) min = j;
    }
    [s[i], s[min]] = [s[min], s[i]]; // échange
  }
}

La boucle externe tourne n fois ; la boucle interne tourne n − i − 1 fois. Le nombre exact d'exécutions du if vaut S(n) = (n−1) + (n−2) + ... + 2 + 1. On peut le borner sans résoudre la somme : il y a au plus n termes valant au plus n−1, donc S(n) ≤ n(n−1) = O(n²) ; et il y a n/2 termes supérieurs à n/2, donc S(n) ≥ (n/2)·(n/2) = Ω(n²). Ensemble, cela donne Θ(n²) : le tri par sélection est quadratique.

Pour bien voir d'où sort le n², comptons explicitement les comparaisons :

// Compte les comparaisons d'une double boucle imbriquée.
// Retourne n(n-1)/2, soit Θ(n²).
function countComparisons(n: number): number {
  let count = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      count++; // une comparaison par paire (i, j)
    }
  }
  return count;
}
// countComparisons(5)  ->  10
// countComparisons(100) -> 4950

Cette règle de multiplication s'étend aux sommations imbriquées. Le produit de matrices élémentaire est trois boucles imbriquées de dimensions x, y, z : le nombre de multiplications vaut Σ Σ Σ 1 = x·y·z, soit O(xyz). Quand les trois dimensions sont égales, c'est O(n³) — un algorithme cubique.

Logarithmes : d'où vient le « log »

Un logarithme est simplement une fonction exponentielle inverse : b^x = y équivaut à x = log_b(y). Les exponentielles croissent à un rythme affolant (demandez à quiconque rembourse un crédit) ; leurs inverses, les logarithmes, croissent donc délicieusement lentement. Les logarithmes surgissent partout où l'on divise ou double quelque chose à répétition.

La recherche dichotomique (binary search) en est l'exemple canonique. Pour trouver un nom dans un annuaire de n noms, on compare au nom du milieu ; quel que soit le côté, une seule comparaison élimine la moitié des noms. Le nombre d'étapes est le nombre de fois où l'on peut diviser n par deux jusqu'à n'avoir plus qu'un nom : par définition, log₂ n. Vingt comparaisons suffisent ainsi à trouver n'importe quel nom dans l'annuaire d'un million de noms de Manhattan.

// Recherche dichotomique sur un tableau trié — O(log n).
// Retourne l'indice de la cible, ou -1 si absente.
function binarySearch(a: number[], target: number): number {
  let lo = 0;
  let hi = a.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] === target) return mid; // trouvé
    if (a[mid] < target) lo = mid + 1; // moitié droite
    else hi = mid - 1; // moitié gauche
  }
  return -1; // chaque tour divise l'intervalle par deux
}

Le même log apparaît dans la hauteur des arbres. Le nombre de feuilles d'un arbre binaire double à chaque niveau de hauteur ajouté ; pour n feuilles, n = 2^h, donc h = log₂ n. Plus généralement, un arbre où chaque nœud a d enfants a une hauteur h = log_d n. La chute : des arbres très courts peuvent avoir énormément de feuilles, et c'est précisément pourquoi les arbres binaires sont au cœur des structures de données rapides. Le même raisonnement compte les bits nécessaires pour représenter n possibilités : w = log₂ n bits, car chaque bit ajouté double le nombre de motifs.

La base du log n'a pas d'importance

Deux propriétés sont capitales pour l'algorithmicien. D'abord, la base du logarithme n'a aucun effet sur le taux de croissance. Comparez log₂(10⁶) ≈ 19,93, log₃(10⁶) ≈ 12,58 et log₁₀₀(10⁶) = 3 : un énorme changement de base ne produit qu'une petite différence de valeur. Changer de base revient à diviser par une constante (log_a b = log_c b / log_c a), facteur que le grand O efface. On est donc toujours justifié à ignorer la base : on écrit O(log n) sans préciser.

C'est ce qui fait la puissance de la recherche dichotomique sur tant de problèmes : le logarithme rabote n'importe quelle fonction à sa taille. Comme log(n^b) = b·log n, le log d'un polynôme reste O(log n). Chercher dans un tableau trié de n² éléments ne demande que deux fois plus de comparaisons que sur n éléments. Et le même principe s'applique au diviser pour régner : l'exponentiation rapide calcule aⁿ en O(log n) multiplications en exploitant aⁿ = (a^{n/2})², divisant l'exposant par deux à chaque étape.

À retenir

• Le modèle RAM compte chaque opération simple et chaque accès mémoire pour un pas ; assez fidèle pour analyser un algorithme sans l'implémenter ni dépendre de la machine.
• On raisonne au pire cas : facile à calculer, toujours une garantie — contrairement au cas moyen, ambigu, et au meilleur cas, illusoire.
• La notation grand O ignore les constantes multiplicatives et les petites entrées : O borne par le haut, Ω par le bas, Θ serre des deux côtés.
• Mémorisez la hiérarchie 1 ≪ log n ≪ n ≪ n log n ≪ n² ≪ n³ ≪ 2ⁿ ≪ n! : n et n log n passent le milliard, n² cale vers 10⁶, 2ⁿ et n! sont condamnés.
• Pour analyser des boucles : la somme prend le terme dominant, le produit des boucles imbriquées se multiplie. Arrondir le nombre d'itérations vers le haut donne toujours une borne correcte.
• Les logarithmes surgissent dès qu'on divise ou double à répétition (recherche dichotomique, hauteur d'arbre, diviser pour régner) ; leur base est sans importance, et un gain algorithmique écrase n'importe quel gain matériel.