Analyse de complexité

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

expliquer pourquoi on mesure un algorithme en comptant des opérations et non en le chronométrant, énoncer le modèle de coût RAM et dire ce qu'il facture et ce qu'il ignore;
compter exactement le nombre de comparaisons et de décalages d'un algorithme donné, et vérifier votre compte en exécutant le programme;
distinguer le cas favorable, le pire des cas et le cas moyen, et énoncer la loi sur laquelle une moyenne est prise;
écrire et manipuler les définitions formelles de $O$ , $Ω$ , $Θ$ et $o$ , exhiber le couple $(c, n_{0})$ qu'elles demandent, et démontrer une appartenance au lieu de l'affirmer;
utiliser les règles de calcul sur ces classes — transitivité, sommes, produits, comparaison des croissances usuelles — et les justifier;
traduire une classe de croissance en un ordre de grandeur: quelle taille d'entrée reste accessible pour un budget d'opérations donné.

Pourquoi compter plutôt que chronométrer

Le chronomètre ne mesure pas l'algorithme

Au chapitre 10 d'Introduction à la programmation, vous avez chronométré deux programmes qui calculent la même somme, et vous avez constaté que deux exécutions consécutives du même code, sur la même machine, sans rien changer, différaient d'un facteur 2,5. La conclusion tirée là-bas mérite d'être reprise ici comme point de départ: une durée caractérise une exécution, pas un algorithme. Elle dépend du processeur, de la fréquence instantanée, de l'état du cache, du système d'exploitation, du langage, de son interprète, de la version de cet interprète et de ce que la machine faisait par ailleurs.

Ce cours va plus loin, et pour une raison qui lui est propre: les algorithmes que vous lirez ici sont exécutables dans la page, dans le navigateur, sur votre machine. Si nous écrivions «ce tri prend 0,4 seconde», vous pourriez nous contredire en trois clics, et vous auriez raison. Nous ne publierons donc aucune durée en secondes dans ce cours. Nous compterons des opérations, nous dirons lesquelles, et ce décompte-là sera le même chez vous et chez nous, aujourd'hui et dans dix ans.

Compter a un second avantage, plus important encore que la reproductibilité: on peut compter sans exécuter. Un chronomètre répond à la question «combien de temps a-t-il mis?», donc après coup, et sur les données que vous lui avez soumises. Un compte répond à «combien d'opérations fera-t-il, en fonction de la taille de l'entrée?», donc avant d'écrire une ligne, et pour toutes les tailles à la fois. C'est cette seconde question qui décide de l'architecture d'un programme, et c'est celle à laquelle tout ce cours répond.

Le choix de ce qui compte comme «taille» n'est pas anodin et nous y reviendrons au chapitre 11: pour un algorithme de tri, $n$ est le nombre d'éléments, mais pour un algorithme qui factorise un entier, la taille est le nombre de chiffres de cet entier, pas sa valeur. Un algorithme qui met $N$ opérations pour factoriser $N$ est exponentiel en la taille de son entrée, puisque $N = 2^{n}$ quand l'entrée a $n$ bits. Retenez pour l'instant la règle: la taille est la longueur de l'écriture de l'instance, pas la grandeur des nombres qu'elle contient.

Le modèle de coût: la machine RAM

Pour que «nombre d'opérations élémentaires» ait un sens, il faut dire quelles opérations existent et ce qu'elles coûtent. C'est le rôle d'un modèle de coût. Celui que toute l'algorithmique classique utilise s'appelle la machine à accès direct, ou RAM (random access machine).

Deux clauses de cette définition méritent qu'on s'y arrête, parce que ce sont elles qui font du modèle une idéalisation.

La première est l'accès direct à coût constant. Lire la case 0 et lire la case 10 000 000 coûtent la même chose. Une machine réelle n'est pas ainsi faite: elle possède une hiérarchie de mémoires — registres, caches L1, L2, L3, mémoire vive, disque — dont les temps d'accès s'échelonnent sur plusieurs ordres de grandeur. Un parcours séquentiel d'un tableau et un parcours du même tableau dans un ordre aléatoire font exactement le même nombre d'accès et ne coûtent pas du tout la même chose sur une machine réelle. Le modèle RAM ne voit pas cette différence. C'est sa limite la plus connue, et c'est aussi la raison pour laquelle, à coût asymptotique égal, on préfère en pratique un algorithme dont les accès sont contigus.

La seconde est le mot de taille bornée. Sans elle, le modèle serait absurde: en autorisant des entiers arbitrairement grands à coût unitaire, on pourrait multiplier des nombres de milliards de bits en une opération, et coder toute une instance dans un seul mot. La clause « $Θ (lo g n)$ bits par mot» est ce qui empêche cette triche.

Une opération sur un grand entier n'est pas une opération élémentaire

Python manipule les entiers en précision arbitraire: 2 ** 1000 est un nombre parfaitement licite. Ce confort est un piège pour l'analyse de coût, parce que la multiplication de deux entiers de $b$ bits ne coûte pas une unité — elle en coûte au moins de l'ordre de $b$ , et bien davantage pour les méthodes naïves. Un algorithme qui manipule des entiers dont le nombre de chiffres croît avec l'entrée sort donc du modèle RAM tel qu'il est posé ici, et son analyse doit compter des opérations sur les bits, pas sur les nombres. Nous le ferons explicitement au chapitre 2, pour la multiplication de Karatsuba. Partout ailleurs dans ce cours, les valeurs manipulées tiennent dans un mot, et l'hypothèse de coût unitaire est honnête.

Le modèle RAM ne prétend pas décrire une machine réelle. Il prétend seulement que les conclusions qu'on en tire — celui-ci est meilleur que celui-là, à partir d'une certaine taille — survivent au passage sur une vraie machine. Cette prétention est vérifiée depuis soixante ans, à ceci près que les constantes cachées et les effets de cache décident de tout sur les petites tailles. Le modèle est un instrument de conception, pas de prédiction au dixième près.

Question 1.1

Dans le modèle RAM tel qu'il est posé ci-dessus, laquelle de ces affirmations est fausse?

Quelle opération compter?

Le coût total additionne des opérations de natures différentes, et il serait pénible de toutes les suivre. L'usage est d'en choisir une, celle qui domine, et de compter celle-là: on l'appelle l'opération barométrique.

Pour un algorithme de tri ou de recherche, c'est la comparaison entre deux éléments, parce que c'est elle qui fait le travail et parce que, sur des objets réels — deux chaînes de caractères, deux dates, deux enregistrements —, elle est de loin l'opération la plus chère. Pour un algorithme de graphe, ce sera le nombre d'arêtes examinées; pour une structure de données, le nombre d'accès mémoire; pour union-find au chapitre 8, le nombre d'opérations union et find. Le choix est légitime tant que le coût total reste proportionnel, à une constante près, au nombre d'opérations barométriques.

Convention du cours: chaque fois que nous annonçons un coût, nous disons de quoi il est le nombre. «Ce tri est en $O (n lo g n)$ » sans préciser est une phrase incomplète; «ce tri fait $O (n lo g n)$ comparaisons» est une phrase complète.

Compter, sur deux algorithmes que vous connaissez

Les deux algorithmes de cette section vous sont familiers. C'est précisément pour cela qu'ils conviennent: l'objet du chapitre n'est pas de les découvrir, mais d'apprendre à en extraire un nombre.

La recherche séquentielle

Le problème: étant donné un tableau a de $n$ éléments et une valeur cible, renvoyer un indice $i$ tel que a[i] == cible, ou $- 1$ si la valeur est absente. La méthode: regarder les cases dans l'ordre.

def recherche_sequentielle(a, cible):
    """Renvoie l'indice de cible dans a, ou -1 si elle est absente."""
    for i in range(len(a)):
        if a[i] == cible:
            return i
    return -1

L'opération barométrique est la comparaison a[i] == cible, et on la compte en instrumentant la boucle:

def recherche_comptee(a, cible):
    """Meme algorithme, en comptant les comparaisons avec la cible."""
    comparaisons = 0
    for i in range(len(a)):
        comparaisons += 1
        if a[i] == cible:
            return i, comparaisons
    return -1, comparaisons

Le compteur est incrémenté avant le test, parce que la comparaison a lieu que le test réussisse ou non; placé après, il oublierait la comparaison décisive et donnerait systématiquement un de moins.

Tout ce cours utilise le même tableau témoin, a = [38, 27, 43, 3, 9, 82, 10], dont la version triée est [3, 9, 10, 27, 38, 43, 82]. Ces sept nombres sont fictifs; ils n'ont d'autre vertu que d'être toujours les mêmes, d'un chapitre à l'autre, pour que vous puissiez comparer les traces.

Exemple 1.1 · La recherche séquentielle sur le tableau témoin

a = [38, 27, 43, 3, 9, 82, 10]
for cible in [38, 3, 10, 100]:
    print(cible, recherche_comptee(a, cible))

38 (0, 1)
3 (3, 4)
10 (6, 7)
100 (-1, 7)

Quatre lignes, et toute l'analyse y est. La cible 38 est en tête: une comparaison. La cible 3 est à l'indice 3: comparaisons, soit l'indice plus un. La cible 10 est en dernier, la cible 100 est absente: comparaisons dans les deux cas, c'est-à-dire .

Le tri par insertion

Second algorithme: celui du joueur de cartes qui range sa main. On prend les éléments un par un, de gauche à droite, et on insère chacun à sa place dans la partie déjà triée, en décalant vers la droite tous ceux qui lui sont supérieurs.

def tri_insertion(a):
    """Trie une copie de a en inserant chaque element a sa place."""
    t = list(a)
    for i in range(1, len(t)):
        valeur = t[i]
        j = i - 1
        while j >= 0 and t[j] > valeur:
            t[j + 1] = t[j]          # decalage vers la droite
            j -=

Deux opérations méritent d'être comptées, et elles ne racontent pas la même histoire: les comparaisons t[j] > valeur et les décalages t[j + 1] = t[j]. La version instrumentée remplace le and court-circuité par une boucle avec break, uniquement pour pouvoir incrémenter le compteur juste avant la comparaison; l'algorithme est inchangé.

def tri_insertion_compte(a):
    """Meme tri, en comptant les comparaisons et les decalages."""
    t = list(a)
    comparaisons = 0
    decalages = 0
    for i in range(1, len(t)):
        valeur = t[i]
        j = i - 1
        while j >= 0:
            comparaisons += 1
            if t[j]

Exemple 1.2 · Le tri par insertion du tableau témoin, passe par passe

Faisons afficher l'état du tableau et les deux compteurs après chacune des six passes.

a = [38, 27, 43, 3, 9, 82, 10]
t = list(a)
total_c = total_d = 0
for i in range(1, len(t)):
    valeur

Un compte est instructif; une formule l'est davantage. À la passe $i$ , le nombre de décalages $d_{i}$ vaut le nombre d'éléments de t[0:i] strictement supérieurs à t[i], donc $0 \leq d_{i} \leq i$ . Le nombre de comparaisons vaut $d_{i} + 1$ lorsque la boucle s'arrête sur un élément inférieur ou égal, et lorsqu'elle sort par la gauche. D'où l'encadrement, valable pour tout tableau de éléments deux à deux distincts:

n - 1 \leq C (n) \leq i = 1 \sum n - 1 i = \frac{n ( n - 1 )}{2} . (1.1)

Sur le tableau témoin, $n = 7$ , donc $6 \leq 15 \leq 21$ : les 15 comparaisons mesurées tombent bien dans la fourchette. Les deux bornes sont atteintes — la gauche sur un tableau déjà trié, la droite sur un tableau en ordre strictement décroissant —, ce que le programme confirme:

print(tri_insertion_compte([3, 9, 10, 27, 38, 43, 82])[1:])
print(tri_insertion_compte([82, 43, 38, 27, 10, 9, 3])[1:])

(6, 0)
(21, 21)

Question 1.2

Comptez, ne chronométrez pas. Complétez le tri par insertion pour qu'il trie le tableau témoin et affiche, séparés par une espace, le nombre de comparaisons puis le nombre de décalages. Les deux nombres attendus sont ceux du cours, et ils sont les mêmes sur toutes les machines.

tri_insertion.py

Pire cas, cas moyen, cas favorable

Trois fonctions, pas une

Les deux exemples précédents montrent la même chose: pour une taille $n$ fixée, le coût n'est pas un nombre mais un ensemble de nombres, un par instance. On en extrait trois fonctions.

Le pire des cas est, de loin, la plus utile des trois, et pour trois raisons. Il donne une garantie: quoi qu'il arrive, le coût ne dépassera pas $T_{m a x} (n)$ , ce qu'aucune moyenne ne promet. Il se calcule sans hypothèse sur les données, alors qu'une moyenne exige une loi qu'on ne connaît souvent pas. Et il correspond à ce qui se produit quand les données sont choisies par quelqu'un qui veut vous nuire — situation banale dès qu'un programme est exposé sur un réseau. Un tri quadratique dans le pire des cas et rapide en moyenne devient une faille de disponibilité le jour où un attaquant choisit l'entrée.

Le cas favorable, lui, n'a presque aucune valeur pratique: il suffit d'ajouter au début d'un algorithme quelconque un test «si l'entrée est celle-ci, renvoyer la réponse» pour obtenir un cas favorable en $Θ (1)$ . On le mentionne surtout pour ce qu'il révèle de l'algorithme — le tri par insertion en $n - 1$ comparaisons sur un tableau trié dit qu'il sait exploiter un ordre préexistant, et c'est une vraie qualité.

Les trois cas de la recherche séquentielle

Reprenons le tableau témoin. Le cas favorable est la cible en tête: $T_{m i n} (n) = 1$ . Le pire des cas est la cible en dernier ou absente: $T_{m a x} (n) = n$ . Le cas moyen demande une loi, et c'est ici que tout se joue.

Première loi. La cible est présente, et sa position est uniforme sur ${0, 1, \dots, n - 1}$ . Le coût vaut $i + 1$ si la cible est à l'indice $i$ , donc

\overset{ˉ}{T} (n) = i = 0 \sum n - 1 \frac{1}{n} (i + 1) = \frac{1}{n} \cdot \frac{n ( n + 1 )}{2} = \frac{n + 1}{2} . (1.2)

Pour $n = 7$ , cela fait $4$ comparaisons, ce que le programme confirme exactement: la somme des coûts des sept recherches réussies vaut $1 + 2 + \dots + 7 = 28$ , soit $4, 0$ en moyenne.

Deuxième loi. La cible est absente avec probabilité $q$ , et présente à une position uniforme avec probabilité $1 - q$ . Alors

\overset{ˉ}{T} (n) = q n + (1 - q) \frac{n + 1}{2} . (1.3)

Pour $q = 1/2$ et $n = 7$ , cela donne $3, 5 + 2 = 5, 5$ comparaisons, contre $4$ sous la première loi. Même algorithme, même taille, deux moyennes différentes. Ce n'est pas une contradiction: ce sont deux réponses à deux questions différentes, et seule l'énonciation de la loi permet de savoir laquelle on a posée.

Question 1.3

Un tableau non trié contient 500 éléments. On cherche une valeur absente une fois sur quatre; lorsqu'elle est présente, sa position est uniforme. Combien de comparaisons la recherche séquentielle fait-elle en moyenne?

Le cas moyen du tri par insertion

L'analyse en moyenne du tri par insertion est plus riche, et elle introduit une technique que tout le cours réutilise: décomposer l'espérance en une somme d'espérances élémentaires.

Posons la loi une fois pour toutes: l'entrée est une permutation uniforme de $n$ éléments deux à deux distincts, c'est-à-dire que chacun des $n!$ ordres possibles a la probabilité $1/ n!$ .

Commençons par les décalages. À la passe $i$ , le nombre de décalages $d_{i}$ est le nombre d'indices $j < i$ tels que $t [j] > t [i]$ , c'est-à-dire le nombre de paires en désordre dont $i$ est le second membre. Le total $\sum_{i} d_{i}$ est donc exactement le nombre d' de la permutation. Or pour une paire donnée, la probabilité que les deux éléments soient dans le désordre vaut par symétrie, et il y a paires. Par linéarité de l'espérance — qui ne demande aucune indépendance, et c'est ce qui rend l'argument si commode —,

E [i \sum d_{i}] = (2 n) \cdot \frac{1}{2} = \frac{n ( n - 1 )}{4} . (1.4)

Passons aux comparaisons. La passe $i$ en fait $d_{i} + 1$ , sauf lorsque l'élément remonte jusqu'à l'indice 0, auquel cas elle en fait $d_{i} = i$ . Or l'élément remonte jusqu'au bout exactement lorsque $t [i]$ est le minimum des $i + 1$ premiers éléments, événement de probabilité . D'où

\overset{ˉ}{C} (n) = \frac{n ( n - 1 )}{4} + (n - 1) - i = 1 \sum n - 1 \frac{1}{i + 1} = \frac{n ( n - 1 )}{4} + n - H_{n}, (1.5)

où $H_{n} = 1 + \frac{1}{2} + \dots + \frac{1}{n}$ est le -ième nombre harmonique, rappelé en annexe A.

Exemple 1.3 · La formule du cas moyen, vérifiée par énumération exhaustive

La relation (1.5) se vérifie sans approximation pour les petites tailles: on énumère les $n!$ permutations, on compte, on fait la moyenne exacte en fractions.

from fractions import Fraction
from itertools import permutations


def comparaisons(a):
    t = list(a)
    total = 0
    for i in range(1, len(t)):

La relation (1.5) dit l'essentiel: le terme dominant est $n (n - 1) /4$ , soit la moitié du pire des cas. En moyenne, chaque élément ne remonte que la moitié de la partie déjà triée. Le tri par insertion est donc quadratique en moyenne comme au pire; ce n'est pas un algorithme que la moyenne sauve, contrairement au tri rapide du chapitre 3, dont le pire des cas est quadratique et la moyenne en $Θ (n lo g n)$ .

Question 1.4

Vérifiez la relation (1.5) par énumération exhaustive. Le programme parcourt pour l'instant une seule permutation, celle qui est déjà triée, et affiche donc le cas favorable. Remplacez-la par les 5040 permutations de sept éléments et affichez la moyenne exacte, arrondie à trois décimales.

cas_moyen.py

Question 1.5

Un algorithme a un coût moyen de 100 opérations pour n = 1000 sous l'hypothèse d'une entrée uniforme. Que pouvez-vous en conclure sur une exécution donnée?

Les notations asymptotiques

Pourquoi une notation

Les formules obtenues jusqu'ici — $n$ , $(n + 1) /2$ , $n (n - 1) /4 + n - H_{n}$ — sont exactes, et cette exactitude est un défaut autant qu'une qualité. Elle est encombrante: comparer $n (n - 1) /4 + n - H_{n}$ à demande un calcul, alors que la réponse tient en un mot. Elle est fragile: les constantes dépendent du détail de l'implémentation, du langage et de ce qu'on a décidé de compter. Et elle est trompeuse: elle suggère une précision que le modèle RAM ne possède pas.

Ce qu'on veut retenir d'un coût, c'est sa vitesse de croissance quand $n$ devient grand, à un facteur constant près. Les notations asymptotiques sont l'outil qui dit cela avec rigueur.

Lisez ces quatre lignes comme des phrases, pas comme des formules.

$f \in O (g)$ : « $f$ ne croît pas plus vite que $g$ ». C'est une majoration, valable seulement à partir d'un rang, et seulement à une constante multiplicative près. Les deux quantificateurs existentiels sont l'essentiel: démontrer une appartenance à $O (g)$ , c'est exhiber un couple $(c, n_{0})$ .
$f \in Ω (g)$ : « croît au moins aussi vite que ». C'est la minoration symétrique, et c'est ce qu'on démontre pour établir qu'un problème est difficile — la borne inférieure en des tris par comparaison, au chapitre 3.

Démontrer une appartenance: exhiber le couple

L'explorateur ci-dessous vous fait chercher le couple vous-même. C'est une chasse instructive: la définition ne dit pas comment trouver $(c, n_{0})$ , elle dit seulement qu'il faut en trouver un, et l'expérience de ne pas y arriver pour $c = 3$ vaut mieux qu'un paragraphe d'explication.

Explorateur 1.1 · Trouver vous-même la constante et le seuil

La définition demande un couple: une constante c et un rang n₀ tels que T(n) ≤ c·g(n) pour tout n ≥ n₀. Ici T(n) = 3n² + 10n + 50 et g(n) = n². Déplacez les deux curseurs jusqu'à ce que le verdict passe au vert, puis essayez de faire descendre c: vous buterez sur 3, et aucun seuil n₀ ne sauvera une constante plus petite. Le dernier affichage, le rapport T(n)/n² pour n grand, ne bouge jamais — c'est lui qui explique pourquoi.

Constante c4,0

Seuil n₀14

Verdict

le couple convient

Plus petit n₀ pour ce c

T(n₀)

778

c · n₀²

784

T(40) / 40²

3,28

T(n)/n² quand n grandit

3,00

Question 1.6

Remettez dans l'ordre les étapes d'une démonstration de $T (n) \in O (g (n))$ .

Glissez les éléments pour les mettre dans le bon ordre

Annoncer explicitement le couple

(c, n_{0})

obtenu

Majorer chaque terme de

T (n)

par un multiple de

g (n)

, valable à partir d'un certain rang

Contrôler l'inégalité sur une valeur, par exemple

n = n_{0}

Écrire ce que la définition exige: une constante

c > 0

et un rang

n_{0}

Additionner les majorations pour obtenir une inégalité de la forme

T (n) \leq c g (n)

Question 1.7

Le seuil de l'exemple 1.4, trouvé par le programme plutôt que par le discriminant. Pour c = 4 et T(n) = 3n² + 10n + 50, faites chercher au programme le plus petit entier n à partir duquel T(n) ne dépasse plus 4n², puis affichez-le.

seuil.py

Ce que la notation ne dit pas

Un second malentendu concerne le mot «asymptotique». Les définitions portent sur ce qui se passe à partir d'un rang, et ce rang peut être grand. Deux algorithmes en $Θ (n lo g n)$ et $Θ (n^{2})$ comparaisons ne se départagent que pour $n$ assez grand, et la constante cachée décide du reste: c'est précisément pourquoi les bibliothèques de tri basculent sur un tri par insertion quadratique en dessous d'une trentaine d'éléments. Si $n$ vaut toujours 12 dans votre application, l'analyse asymptotique ne vous apprend rien et il faut mesurer.

L'algèbre des classes

Les définitions sont maniables une fois, pas cinquante. On démontre donc une fois pour toutes les règles de calcul, et on les applique ensuite sans revenir aux quantificateurs.

Transitivité

Démonstration. Supposons $f \in O (g)$ et $g \in O (h)$ . Par définition de la première appartenance, il existe $c_{1} > 0$ et $n_{1} \in N$ tels que

\forall n \geq n_{1}, f (n) \leq c_{1} g (n) .

Par définition de la seconde, il existe $c_{2} > 0$ et $n_{2} \in N$ tels que $g (n) \leq c_{2} h (n)$ pour tout . Posons et , qui est strictement positif comme produit de deux réels strictement positifs. Soit . Les deux inégalités sont alors simultanément disponibles, et comme , multiplier la seconde par en préserve le sens:

f (n) \leq c_{1} g (n) \leq c_{1} (c_{2} h (n)) = c h (n) .

Le couple $(c, n_{0})$ témoigne donc de $f \in O (h)$ . Pour $Ω$ , le même calcul s'écrit avec les inégalités renversées: de $f (n) \geq c_{1} g (n)$ et on tire , la multiplication par préservant encore le sens. Enfin étant l'intersection de et de , sa transitivité découle des deux précédentes.

Deux détails de cette démonstration sont à retenir parce qu'ils reviendront: on prend le maximum des deux rangs, parce qu'une propriété valable à partir de $n_{1}$ et une autre à partir de $n_{2}$ ne sont simultanément disponibles qu'à partir de $max (n_{1}, n_{2})$ ; et on multiplie les constantes, ce qui est licite . Une «constante» nulle ou négative casserait tout, et c'est pourquoi la définition exige .

Les règles que l'on utilise vraiment

Les propriétés suivantes se démontrent toutes sur le modèle ci-dessus, en exhibant le couple. Elles sont énoncées pour $O$ ; les versions $Ω$ et $Θ$ sont identiques.

Règle	Énoncé	Ce qu'elle sert à faire
Réflexivité	$f \in Θ (f)$	point de départ
Constante	$λ f \in Θ (f)$ pour $λ > 0$	oublier les facteurs constants
Somme	si $f_{1} \in O (g_{1})$ et , alors

La règle du maximum est celle qui fait tout le travail au quotidien: elle autorise à jeter les termes de moindre ordre. Elle se lit sur un exemple: $3 n^{2} + 10 n + 50 \in Θ (n^{2})$ parce que, pour $n$ grand, $10 n + 50$ est négligeable devant $3 n^{2}$ . La règle du traduit l'imbrication des boucles: une boucle de tours dont le corps coûte coûte .

Un cas particulier mérite d'être isolé parce qu'il justifie une convention du cours entier.

Un polynôme est du degré de son terme dominant

Démonstration. Il faut établir les deux appartenances séparément.

Majoration. Posons $A = ∣ a_{d} ∣ + ∣ a_{d - 1} ∣ + \dots + ∣ a_{0} ∣$ , qui est strictement positif puisque . Pour tout et tout , on a , donc

p (n) \leq i = 0 \sum d ∣ a_{i} ∣ n^{i} \leq (i = 0 \sum d ∣ a_{i} ∣) n^{d} = A n^{d} .

Le couple $(A, 1)$ témoigne de $p \in O (n^{d})$ .

Minoration. Posons $B = ∣ a_{d - 1} ∣ + \dots + ∣ a_{0} ∣$ , la somme des modules des coefficients autres que le dominant. Pour $n \geq 1$ , chacun des $n^{i}$ avec vérifie , donc

p (n) \geq a_{d} n^{d} - B n^{d - 1} = n^{d} (a_{d} - \frac{B}{n}) .

Choisissons $n_{0} = max (1, ⌈ 2 B / a_{d} ⌉)$ . Pour $n \geq n_{0}$ , on a $B / n \leq a_{d} /2$ , donc le facteur entre parenthèses vaut au moins , et

p (n) \geq \frac{a _{d}}{2} n^{d} .

Le couple $(a_{d} /2, n_{0})$ témoigne de $p \in Ω (n^{d})$ . Les deux appartenances donnent $p \in Θ (n^{d})$ .

Appliquons la démonstration à $T (n) = 3 n^{2} + 10 n + 50$ . La majoration fournit $A = 63$ et $n_{0} = 1$ : c'est le couple brutal de l'exemple 1.4, ce qui n'est pas une coïncidence — l'exemple appliquait la démonstration sans le dire. La minoration fournit , et . Ces constantes sont bien plus lâches que les meilleures possibles; la démonstration ne cherche pas à être serrée, elle cherche à valoir pour tout polynôme.

Deux corollaires immédiats, qu'il est inutile de redémontrer chaque fois: $n^{d} \in o (n^{d + 1})$ pour tout $d$ , et un polynôme de degré $d$ n'appartient jamais à $O (n^{d - 1})$ .

La classe de log(n!)

Le résultat suivant servira au chapitre 3, où la borne inférieure des tris par comparaison s'obtient en comptant les feuilles d'un arbre de décision: il y en a $n!$ , la profondeur d'un arbre binaire à $F$ feuilles vaut au moins $lo g_{2} F$ , et c'est $lo g_{2} (n!)$ qu'il faut alors savoir estimer.

Démonstration. Écrivons $lo g$ pour $lo g_{2}$ et travaillons pour $n \geq 4$ .

Majoration. Chacun des $n$ facteurs de $n! = 1 \times 2 \times \dots \times n$ est au plus $n$ , donc $n! \leq n^{n}$ . Le logarithme étant croissant,

lo g (n!) \leq lo g (n^{n}) = n lo g n .

Le couple $(1, 1)$ témoigne de $lo g (n!) \in O (n lo g n)$ .

Minoration. Ne gardons que la seconde moitié des facteurs. Le produit $n!$ contient tous les entiers de $⌈ n /2 ⌉$ à $n$ , soit au moins $n /2$ facteurs, et chacun d'eux vaut au moins $n /2$ . En jetant tous les autres, qui sont $\geq 1$ , il reste

n! \geq (\frac{n}{2})^{n /2}, donc lo g (n!) \geq \frac{n}{2} lo g \frac{n}{2} = \frac{n}{2} (lo g n - 1) .

Il reste à absorber le $- 1$ . Pour $n \geq 4$ on a $lo g n \geq 2$ , donc $1 \leq \frac{1}{2} lo g n$ et par conséquent . En reportant,

lo g (n!) \geq \frac{n}{2} \cdot \frac{lo g n}{2} = \frac{1}{4} n lo g n .

Le couple $(1/4, 4)$ témoigne de $lo g (n!) \in Ω (n lo g n)$ , et les deux appartenances donnent la conclusion. $□$

Les deux constantes obtenues, $1$ et $1/4$ , encadrent le rapport $lo g_{2} (n!) / (n lo g_{2} n)$ . La formule de Stirling, hors programme ici, dit que ce rapport tend vers 1; on le voit converger lentement:

$n$	$lo g_{2} (n!)$	$n lo g_{2} n$	rapport
10	21,8	33,2	0,656
100	524,8	664,4	0,790
1 000	8 529,4	9 965,8	0,856
1 000 000	18 488 885	19 931 569	0,928

Le rapport reste bien dans $[1/4, 1]$ , comme la démonstration le garantit, et il ne s'approche de 1 que très lentement — un rappel que « $Θ$ » n'est pas «égal».

Question 1.8

Parmi les quatre affirmations suivantes, laquelle est FAUSSE?

Ordres de grandeur

Les classes usuelles, et ce qu'elles coûtent

Presque tous les coûts rencontrés en algorithmique se rangent dans une courte liste de classes. Les voici par croissance strictement croissante — chacune est un $o$ de la suivante:

Θ (1) \subset Θ (lo g n) \subset Θ (n) \subset Θ (n lo g n) \subset Θ (n^{2}) \subset Θ (n^{3}) \subset Θ (2^{n}) \subset Θ (n!)

avec leurs noms: constant, logarithmique, linéaire, quasi-linéaire, quadratique, cubique, exponentiel, factoriel. On appelle polynomial tout coût dans $O (n^{k})$ pour un $k$ fixé; la frontière entre le polynomial et l'exponentiel est celle du chapitre 11, et elle est la plus importante de la discipline.

La figure 1.3 dit tout en une image, mais un tableau de nombres est plus facile à citer. Le voici, calculé avec $lo g_{2}$ , et il sera repris tel quel dans les chapitres suivants:

$n$	$n lo g_{2} n$	$n^{2}$	rapport $n^{2} / (n lo g_{2} n)$

Lisez la dernière colonne: à cent éléments, remplacer un algorithme quadratique par un algorithme quasi-linéaire fait gagner un facteur 15 — appréciable, pas décisif. À un million d'éléments, le facteur est de 50 000. Le gain d'un meilleur algorithme n'est pas un pourcentage, c'est un facteur qui croît avec les données; et c'est pourquoi il ne peut pas être compensé par une machine plus rapide.

La comparaison symétrique vaut d'être faite pour le logarithme. La recherche dichotomique dans un tableau trié examine au plus $⌊ lo g_{2} n ⌋ + 1$ éléments: 10 comparaisons pour mille éléments, 20 pour un million, 30 pour un milliard. Multiplier les données par mille ajoute dix comparaisons. Un coût logarithmique est, à l'échelle de ce que les machines traitent, pratiquement gratuit.

Quelle taille reste accessible?

L'autre manière de lire les classes est de fixer un budget d'opérations et de demander quelle taille d'entrée il permet d'atteindre. Prenons un budget d'un milliard d'opérations élémentaires — un ordre de grandeur raisonnable pour un calcul qu'on accepte d'attendre.

Classe	Nom	Taille maximale $n$ pour $1 0^{9}$ opérations
$lo g_{2} n$	logarithmique	pratiquement illimitée
$n$	linéaire	$1 0^{9}$
$n lo g_{2} n$

Ces sept lignes forment le tableau le plus utile du chapitre, et elles se calculent en trois lignes de Python plutôt que de se retenir par cœur. Observez leur enseignement principal: la frontière du praticable ne se déplace pas par petits pas. Entre le quasi-linéaire et le quadratique, elle passe de quarante millions à trente mille; entre le cubique et l'exponentiel, de mille à vingt-neuf. Un problème pour lequel on ne connaît qu'un algorithme exponentiel n'est pas «un peu plus lent»: il est hors de portée dès la trentaine d'objets, et le restera quelle que soit la machine — doubler la vitesse de la machine fait gagner un élément sur une entrée traitée en $2^{n}$ .

Question 1.9

Un programme quadratique traite 1000 enregistrements en 4 millions d'opérations. Combien d'opérations, en millions, lui faudra-t-il pour 25 000 enregistrements?

Coût amorti: une première rencontre

Le tableau qui double

Il reste une troisième manière de dire ce que coûte un algorithme, et c'est celle que ce chapitre se contente d'annoncer. Prenons l'exemple canonique, le tableau dynamique — la list de Python, le vector de C++, l'ArrayList de Java.

Un tableau occupe en mémoire un bloc contigu d'une certaine capacité. Tant qu'il reste de la place, ajouter un élément à la fin coûte une écriture, donc $Θ (1)$ . Quand le bloc est plein, il faut en allouer un plus grand et y recopier tout le contenu: cette insertion-là coûte $Θ (taille)$ . La stratégie universellement retenue est de doubler la capacité à chaque débordement.

def insertions(n):
    """Simule n ajouts en fin de tableau et compte les ecritures elementaires."""
    capacite, taille = 1, 0
    recopies, ecritures = 0, 0
    for _ in range(n):
        if taille == capacite:
            recopies += taille          # tout le contenu est recopie
            ecritures += taille
            capacite *= 2
        ecritures += 1                  # l'ajout lui-meme
        taille +=

for n in [16, 17, 1000, 1000000]:
    recopies, ecritures, capacite = insertions(n)
    print(f"n = {n:>7} : {recopies:>7} recopies, {ecritures:>8} ecritures, "
          f"capacite {capacite:>7}, cout moyen par ajout {ecritures / n:.3f

n =      16 :      15 recopies,       31 ecritures, capacite      16, cout moyen par ajout 1.938
n =      17 :      31 recopies,       48 ecritures, capacite      32, cout moyen par ajout 2.824
n =    1000 :    1023 recopies,     2023 ecritures, capacite    1024, cout moyen par ajout 2.023
n = 1000000 : 1048575 recopies,  2048575 ecritures, capacite 1048576, cout moyen par ajout 2.049

Le nombre moyen d'écritures par ajout reste inférieur à 3, quelle que soit la valeur de $n$ . L'argument est court: sur une suite de $n$ ajouts, les recopies ont lieu aux tailles $1, 2, 4, \dots, 2^{k}$ avec $2^{k} < n$ , et leur total vaut

1 + 2 + 4 + \dots + 2^{k} = 2^{k + 1} - 1 < 2 n . (1.6)

En ajoutant les $n$ écritures des ajouts eux-mêmes, on obtient moins de $3 n$ écritures pour $n$ ajouts. Une suite de $n$ ajouts coûte donc $Θ (n)$ , et non $Θ (n^{2})$ comme le laisserait craindre un pire cas par opération en $Θ (n)$ .

Amorti n'est pas moyen

La confusion est classique et elle est grave, parce que les deux notions n'offrent pas les mêmes garanties.

Le coût moyen est une espérance prise sur une loi de probabilité des entrées. Il ne promet rien sur une exécution donnée, et il ne vous concerne que si vos données suivent la loi supposée.
Le coût amorti est un résultat de pire des cas, sans aucune probabilité. Il porte sur une suite d'opérations et affirme que leur coût total est borné, quelle que soit la suite — y compris celle que choisirait un adversaire.

Le tableau dynamique illustre l'écart: son ajout coûte $Θ (n)$ dans le pire des cas pour une opération isolée, $Θ (1)$ amorti sur une suite d'ajouts, et ce second énoncé n'invoque aucune loi. Dites donc «amorti» quand c'est amorti, et «en moyenne» quand c'est une espérance; ce cours ne mélange jamais les deux.

Une précision pour finir, parce qu'elle explique pourquoi on double au lieu d'agrandir d'une constante: si l'on augmentait la capacité de 100 cases à chaque débordement, les recopies auraient lieu aux tailles $100, 200, \dots$ et leur total serait de l'ordre de $n^{2} /200$ , donc quadratique. C'est le caractère géométrique de la croissance qui rend la somme (1.6) télescopique et le coût amorti constant. Le chapitre 4 reprendra ce calcul proprement, par la méthode du potentiel, et démontrera l'énoncé que ce chapitre se borne à rendre plausible: l'ajout en fin d'un tableau dynamique a un coût amorti $Θ (1)$ .

Question 1.10

Comptez le prix du doublement. Complétez la simulation pour qu'elle affiche, séparés par une espace, le nombre de recopies et le nombre total d'écritures effectuées par mille ajouts en fin de tableau. Le programme ne compte rien pour l'instant et affiche donc le coût sans recopie.

tableau_doublant.py

Synthèse

Un algorithme se mesure en comptant des opérations, pas en le chronométrant: une durée dépend de la machine, du langage et de l'instant, un décompte ne dépend que de l'algorithme et des données. Le modèle de coût est la machine RAM: coût unitaire pour une opération arithmétique, une comparaison et un accès mémoire à une adresse quelconque, mots de $Θ (lo g n)$ bits. Il ignore la hiérarchie des caches et interdit de facturer une unité pour une opération sur un grand entier.
Le coût d'un algorithme n'est pas une fonction mais trois: $T_{m i n}$ , $T_{m a x}$ et $\overset{ˉ}{T}$ . Sur le tableau témoin , la recherche séquentielle coûte 1, 7 et 4 comparaisons; le tri par insertion en fait , avec , entre les 6 d'un tableau trié et les 21 d'un tableau inversé. Une moyenne est une espérance, donc une : sous la loi uniforme des permutations, le tri par insertion fait comparaisons, soit exactement pour .

Série d'exercices du chapitre 1Exercice 1 sur 5

Question 1.11

Sur quelle entrée de sept éléments distincts le tri par insertion fait-il le plus de comparaisons?

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Exercice 1.1 · Compter deux boucles imbriquées

Déterminez, en fonction de $n$ , le nombre exact d'exécutions de la ligne marquée dans chacun des deux fragments suivants, puis donnez la classe $Θ$ correspondante.

# fragment A
compteur = 0
for i in range(n):
    for j in range(n):
        compteur += 1          # ligne marquee

# fragment B
compteur = 0

Exercice 1.2 · Exhiber le couple

Pour chacune des affirmations suivantes, donnez explicitement un couple $(c, n_{0})$ qui la démontre, ou prouvez qu'aucun couple n'existe.

$4 n^{2} + 7 n + 3 \in O (n^{2})$

Exercice 1.3 · Deux moyennes pour un même algorithme

On cherche une valeur dans un tableau de $n = 100$ éléments par recherche séquentielle. Calculez le nombre moyen de comparaisons sous chacune des trois lois suivantes, puis commentez.

La cible est présente, sa position est uniforme.
La cible est absente une fois sur deux; sinon sa position est uniforme.
La cible est présente, mais sa position suit une loi où l'indice 0 a la probabilité $1/2$ , l'indice 1 la probabilité $1/4$ , l'indice 2 la probabilité $1/8$ , et ainsi de suite (l'indice 99 recevant tout le reste).

Solution

Loi 1. La relation (1.2) donne directement $(n + 1) /2 = 101/2 = 50, 5$ comparaisons.

Exercice 1.4 · Deux tris quadratiques, comparés

Le tri par sélection cherche à chaque passe le minimum du reste et l'échange avec la première case non triée; il fait donc toujours exactement $n (n - 1) /2$ comparaisons, quelle que soit l'entrée. Le tri par insertion en fait entre $n - 1$ et $n (n - 1) /2$ .

Donnez la classe $Θ$ du tri par sélection dans le pire des cas, dans le cas favorable et en moyenne.
Même question pour le tri par insertion.
Les deux tris sont en $Θ (n^{2})$ comparaisons dans le pire des cas. Donnez une raison objective de préférer néanmoins le tri par insertion, et une raison objective de préférer le tri par sélection.

Exercice 1.5 · Une borne inférieure sur le nombre de comparaisons

Cet exercice demande une démonstration complète.

Soit un algorithme qui, à partir d'un tableau a de $n \geq 2$ nombres deux à deux distincts, détermine le maximum, et qui n'a pas d'autre accès aux données que la comparaison de deux éléments. Démontrez que tout tel algorithme effectue au moins $n - 1$ comparaisons dans le pire des cas.

Indication: appelez «perdant» tout élément dont l'algorithme a appris, directement ou par transitivité, qu'il n'est pas le maximum, et regardez ce qu'une comparaison ajoute à cet ensemble.

Solution

Démonstration. Considérons une exécution de l'algorithme sur une entrée de $n$ éléments deux à deux distincts, et disons qu'un élément est perdant dès que l'exécution permet de conclure qu'il n'est pas le maximum.

Pour que l'algorithme soit correct, tous les éléments sauf un doivent être perdants à la fin. En effet, supposons qu'à la fin de l'exécution deux éléments et ne soient pas perdants et que l'algorithme réponde « est le maximum». Puisque n'est pas perdant, rien dans les comparaisons effectuées n'exclut que soit le plus grand: on peut donc modifier les valeurs de l'entrée en gardant les résultats de les comparaisons effectuées et en rendant strictement plus grand que . Sur cette nouvelle entrée, l'algorithme suit exactement le même chemin d'exécution — il n'a vu que les mêmes réponses aux mêmes comparaisons — et répond encore «», ce qui est faux. L'algorithme serait donc incorrect. Il faut donc qu'à la fin il y ait au plus un élément non perdant, c'est-à-dire .

Références

Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4ᵉ éd., MIT Press — chapitres 2 et 3 pour le modèle RAM, l'analyse du tri par insertion et les définitions de $O$ , $Ω$ et $Θ$ ; l'annexe A pour les sommes usuelles.
Cormen, Leiserson, Rivest & Stein, Algorithmique, 3ᵉ éd., Dunod — la traduction française des mêmes chapitres, utile pour fixer le vocabulaire en français.
Sedgewick & Wayne, Algorithms, 4ᵉ éd., Addison-Wesley — section 1.4, «Analysis of Algorithms», pour l'approche empirique et la notion d'ordre de croissance illustrée par des mesures.
Kleinberg & Tardos, Algorithm Design, Pearson — chapitre 2, en particulier la discussion de ce que «temps polynomial» veut dire et la table des tailles praticables.
Dasgupta, Papadimitriou & Vazirani, Algorithms, McGraw-Hill — chapitre 0, une introduction courte et très claire aux notations asymptotiques et à leurs pièges.
Beauquier, Berstel & Chrétienne, Éléments d'algorithmique, Masson — pour les analyses en moyenne détaillées, avec le dénombrement des inversions d'une permutation.

Passe $i$	Valeur insérée	Comparaisons	Décalages	Tableau après la passe
1	27	1	1	27, 38, 43, 3, 9, 82, 10
2	43	1	0	27, 38, 43, 3, 9, 82, 10
3	3	3	3	3, 27, 38, 43, 9, 82, 10
4	9	4	3	3, 9, 27, 38, 43, 82, 10
5	82	1	0	3, 9, 27, 38, 43, 82, 10
6	10	5	4	3, 9, 10, 27, 38, 43, 82
total		15	11

Objectifs du chapitre

Pourquoi compter plutôt que chronométrer

Le chronomètre ne mesure pas l'algorithme

Le modèle de coût: la machine RAM

Quelle opération compter?

Compter, sur deux algorithmes que vous connaissez

La recherche séquentielle

Le tri par insertion

Pire cas, cas moyen, cas favorable

Trois fonctions, pas une

Les trois cas de la recherche séquentielle

Le cas moyen du tri par insertion

Les notations asymptotiques

Pourquoi une notation

Démontrer une appartenance: exhiber le couple

Ce que la notation ne dit pas

L'algèbre des classes

Transitivité

Les règles que l'on utilise vraiment

Un polynôme est du degré de son terme dominant

La classe de log(n!)

Ordres de grandeur

Les classes usuelles, et ce qu'elles coûtent

Quelle taille reste accessible?

Coût amorti: une première rencontre

Le tableau qui double

Synthèse

Exercices

Références

Le pire des cas

La classe, et le couple qui la justifie

Le cas favorable

Combien de temps un meilleur algorithme fait-il gagner?

100	664	10 000	15
1 000	9 966	1 000 000	100
10 000	132 877	100 000 000	753
1 000 000	19 931 569	$1 0^{12}$	50 172