L'analyse asymptotique

Tout le cours repose sur une seule phrase, et elle est étrange la première fois qu'on la lit : on mesure la vitesse d'un algorithme sans jamais le faire tourner. Pas de chronomètre, pas de machine, pas même de langage — on compte, et on regarde ce que ce compte devient quand l'entrée grossit.

Pourquoi le chronomètre ment

Commençons par la scène qui rend tout le reste nécessaire. Tu écris deux versions d'un programme qui trie une liste. Tu les lances sur ta machine, avec mille nombres : les deux répondent en moins d'une seconde. Laquelle est la meilleure ?

La question paraît simple et elle est piégée, parce que le chronomètre ne mesure pas ce que tu crois. Il mesure ton algorithme plus la fréquence de ton processeur, plus la quantité de mémoire libre, plus les optimisations que ton compilateur a bien voulu appliquer, plus ce que le système d'exploitation faisait pendant ce temps, plus l'entrée précise que tu as choisie. Change n'importe lequel de ces six termes et le verdict change. Deux personnes qui mesurent le même algorithme n'obtiennent pas le même résultat, et aucune des deux n'a tort.

Il faut donc une mesure qui ne dépende que de l'algorithme. On en connaît une : le nombre d'opérations élémentaires — comparaisons, affectations, additions — qu'il effectue en fonction de la taille de son entrée. On note cette quantité T(n), où n est la taille de l'entrée. Elle se compte à la main, sur le papier, sans allumer quoi que ce soit.

Reste à se convaincre que cet écart n'est pas théorique. Prenons deux tris, l'un en n² opérations, l'autre en n log n, et supposons qu'une opération coûte une microseconde :

Sur un million d'éléments, l'un rend sa réponse pendant que tu prends un café, l'autre pendant que tu prends des vacances. Et voici ce qu'il faut vraiment retenir de ce tableau : un superordinateur cent fois plus rapide ne sauve pas le premier. Onze jours divisés par cent font encore près de trois heures. Le choix de l'algorithme bat le choix de la machine, et il le bat de si loin que la comparaison n'a même pas de sens.

Une dernière précision de vocabulaire, parce qu'elle revient à chaque ligne du cours. T(n) dépend encore de détails sans intérêt — le nombre exact d'affectations, la façon dont on a écrit la condition. Ce qui nous intéresse est son ordre de croissance : la forme que prend T(n) quand n grandit, une fois les constantes mises de côté. Tout le reste du module consiste à donner un langage précis à cette idée floue.

L'opération baromètre

Compter toutes les opérations d'un algorithme est fastidieux, et — c'est le point important — parfaitement inutile. Regarde une boucle : si une instruction du corps s'exécute n² fois, ses voisines aussi. Elles montent et descendent ensemble. En compter une seule suffit donc à connaître l'ordre de croissance de toutes.

C'est exactement l'idée de l'opération baromètre : une opération de l'algorithme exécutée au moins aussi souvent que toutes les autres. Compter ses exécutions suffit à déterminer l'ordre de croissance de T(n). Le nom est bien choisi — un baromètre ne mesure pas le temps qu'il fait, il en donne une indication fidèle.

Comment le choisir ? Trois réflexes, dans cet ordre. L'instruction la plus profondément imbriquée dans les boucles est presque toujours le bon candidat. Si plusieurs se présentent, on garde celle qui s'exécute le plus souvent — les autres seront dominées de toute façon. Et pour un algorithme de tri ou de recherche, c'est typiquement la comparaison ou l'affectation.

Le code ci-dessous n'est là que pour ça : montrer où tombe le baromètre dans le cas le plus fréquent du cours, deux boucles imbriquées. Lis les commentaires avant le code — ce sont eux qui portent le raisonnement.

int somme = 0;

for (int i = 0; i < n; i++) {          // la boucle externe tourne n fois
  for (int j = 0; j < n; j++) {        // et pour CHACUN de ces n tours, n fois encore
    somme += tableau[i][j];            // ← le BAROMÈTRE : n × n exécutions
  }
}

Les comparaisons i < n et j < n sont elles aussi en Θ(n²) — on n'annonce qu'une seule opération baromètre, la plus interne.

Vérifie-le à la main, c'est le seul moyen d'y croire vraiment. Pour n = 3, les couples (i, j) parcourus sont (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2). Le baromètre s'exécute neuf fois, soit 3 × 3. Cette vérification sur une petite valeur est le réflexe le plus rentable de tout le cours : elle attrape la moitié des erreurs de comptage.

for (int i = 0; i < n; i++) {
  std::cout << "Bonjour ";        // (a)
  for (int j = 0; j < 10; j++)
    std::cout << j;               // (b)
}

Pire cas, meilleur cas, cas moyen

Un même algorithme, sur deux entrées de même taille, peut se comporter très différemment. Cherche une valeur dans une liste de mille entiers, en les parcourant un par un. Si elle est en première position, une comparaison suffit. Si elle est en dernière — ou absente —, il en faut mille. Si elle est au milieu, environ cinq cents.

Trois nombres pour un seul algorithme et une seule taille d'entrée. Lequel annonce-t-on ? La réponse honnête est : cela dépend de ce qu'on veut garantir. D'où trois mesures distinctes, et pas une hiérarchie entre elles.

Sur la recherche linéaire, cela donne : meilleur cas Θ(1) — la valeur est en tête ; pire cas Θ(n) — elle est en queue ou absente ; cas moyen Θ(n) — si elle est présente et uniformément répartie, on s'arrête en moyenne à la position (n + 1)/2, donc après environ n/2 comparaisons. Le meilleur cas est spectaculaire et parfaitement trompeur : en pratique, cet algorithme est linéaire, parce que deux de ses trois mesures le sont.

Le choix entre pire et moyen n'est pas mathématique, il est contextuel — et c'est précisément ce que l'examen aime demander. Un détecteur de fuite de gaz doit déclencher son alarme avant un délai fixé dans tous les cas : on exige une garantie de pire cas, même si le cas moyen est dix fois meilleur. Un tri sur une page web peut au contraire accepter un excellent cas moyen au prix d'un pire cas occasionnellement lent : personne ne remarquera la fois sur mille.

O, Ω, Θ : le plafond et le plancher

Tu sais maintenant compter, et tu obtiens des choses comme T(n) = 3n² + 5n + 17. C'est précis ; c'est trop précis. Les trois constantes viennent de la machine et de la façon dont tu as écrit le code — elles ne disent rien sur l'algorithme. Ce qui reste vrai partout, c'est « ça grandit comme n² ». Les trois notations asymptotiques existent pour dire exactement cela, et rien de plus.

Avant les formules, l'intuition en français. Dire que f appartient à O(g), c'est dire qu'à partir d'une certaine taille, f reste sous un multiple constant de g. Ω renverse l'inégalité : f reste au-dessus. Θ enferme f entre deux multiples de g. Le membre de phrase « à partir d'une certaine taille » n'est pas une précaution de style : c'est lui qui autorise à ignorer les petites valeurs de n, et c'est le mot asymptotique qui le porte.

Voici les trois définitions telles que l'examen les demande. Elles se ressemblent beaucoup, et c'est volontaire — seul le sens de l'inégalité change.

O (grand O) — la borne supérieure. On dit que f(n) appartient à O(g(n)) s'il existe deux constantes positives c et n₀ telles que :

La virgule se lit « pour tout » : l'inégalité n'est exigée qu'à partir du seuil, jamais avant.

Ω (grand oméga) — la borne inférieure. Mêmes constantes, même seuil, et une seule chose change — le sens de l'inégalité :

Θ (grand thêta) — l'encadrement. Il faut cette fois trois constantes positives — deux multiplicateurs et toujours un seuil — telles que, à partir de ce seuil :

Décortiquons, parce que ces quatre symboles reviendront à chaque démonstration du cours. f est ta fonction réelle, celle que tu as comptée — 3n² + 5n + 17. g est la fonction simple à laquelle tu la compares — n². La constante c est le droit d'agrandir g autant qu'il faut : c'est elle qui matérialise « on ignore les constantes ». Et n₀ est un seuil : en dessous, l'inégalité a le droit d'être fausse. L'inégalité complète dit donc, littéralement : passé un certain point, f reste sous une copie agrandie de g.

Un exemple complet, du genre qu'on demande de rédiger. Montrons que 3n² + 5n + 17 est dans O(n²). Il faut exhiber un c et un n₀. Pour n ≥ 4, on a 5n + 17 qui reste sous n² ; donc 3n² + 5n + 17 reste sous 3n² + n² = 4n². Le couple c = 4, n₀ = 4 convient. On n'a pas à trouver le meilleur couple — n'importe lequel qui marche suffit à établir l'appartenance.

Enfin, la relation entre les trois, qui explique pourquoi Θ est la mesure qu'on préfère quand on la connaît : f est dans Θ(g) si et seulement si elle est à la fois dans O(g) et dans Ω(g). Θ dit « au plus » et « au moins » dans la même phrase.

Il reste une question pratique : exhiber c et n₀ à la main est parfois pénible. Il existe un raccourci, et le cours l'accepte comme démonstration : étudier la limite du rapport des deux fonctions.

Appliqué à 3n² + 5n contre n², le rapport vaut 3 + 5/n, qui tend vers 3. Comme 3 est strictement entre 0 et l'infini, la conclusion tombe : 3n² + 5n est dans Θ(n²). Trois lignes, aucune constante à deviner.

La hiérarchie des ordres de croissance

Une poignée de fonctions revient sans cesse, et il faut les connaître dans l'ordre, comme on connaît l'ordre des opérations. Du plus rapide au plus lent : constante, logarithmique, racine, linéaire, linéarithmique, quadratique, cubique, exponentielle, factorielle.

La chaîne est coupée en deux lignes qui se recouvrent sur n log n : une formule ne se coupe pas toute seule, et celle-ci ne tiendrait pas sur la largeur d'un téléphone. Le symbole d'inclusion se lit ici « est contenu dans, mais ne remplit pas ». Θ(log n) ⊂ Θ(n) signifie : toute fonction logarithmique est dans O(n), et la réciproque est fausse.

Cette chaîne est facile à réciter et difficile à sentir. Le tableau suivant est là pour ça — mêmes fonctions, une microseconde par opération, et des tailles d'entrée réalistes.

Deux choses à emporter de ce tableau. D'abord, le logarithme est presque une constante : quand n passe de mille à un million, il passe de dix à vingt. Doubler l'entrée n'ajoute qu'une unité. C'est pour cette raison que tout le cours cherchera à transformer des parcours linéaires en descentes d'arbre.

Ensuite, l'exponentielle n'est pas « lente », elle est impossible. À cent éléments, un algorithme en 2ⁿ demande environ quatre cent mille milliards de milliards d'années — trois millions de fois l'âge de l'univers. Le seuil pratique se situe autour de trente : au-delà, il ne s'agit plus d'attendre, il s'agit de changer d'algorithme.

Analyser une boucle en quatre gestes

On arrive à l'exercice le plus fréquent du cours et de l'intra : on te donne une boucle, tu rends un Θ. La bonne nouvelle est qu'il existe une recette, toujours la même, et que les corrigés du cours la suivent à la lettre.

Elle tient en quatre gestes, à faire dans l'ordre. Un : identifier l'opération baromètre — presque toujours l'instruction la plus interne. Deux : compter ses exécutions en fonction de n, en l'écrivant comme une somme. Trois : simplifier cette somme à l'aide du formulaire. Quatre : conclure en notation asymptotique.

// GESTE 1 — le baromètre : l'instruction la plus interne.
// GESTE 2 — le compte : pour i fixé, l'interne tourne i fois.
//           Donc le total s'écrit  somme de i, pour i de 1 à n.
// GESTE 3 — le formulaire : cette somme vaut n(n+1)/2.
// GESTE 4 — la conclusion : n(n+1)/2 est dominé par n², donc Theta(n^2).

for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= i; j++) {
    somme += j;                    // ← le baromètre
  }
}

Avant de compter quoi que ce soit, il y a un réflexe qui répond à lui seul à la moitié des questions : regarder comment l'indice avance. Un incrément additif — i++, i += 2 — donne une boucle linéaire. Un incrément multiplicatif — i *= 2, i /= 2 — donne une boucle logarithmique. C'est la première chose à observer, et c'est presque toujours suffisant pour savoir où l'on va.

La raison se voit mieux qu'elle ne s'explique. La figure ci-dessous met côte à côte les valeurs que chacune des deux boucles visite avant d'atteindre le bout.

Le raisonnement formel derrière la figure tient en une ligne. Si i part de 1 et double à chaque tour, alors après k tours il vaut 2^k. La boucle s'arrête quand 2^k atteint n, c'est-à-dire quand k atteint log₂ n. Le baromètre s'exécute donc environ log₂ n fois.

Voici les patrons qui couvrent la quasi-totalité des questions d'examen. Vaut mieux les reconnaître que les recalculer.

Le geste 4 — conclure — s'appuie sur trois règles qu'il vaut mieux connaître par leur nom, parce que les énoncés d'examen les nomment.

La règle du maximum. Deux morceaux de programme qui se suivent coûtent l'ordre du plus cher des deux : f + g est dans Θ(max(f, g)). Un programme en n² suivi d'un programme en n log n est en Θ(n²) — le second est absorbé. C'est ce qui autorise à jeter tous les termes sauf le dominant, et c'est aussi pourquoi optimiser la partie rapide d'un programme lent ne sert à rien.

La règle multiplicative. Deux boucles imbriquées dont les bornes sont indépendantes coûtent le produit : une externe en f et une interne en g donnent Θ(f·g). Le mot important est indépendantes — dès que la borne interne dépend de l'indice externe, ce n'est plus un produit mais une somme, et c'est tout l'objet de la section suivante.

La transitivité. Si f est dans O(g) et g dans O(h), alors f est dans O(h). Elle paraît anodine et sert tout le temps : c'est elle qui permet d'enchaîner les majorations sans repartir de la définition à chaque étape.

Un cas typique d'examen, qui les combine. Un programme fait une préparation en O(n), puis une boucle de n tours dont le corps est en O(log n). La boucle coûte O(n log n) par la règle multiplicative ; le total est O(n) + O(n log n), que la règle du maximum ramène à O(n log n). La préparation a disparu, et c'est correct.

int i = n;
while (i > 0) { i = i - 2; }      // (a)

int j = n;
while (j > 0) { j = j / 2; }      // (b)

int i = 1;
while (i <= n) {
  int j = 1;
  while (j <= i) {
    j = j + 1;
  }
  i = 2 * i;
}

Les sommes qu'on recroise

Le geste 2 produit presque toujours une somme, et le geste 3 consiste à la reconnaître. Il n'y en a qu'une poignée, elles sont sur le formulaire officiel — celui qu'on a le droit d'écrire sur sa feuille manuscrite —, et c'est un investissement rentable que de savoir laquelle sert quand.

La plus fréquente de toutes est la somme des n premiers entiers, qu'on appelle somme de Gauss.

Elle se retrouve en dix secondes si on l'oublie, et la manière de la retrouver mérite d'être connue pour elle-même : on écrit la somme deux fois, une fois dans un sens, une fois dans l'autre, et on les additionne colonne par colonne.

Vérifie sur les nombres de la figure : la somme de 1 à 6 vaut 21, et la formule donne 6 × 7/2, soit 21. Cette vérification numérique sur une petite valeur est à faire systématiquement en examen — elle ne coûte rien et elle attrape les erreurs de recopie.

Les autres sommes du formulaire, dans l'ordre où on les rencontre :

Quatre de ces lignes portent un nom, et les énoncés d'examen les emploient sans les expliquer. Une somme est arithmétique quand chaque terme s'obtient en ajoutant toujours la même raison au précédent — c'est le cas d'une boucle à incrément constant. Elle est géométrique quand on multiplie par une raison constante — c'est le cas d'une boucle qui double. Et la harmonique, la somme des inverses, est celle qui surprend : elle a l'air de converger et elle n'en fait rien, elle croît comme un logarithme. On la rencontre dès qu'on analyse un algorithme en moyenne.

La série géométrique mérite un mot de plus, parce qu'elle est la plus contre-intuitive. 1 + 2 + 4 + 8 + 16 fait 31, soit 2⁵ − 1. Autrement dit : la somme de toutes les puissances de deux jusqu'à un rang donné est à peine plus grande que la dernière d'entre elles. C'est exactement ce qui explique le corrigé surprenant de l'exercice précédent, et c'est un fait qu'on réutilisera pour analyser les arbres et les monceaux.

Stirling, et le logarithme du factoriel

La factorielle apparaît plus souvent qu'on ne le croit — dès qu'on énumère des permutations, dès qu'on compte des arrangements, et dès qu'on additionne des logarithmes. Le problème est qu'elle ne ressemble à aucune des fonctions de la hiérarchie : on ne sait pas quoi en faire tant qu'on ne l'a pas traduite. C'est le rôle de la formule de Stirling.

Lue symbole par symbole : la racine est un petit facteur correctif, qui ne croît que comme la racine de n et deviendra négligeable ; le second facteur est le terme dominant, n divisé par e, le tout élevé à la puissance n. On voit déjà pourquoi la factorielle explose : c'est une puissance dont la base et l'exposant grandissent tous les deux.

Mais ce n'est pas n! qu'on rencontre dans une analyse de boucle — c'est son logarithme. Une boucle externe linéaire dont l'interne est logarithmique donne la somme des log i, et une somme de logarithmes est le logarithme d'un produit : log 1 + log 2 + … + log n n'est rien d'autre que log(n!). Applique le logarithme à la formule ci-dessus : le facteur correctif devient un terme en log n, négligeable, et le terme dominant devient n log n − n log e. Il reste :

C'est le résultat à retenir de Stirling pour ce cours. Tout le reste de la formule ne sert qu'à l'établir. Dès que ton comptage aboutit à log(n!), tu écris Θ(n log n) et tu passes à la suite.

int i = 1;
while (i <= n) {
  int j = 1;
  while (j < i) {
    j = 2 * j;
  }
  i = i + 1;
}

Deux familles de propriétés accompagnent Stirling et servent tout le temps. Pour les logarithmes : le log d'un produit est la somme des logs, le log d'un quotient est leur différence, le log d'une puissance fait descendre l'exposant en facteur, et le changement de base se fait par multiplication par une constante. Cette dernière propriété a une conséquence directe : en notation asymptotique, la base du logarithme n'a aucune importance — log₂ n et log₁₀ n ne diffèrent que d'un facteur constant, donc appartiennent au même Θ. C'est pourquoi on écrit simplement log n, sans préciser la base.

Pour les exponentielles, qui sont l'exacte réciproque : additionner les exposants revient à multiplier les puissances, multiplier les exposants revient à empiler les puissances, et soustraire revient à diviser. La quatrième identité est celle qu'on oublie et qui débloque la moitié des démonstrations — b s'écrit toujours a élevé au logarithme de b en base a. C'est elle qui permet de passer d'une écriture exponentielle à une écriture logarithmique quand on est coincé.

Pour les parties entières, qui apparaissent dès qu'une boucle divise par deux : la partie entière par défaut de x est le plus grand entier qui ne le dépasse pas, celle par excès est le plus petit qui l'atteint, et les deux encadrent toujours x à moins d'une unité près. Deux identités reviennent souvent : la somme des deux moitiés entières de n redonne n exactement, et le nombre de bits nécessaires pour écrire n est la partie entière par défaut de log₂ n, plus un. En notation asymptotique, on les efface : elles ne changent le compte que d'une unité.

Quand les constantes gagnent

Le module se termine sur son propre garde-fou, parce qu'un outil dont on ne connaît pas les limites finit par se retourner contre celui qui s'en sert. L'analyse asymptotique ignore les constantes — c'est sa force, et c'est aussi la seule chose qu'on peut lui reprocher.

Regarde ces deux fonctions, tirées d'un exercice du cours. La première est linéaire mais traîne trois boucles imbriquées bornées par des constantes ; la seconde est quadratique et ne fait presque rien à chaque tour.

void a(int n) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 100; j++)          // 100 : une CONSTANTE
      for (int k = 0; k < 300; k++)        // 300 : une constante aussi
        std::cout << "abcde\n";           // ← 30 000 × n exécutions
  }
}

void b(int n) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)            // bornée par i : somme triangulaire
      std::cout << "12345\n";             // ← n(n − 1)/2 exécutions
}

Deux boucles imbriquées ne donnent pas toujours Θ(n²) — tout dépend de ce qui borne la boucle interne, une constante ou l'indice externe.

Le compte donne environ 30 000 n pour la première, donc Θ(n), et n(n − 1)/2 pour la seconde, donc Θ(n²). L'analyse asymptotique tranche sans hésiter en faveur de la première. Cherchons maintenant le point où les deux se croisent : en résolvant 30 000 n = n(n − 1)/2, on trouve n aux alentours de soixante mille.

Autrement dit : sur toute entrée plus petite que soixante mille éléments, l'algorithme « moins efficace » est le plus rapide des deux. Et sur beaucoup de problèmes réels, l'entrée ne dépasse jamais soixante mille éléments.

Ce n'est pas une critique de l'analyse asymptotique, c'est son mode d'emploi. Elle répond à la question « lequel tiendra quand ça grossira ? », qui est presque toujours la bonne question — mais pas toujours. Quand tu sais que n restera petit, et que tu connais les constantes, le calcul explicite l'emporte sur la notation. La règle qu'on en tire est simple : le Θ décide de l'algorithme, les constantes décident de son implémentation.