Le coût d’un algorithme

Compter les opérations

La seconde question

Les leçons Concevoir des boucles correctes et Récursivité ont appris à prouver qu’un algorithme est correct : qu’il termine et que son résultat satisfait la postcondition. Or la leçon Algorithmes numériques a montré deux tests de primalité également corrects, l’un avec environ $n$ divisions et l’autre avec environ $\sqrt{n}$, et la leçon Récursivité, deux manières correctes de calculer $F_{30}$, l’une avec $2\,692\,537$ appels et l’autre avec 29 additions. S’il en est ainsi, la correction ne suffit pas pour choisir : entre deux algorithmes corrects, l’un peut répondre en un instant et l’autre ne pas terminer avant que la réponse ait cessé d’importer. La seconde question que l’on pose à un algorithme est donc : combien coûte-t-il ?

On pourrait mesurer le coût avec une horloge, et la quatrième section le fera. Mais le temps d’une exécution dépend de la machine, du compilateur, de ses options et de ce que l’ordinateur fait au même moment ; on n’en tire rien sur l’algorithme sur une autre machine. Ce qui ne dépend de rien de tout cela, c’est le nombre de pas que fait l’algorithme. Il s’ensuit la première décision de cette leçon : mesurer le coût en comptant, et réserver l’horloge à la vérification du compte.

La taille et l’opération dominante

Compter tous les pas (chaque addition, chaque comparaison, chaque incrémentation de l’indice, chaque accès à la mémoire) serait fastidieux et inutile, car presque tous accompagnent un pas principal dans une proportion fixe. On choisit donc l’opération dominante : celle qui s’exécute au moins autant de fois que n’importe quelle autre, à un facteur constant près, et qui pour cette raison les représente toutes. Dans la somme des éléments d’un vecteur, c’est l’addition ; dans la recherche d’un maximum, la comparaison ; dans un test de primalité, la division. Le nombre de fois qu’elle s’exécute s’exprime en fonction de la taille de l’entrée, que l’on appelle $n$ : le nombre d’éléments du vecteur, le nombre que l’on teste, le nombre de chiffres.

Une boucle simple qui parcourt un vecteur de $n$ éléments et fait avec chacun une quantité fixe de travail exécute son opération dominante $n$ fois. Le maximum d’un vecteur non vide, en revanche, commence avec le premier élément comme candidat et compare chacun des autres : $n - 1$ comparaisons. La différence entre $n$ et $n - 1$ est réelle, mais, comme on le verra dans la troisième section, elle ne change rien à ce qui importe.

Le pire cas

Certains algorithmes n’exécutent pas toujours le même nombre d’opérations sur des données de même taille. La recherche d’une valeur dans un vecteur, en le parcourant jusqu’à la trouver, fait une seule comparaison si la valeur est en première position et $n$ si elle n’y est pas. Pour parler de son coût, on choisit l’une des deux situations, et le choix habituel est le pire cas : le nombre maximal d’opérations parmi toutes les entrées de taille $n$. La raison est la même que celle pour laquelle un contrat s’écrit pour toutes les entrées qui satisfont la précondition : le pire cas est une garantie, et le meilleur cas, un espoir. De sorte que la recherche linéaire coûte $n$ comparaisons dans le pire cas, et quand cette leçon dit « le coût » sans plus, elle désigne celui du pire cas.

Boucles imbriquées

La leçon Boucles a appris à compter les itérations de deux boucles imbriquées. Si la boucle intérieure fait toujours $m$ itérations pour chacune des $n$ de la boucle extérieure, le corps intérieur s’exécute $n \cdot m$ fois. Si la boucle intérieure dépend de l’extérieure, on additionne ligne par ligne. Le cas qui apparaît le plus souvent quand on travaille avec des collections est celui de toutes les paires : comparer chaque élément à chacun de ceux qui le suivent, comme lorsqu’on cherche si un vecteur contient des doublons.

#include <print>​int main(){    for (int n{10}; n <= 10'000; n *= 10) {        long long comparisons{0};        for (int i{0}; i < n; ++i) {            for (int j{i + 1}; j < n; ++j) {                ++comparisons;            }        }        std::println("n = {:>6} : {:>10} comparaisons ; n(n - 1)/2 = {}",                     n, comparisons, static_cast<long long>(n) * (n - 1) / 2);    }}

n =     10 :         45 comparaisons ; n(n - 1)/2 = 45n =    100 :       4950 comparaisons ; n(n - 1)/2 = 4950n =   1000 :     499500 comparaisons ; n(n - 1)/2 = 499500n =  10000 :   49995000 comparaisons ; n(n - 1)/2 = 49995000

Le compteur tient la place de la comparaison que ferait l’algorithme réel. À l’itération $i$ de la boucle extérieure, la boucle intérieure va de $i + 1$ à $n - 1$ et fait $n - 1 - i$ itérations ; de sorte que le total est $(n - 1) + (n - 2) + \cdots + 1 + 0$, la somme de la leçon Boucles :

La sortie confirme la formule pour chaque taille. Le compteur est un long long parce qu’à partir d’un $n$ d’environ soixante-cinq mille le nombre de paires dépasse le maximum de int (de 32 bits sur cette plateforme), et la formule multiplie après la conversion pour la même raison : le compteur d’un algorithme quadratique déborde bien avant les données.

On remarquera déjà ce que la troisième section généralisera : quand on multiplie $n$ par 10, les comparaisons sont multipliées par environ 100. Avec dix données, 45 comparaisons ; avec dix mille, presque cinquante millions.