Complexité algorithmique et Green IT

Un quartier équipé d'un réseau électrique intelligent produit des relevés par centaines de milliers. Il faut y repérer deux productions dont la somme couvre exactement une demande, le problème du 2-sum. Écrit naïvement, l'algorithme tourne pendant des heures ; écrit correctement, en une fraction de seconde. Ce chapitre donne l'outil qui permet de prévoir cet écart avant d'écrire le code. Il se termine sur ce qui en fait un enjeu d'ingénieur : du temps de calcul économisé, c'est de l'énergie et du matériel économisés.

Il fait suite aux paradigmes de programmation : on y a vu comment structurer un programme, on regarde ici ce qu'il en coûte.

Mesurer un algorithme, pas un programme

Chronométrer un programme donne un nombre qui dépend de la machine, du langage, de la version de l'interpréteur, de la charge du système et du jeu d'essai. Il suffit de changer l'un de ces facteurs pour que le nombre change.

Ce qu'on cherche

Non pas « combien de temps ça prend », mais « comment le temps grandit quand les données grandissent ». Cette question-là a une réponse indépendante de la machine, et c'est la seule qui permette de décider avant d'avoir écrit le code.

Opération élémentaire et fonction de coût

Définition

Une opération élémentaire est une opération dont le coût ne dépend pas de la taille de l'entrée : une comparaison, une affectation, une addition, un accès à une case de tableau.

La fonction de coût $T(n)$ est le nombre d'opérations élémentaires effectuées sur une entrée de taille $n$ .

Compter, sur un exemple. Rechercher une valeur dans une liste non triée de $n$ éléments, en comptant les comparaisons au passage. L'algorithme est écrit en pseudo-code, la notation du parcours Algorithmique. Le bouton de déroulement exécute l'algorithme ligne par ligne. La seule chose à suivre est la variable comparaisons : elle monte jusqu'à 4 quand la cible est en quatrième position, et jusqu'à $n = 6$ quand elle est absente. C'est ce second nombre, celui de la recherche infructueuse, qui donne le coût à retenir.

Algorithme

pas 1 / 40

Fonction Rechercher(tableau, n, cible)

comparaisons ← 0

Pour i de 1 à n

comparaisons ← comparaisons + 1

Si tableau[i] = cible Alors

Écrire "trouvé en ", comparaisons, " comparaisons"

Retourner i

FinSi

FinPour

Écrire "absent, après ", comparaisons, " comparaisons"

Retourner -1

FinFonction

Début

t ← [42, 17, 8, 23, 4, 15]

Écrire Rechercher(t, 6, 23)

Écrire Rechercher(t, 6, 99)

Fin

programme principal

t[42, 17, 8, 23, 4, 15]

Dans le pire des cas (la valeur est absente) la boucle fait $n$ tours. Le compteur ne retient que les comparaisons de valeur. Chaque tour en coûte deux autres, invisibles dans le code : le test de fin de boucle et l'incrémentation de $i$ . En ajoutant l'initialisation du compteur et le retour final, on obtient $T(n) = 3n + 2$ opérations environ.

Pourquoi on jette les constantes

Le $3$ dépend de ce qu'on décide d'appeler « une opération », et le $+ 2$ devient négligeable dès que $n$ dépasse quelques dizaines. Ce qui survit à tous ces choix arbitraires, c'est que $T$ croît proportionnellement à $n$ . C'est cette information-là qu'on garde, et rien d'autre.

La notation de Landau

Il reste à écrire «  $T$ croît proportionnellement à $n$  » d'une manière qui ne dépende d'aucune convention de comptage. Il faut donc un langage qui compare deux fonctions à un facteur constant près, et seulement pour les grandes valeurs de $n$ . C'est exactement ce que fournit la notation ci-dessous.

Définition

On dit que $u$ est dominée par $v$ , et on note $u(n) = O(v(n))$ , s'il existe un rang $n_0$ et un réel $k > 0$ tels que :

\forall n \geq n_0, \quad |u(n)| \leq k\,|v(n)|

En clair : à partir d'un certain rang $n_0$ , la courbe de $u$ reste sous celle de $v$ agrandie par un facteur fixe $k$ . Les deux paramètres portent chacun une permission : $k$ permet d'ignorer les constantes, $n_0$ permet d'ignorer le début de la courbe.

Ce que la définition écarte, du même coup : elle ne dit rien de $T(10)$ , rien de la machine, et rien du rapport exact entre deux algorithmes de même classe.

Trois notations, et il faut savoir laquelle on emploie :

$O(v)$ , la majoration : « ne croît pas plus vite que ». C'est la plus utilisée, parce qu'on veut garantir un plafond.
$\Omega(v)$ , la minoration : « croît au moins aussi vite que ». C'est celle des bornes inférieures, donc des théorèmes d'impossibilité.
$\Theta(v)$ , l'encadrement : $O(v)$ et $\Omega(v)$ à la fois. C'est la plus précise, et souvent celle qu'on veut vraiment dire.

« Cet algorithme est en O(n²) » peut être vrai et inutile

Un algorithme en $\Theta(n)$ est aussi, formellement, en $O(n^2)$ , et en $O(n^{100})$ . La majoration reste vraie, elle est simplement mauvaise.

Quand on affirme une complexité, dire si c'est une majoration ou un encadrement. Écrire $\Theta$ quand on le sait est plus fort, plus précis, et signale qu'on a compris la différence.

Une preuve, sur l'exemple de la recherche

Il s'agit de montrer que $T(n) = 3n + 2 = O(n)$ , c'est-à-dire de trouver un rang $n_0$ et un facteur $k$ qui conviennent.

Le couple $n_0 = 1$ et $k = 5$ convient. Pour tout $n \geq 1$ on a $2 \leq 2n$ , donc $3n + 2 \leq 3n + 2n = 5n$ .

Donc $\forall n \geq 1, |3n + 2| \leq 5|n|$  : la définition est vérifiée avec $n_0 = 1$ et $k = 5$ . ∎

Le couple $(n_0, k)$ n'est pas unique : n'importe quel $k > 3$ conviendrait, avec un $n_0$ adapté. Exhiber un couple suffit, c'est tout ce que demande la définition.

Les classes usuelles

Complexité	Nom	Exemple typique	Pour mille éléments	Pour un million
$O(1)$	constante	accès à une case de tableau	1	1
$O(\log n)$	logarithmique	recherche dichotomique	10	20
$O(n)$	linéaire	parcours d'une liste	10³	10⁶
$O(n \log n)$	quasi-linéaire	tri par fusion	10⁴	2 × 10⁷
$O(n^2)$	quadratique	double boucle imbriquée	10⁶	10¹²
$O(2^n)$	exponentielle	énumération de tous les sous-ensembles	10³⁰¹	inatteignable

L'ordre des lignes est celui des croissances comparées, vues dans le chapitre sur l'étude de fonction : toute puissance de $n$ l'emporte sur le logarithme, et l'exponentielle l'emporte sur toute puissance.

Le logarithme mérite qu'on s'y arrête, parce qu'il est le seul dont l'origine ne se devine pas. Il vient du fait qu'on coupe en deux : chaque étape écarte la moitié de ce qui reste, et le nombre d'étapes est le nombre de fois qu'on peut diviser $n$ par 2.

Soit un tableau trié de quinze valeurs : 3 8 12 19 23 31 37 42 48 55 61 70 76 84 90. La dichotomie compare d'abord la cible à la valeur du milieu, 42. Selon la réponse, elle continue dans la moitié gauche (dont le milieu est 19) ou dans la moitié droite (dont le milieu est 70), et ainsi de suite. Toutes les suites de questions possibles forment un arbre. On cherche ici 61.

Graphe orienté15 sommets, 14 arêtes

0 / 4

Rien n'est encore visité.

L'arbre de toutes les recherches possibles dans un tableau trié de quinze valeurs. La recherche de 61 n'en parcourt qu'une branche : quatre comparaisons, une par niveau.

Le dessin montre pourquoi la dichotomie est si rapide : elle ne parcourt pas l'arbre, elle en suit une seule branche. Son coût est donc la profondeur de l'arbre, et non son nombre de nœuds. Au pire, il faut $\lfloor \log_2 n \rfloor + 1$ comparaisons : 4 pour quinze valeurs, 10 pour mille, 20 pour un million, 33 pour les huit milliards d'habitants de la planète.

Un ordre de grandeur à retenir sans calcul

$\log_2$ d'un million vaut environ 20, et $\log_2$ d'un milliard environ 30. Multiplier la taille des données par mille n'ajoute que dix comparaisons. C'est ce comportement, et lui seul, qui rend les index de bases de données praticables sur des tables que personne ne pourrait parcourir.

La table se lit mieux en la voyant. Sur un domaine volontairement petit, l'écart paraît modeste ; c'est justement le piège des mesures faites sur de petites tailles. Le curseur sous la figure élargit l'axe horizontal : il suffit de le pousser pour voir le piège se refermer.

Élargir jusqu'à30

linéaire, n vaut 30quasi-linéaire, n log₂ n vaut 147,21quadratique, n² vaut 900

Valeurs pour n = 30, le bord droit de la figure.

Trois classes de complexité. À n = 30, le quadratique coûte six fois le quasi-linéaire, et l'écart paraît modeste. En élargissant jusqu'à quelques milliers, le linéaire et le quasi-linéaire se couchent sur l'axe : à cette échelle, seul le quadratique se voit encore.

Ce qu'il faut y regarder n'est pas la hauteur des courbes, mais leur écartement quand le domaine s'élargit. Sur le domaine de départ, les trois se tiennent ; en poussant le curseur, deux d'entre elles s'écrasent sur l'axe horizontal pendant que la troisième sort du cadre. Un banc d'essai mené sur trente éléments aurait conclu que les trois algorithmes se valent.

L'ordre de grandeur qui rend la table concrète

À un milliard d'opérations par seconde, un algorithme en $O(n^2)$ traite un million d'éléments en environ 17 minutes. Le même problème en $O(n \log n)$ demande 20 millisecondes : cinquante mille fois moins. Et l'écart s'ouvre avec la taille, il ne se referme jamais : à cent millions d'éléments, le quadratique demande près de quatre mois là où le quasi-linéaire tient en trois secondes. Ce n'est plus une optimisation, c'est la différence entre faisable et infaisable.

L'exponentielle, elle, sort de l'échelle du temps. $O(2^n)$ avec $n = 100$ demande environ $1{,}3 \times 10^{30}$ opérations, soit quarante mille milliards d'années à la même cadence : trois mille fois l'âge de l'univers. Aucune machine, jamais, ne le fera.

Le réflexe du doublement

« Si on double la taille des données, que devient le temps ? » $O(\log n)$  : il augmente d'une constante. $O(n)$  : il double. $O(n \log n)$  : il fait un peu plus que doubler. $O(n^2)$  : il quadruple. $O(2^n)$  : il est élevé au carré.

C'est aussi la façon la plus simple de deviner la complexité d'un code inconnu : mesurer sur $n$ , puis sur $2n$ , et lire le rapport.

Meilleur cas, pire cas, cas moyen

Pour une même taille $n$ , le nombre d'opérations dépend souvent du contenu de l'entrée. La recherche linéaire trouve parfois au premier essai, parfois au dernier. On distingue donc trois fonctions de coût :

le meilleur cas, ici la cible en première case : $\Theta(1)$ . Rarement intéressant, il décrit un coup de chance ;
le pire cas, ici la cible absente : $\Theta(n)$ . C'est la garantie, donc ce qu'on annonce par défaut ;
le cas moyen, ici la cible présente à une position au hasard : $(n + 1)/2$ comparaisons en moyenne, soit $\Theta(n)$ . Le plus réaliste, mais il exige une hypothèse sur les entrées, qu'il faut alors écrire.

Le cas et la notation sont deux questions différentes

On lit souvent « le meilleur cas est en $\Omega$ , le pire cas en $O$  ». C'est une confusion. Le cas dit de quelle entrée on parle ; la notation dit si on majore, minore ou encadre le coût de cette entrée. On peut donc encadrer le pire cas ( $\Theta(n)$ ci-dessus), ou seulement majorer le cas moyen si l'on ne sait pas mieux faire.

Le tri rapide, cas d'école du décalage

Son pire cas est $\Theta(n^2)$  : sur une liste déjà triée avec un pivot mal choisi. Son cas moyen est $\Theta(n \log n)$ , et c'est celui qu'on observe en pratique, surtout avec un pivot tiré au hasard. C'est pourquoi on le trouve dans de nombreuses bibliothèques (C++, tableaux de nombres en Java) malgré un pire cas médiocre : annoncer le seul pire cas donnerait une image fausse de son comportement réel.

Python, lui, a fait un autre choix : sorted est un Timsort, un tri par fusion adapté, en $\Theta(n \log n)$ au pire et en $\Theta(n)$ sur des données déjà triées.

Complexité spatiale

Définition

La complexité spatiale est la quantité de mémoire supplémentaire utilisée par l'algorithme, en fonction de $n$ , sans compter l'entrée elle-même.

Elle s'exprime avec les mêmes notations, et elle s'échange souvent contre du temps. La table de hachage, plus bas, en donne le cas type : elle consomme $O(n)$ de mémoire pour ramener une recherche de $O(n)$ à $O(1)$ en moyenne.

Ne pas oublier la pile d'appels

Un algorithme récursif consomme de la mémoire à chaque appel imbriqué. Une récursion de profondeur $n$ occupe $O(n)$ d'espace même si elle ne déclare aucune variable, et c'est ce qui provoque le RecursionError.

Complexité d'un problème, complexité d'un algorithme

C'est la confusion la plus fréquente, et elle survit longtemps parce qu'elle ne se voit pas sur de petits jeux de données.

Deux notions distinctes

La complexité d'un algorithme est le coût de cet algorithme-là. Elle se calcule en le lisant.

La complexité d'un problème est le coût du meilleur algorithme possible pour le résoudre, y compris ceux que personne n'a encore trouvés. C'est une borne inférieure, et elle se démontre.

Sur le 2-sum

Trois algorithmes, trois complexités : $\Theta(n^2)$ au pire par force brute, $\Theta(n \log n)$ par tri et deux pointeurs, $O(n)$ en moyenne par table de hachage.

Pour le problème, une borne se voit tout de suite : il faut au moins lire l'entrée, donc $\Omega(n)$ . En moyenne, le hachage atteint cette borne, et on ne fera pas mieux. Mais la réponse change si l'on exige une garantie au pire cas. Le hachage peut alors dégénérer en $O(n^2)$ . Et l'on démontre qu'un algorithme se bornant à comparer des sommes ne descend pas sous $n \log n$ . Le tri et les deux pointeurs deviennent alors l'algorithme optimal.

Même problème, deux réponses. La complexité d'un problème s'énonce toujours avec ses hypothèses : quel cas, et quelles opérations on s'autorise.

Les tables de hachage

La table de hachage vient d'être citée deux fois sans être expliquée, et c'est elle qui porte le meilleur des trois algorithmes du 2-sum. Reste à ouvrir la boîte : d'où vient ce $O(1)$ , et à quelle condition tient-il ?

Définition

Une table de hachage associe des clés à des valeurs. Une fonction de hachage transforme une clé en un indice de tableau ; on range la valeur à cet indice. Insertion, recherche et suppression coûtent alors $O(1)$ en moyenne.

Le principe est celui du vestiaire : plutôt que de parcourir tous les manteaux pour trouver le sien, on calcule un numéro à partir du ticket et on va directement au bon casier.

L'analogie s'arrête là, et il vaut la peine de voir le calcul, parce que c'est lui qui explique à la fois la vitesse et les collisions. Le passage d'une clé à un indice se fait en deux temps.

Transformer la clé en entier. Pour une chaîne, on parcourt les caractères en combinant leurs codes, typiquement $h \leftarrow 31\,h + \text{code}(c)$ pour chaque caractère $c$ , en partant de $h = 0$ . Le résultat est un entier quelconque, souvent très grand, qui dépend de toute la chaîne et de l'ordre de ses lettres : changer une lettre change l'entier.

Ramener cet entier dans le tableau. On prend le reste de sa division par la taille $m$ du tableau : $\text{indice} = h \bmod m$ . Ce reste est nécessairement compris entre 0 et $m - 1$ , donc toujours un indice valide.

Le calcul complet sur Lyon, lettre par lettre et en partant de $h = 0$  : $31 \times 0 + 76 = 76$ pour L, puis $31 \times 76 + 121 = 2\,477$ pour y, puis $31 \times 2\,477 + 111 = 76\,898$ pour o, enfin $31 \times 76\,898 + 110 = 2\,383\,948$ pour n. Sur une table de 8 cases, l'indice vaut $2\,383\,948 \bmod 8 = 4$  ; sur une table de 7 cases, il vaut $2\,383\,948 \bmod 7 = 0$ . Quatre lettres ont suffi à produire un entier à sept chiffres : c'est cette dispersion qui fait tout l'intérêt du procédé.

main.py

Sortie

>_ Prêt à exécuter…

Le même calcul, clé par clé. Chaque insertion affiche l'empreinte, le modulo et la case visée ; une clé qui tombe dans une case déjà occupée s'affiche en rouge.

Table de hachage à chaînageh ← h × 31 + code, puis h mod 8Cases :

Table vide. Insérer les clés une à une pour voir où chacune tombe.

case 0
case 1
case 2
case 3
case 4
case 5
case 6
case 7

0 clé dans 8 casesfacteur de charge α = 0,000 collisionplus longue liste : 0

Insérer les cinq villes sur 8 cases, puis passer à 7 et à 11 cases : la même suite de clés se répartit autrement. Ajouter ensuite quelques clés pour voir le facteur de charge monter et les listes s'allonger.

Deux conséquences se lisent directement sur ce calcul.

La première est la vitesse : quel que soit le nombre de clés déjà rangées, l'accès demande le même parcours de la chaîne et la même division. Rien ne dépend du nombre d'éléments, et c'est de là que vient le $O(1)$ .

La seconde est l'inévitabilité des collisions : le calcul projette un espace de clés immense sur $m$ cases seulement. Deux clés différentes finiront par tomber sur la même case. Avec 7 cases, SiraP rejoint Lyon en case 0 : c'est le hasard ordinaire, et on ne peut pas l'empêcher.

Paris et SiraP sur 8 cases : une collision qui n'a rien d'un hasard

Sur 8 cases, Paris et son miroir SiraP tombent tous deux en case 3. Ce n'est pas de la malchance : $31 = 32 - 1$ , donc modulo 8 multiplier par 31 revient à changer de signe. L'indice ne dépend plus que de la somme alternée des codes, et tout mot de longueur impaire tombe dans la même case que son miroir. De même, une majuscule et sa minuscule diffèrent de 32 : modulo 8, elles sont confondues.

Avec 7 cases, la structure disparaît et les deux mots se séparent. D'où la règle : avec une fonction de hachage aussi simple, on choisit une taille de table première. Les vraies implémentations (Python, Java) gardent une puissance de deux, mais brassent les bits de l'empreinte avant de la réduire.

Les collisions

Deux clés différentes peuvent donner le même indice : c'est une collision. Elles sont inévitables, il y a plus de clés possibles que de cases. Deux stratégies pour les traiter : le chaînage, où chaque case contient la liste des paires qui s'y trouvent, et l'adressage ouvert, où l'on cherche la case libre suivante.

Voici le chaînage en code : chaque case est une liste, et une collision allonge simplement la liste.

main.py

Sortie

>_ Prêt à exécuter…

Facteur de charge

Le facteur de charge d'une table est $\alpha = \dfrac{\text{nombre de clés}}{\text{nombre de cases}}$ . Avec le chaînage et une bonne fonction de hachage, une liste contient en moyenne $\alpha$ clés, et une recherche coûte $O(1 + \alpha)$ .

Tant que $\alpha$ reste borné, la recherche reste en $O(1)$ en moyenne. C'est pourquoi une table se redimensionne : quand $\alpha$ dépasse un seuil (deux tiers pour le dict de Python), elle alloue un tableau plus grand et y range à nouveau toutes les clés.

« En moyenne » et « amorti » ne disent pas la même chose

En moyenne porte sur les données : une recherche est rapide si les clés se répartissent bien, mais une recherche particulière peut tomber sur une case surchargée.

Amorti porte sur une suite d'opérations : un redimensionnement coûte $O(n)$ , mais il n'arrive que rarement, et réparti sur toutes les insertions qui l'ont précédé, il ne coûte que $O(1)$ par insertion.

Une insertion dans un dict est donc en $O(1)$ amorti et en moyenne : les deux mots désignent deux raisons différentes.

Le O(1) est une moyenne, pas une garantie

Si toutes les clés atterrissent dans la même case, la table dégénère en liste chaînée et la recherche redevient $O(n)$ . C'est le pire cas, et il est réellement exploitable : une attaque par collisions de hachage consiste à envoyer à un serveur des clés choisies pour se percuter, jusqu'à l'effondrement.

En pratique, avec une bonne fonction de hachage et un facteur de charge maîtrisé, le coût reste $O(1)$ en moyenne. Mais on écrit «  $O(1)$ en moyenne », jamais «  $O(1)$  » tout court.

En Python, la table de hachage est le type dict ; l'appartenance à un set en est un cas particulier. Ce sont les dictionnaires et les ensembles du parcours Python, et leur rapidité vient de là.

main.py

Sortie

>_ Prêt à exécuter…

Mesurer une durée plus courte que la précision de l'horloge

Dans le navigateur, l'horloge n'est précise qu'au dixième de milliseconde, par sécurité. Une recherche dans un set est des milliers de fois plus courte : chronométrée une seule fois, elle afficherait 0, et le rapport serait absurde. D'où timeit, qui répète l'opération des centaines de milliers de fois et divise. C'est la règle de toute mesure de performance : ne jamais chronométrer une seule exécution d'une opération brève.

Pourquoi hash() de Python donne un résultat différent à chaque exécution

Relancer un programme qui affiche hash("clavier") : la valeur change. Ce n'est pas un bug, c'est la protection contre l'attaque par collisions décrite plus haut. Une graine aléatoire est tirée au démarrage, ce qui empêche un attaquant de préparer à l'avance des clés qui se percutent. C'est aussi la raison pour laquelle un hash() ne doit jamais être stocké sur disque ni transmis : il n'a de sens que dans le processus qui l'a calculé.

Vérification rapideon peut se reprendre

1.Un algorithme en O(n²) est-il toujours plus lent qu'un O(n log n) ?

2.Une table de hachage donne un accès en O(1)…

3.Une table de 1 000 cases contient 3 000 clés, rangées par chaînage. Combien de clés contient une case, en moyenne ?

4.On double la taille des données. Un algorithme en O(n²) voit son temps…

5.Complexité d'un problème et complexité d'un algorithme, quelle différence ?

Le 2-sum, trois algorithmes

Le problème : étant donné une liste d'entiers et une cible, existe-t-il deux éléments distincts dont la somme vaut la cible ? Les valeurs peuvent être négatives, il peut y avoir des doublons, et rien n'est trié.

C'est la question posée en ouverture du chapitre, dépouillée de son décor : sur les relevés du quartier, la liste est celle des productions instantanées, et la cible la demande à couvrir. Les trois algorithmes qui suivent y répondent tous les trois correctement. Ils ne s'y prennent pas du tout de la même façon, et l'écart se voit à partir de quelques milliers de relevés.

Force brute : $\Theta(n^2)$ en temps, $O(1)$ en espace

On essaie toutes les paires. Il y en a $(n-1) + (n-2) + \dots + 1 = n(n-1)/2$ , la somme des termes d'une suite arithmétique (le chapitre sur les suites). Le pire cas, quand aucune paire ne convient, les parcourt toutes : le comportement est bien quadratique.

Tri puis deux pointeurs : $\Theta(n \log n)$ en temps, $O(n)$ en espace

On trie, puis on place un pointeur à chaque extrémité. Si la somme est trop grande, on recule celui de droite ; trop petite, on avance celui de gauche. Le tri domine le coût total. La mémoire vient du tri lui-même (sorted crée une nouvelle liste) et de la liste des indices d'origine, qu'il faut conserver pour répondre.

Table de hachage : $O(n)$ en moyenne en temps, $O(n)$ en espace

Un seul parcours. Pour chaque élément $x$ , on regarde si son complément $\text{cible} - x$ a déjà été rencontré. La table rend cette question $O(1)$ en moyenne, et c'est tout le gain.

Les trois coûts, de dix à un million d'éléments. En échelle linéaire, la table de hachage se confondrait avec l'axe dès quelques centaines d'éléments. On passe donc en échelle log-log : chaque graduation multiplie la précédente par dix, et une complexité en $n^a$ devient une droite de pente $a$ . L'écart entre les deux meilleurs reste modeste ; celui qui les sépare de la force brute se compte en décades.

table de hachage, n vaut 1 000 000tri et deux pointeurs, n log₂ n vaut 19 931 569force brute, n²/2 vaut 5 × 10¹¹

Valeurs pour n = 1 000 000, le bord droit de la figure.

Les trois algorithmes du 2-sum, en échelle log-log. À un million d'éléments, un million d'opérations pour la table, vingt millions pour le tri, cinq cents milliards pour la force brute. La table et le tri sont deux droites presque parallèles de pente voisine de 1, la force brute une droite de pente 2.

Ce qu'il faut y regarder, c'est la pente des droites, pas leur position. Deux d'entre elles montent au même rythme : le tri ne coûte qu'un facteur logarithmique de plus que la table, et ce facteur se voit à peine. La troisième monte deux fois plus vite, et l'écart qui la sépare des deux autres s'ouvre de façon irrattrapable. Une pente, sur ce type de graphe, est un exposant.

main.py

Sortie

>_ Prêt à exécuter…

Pourquoi vérifier la somme et non les indices

Les trois algorithmes peuvent renvoyer des paires différentes quand plusieurs solutions existent, et ils ont tous raison. Tester l'égalité des indices ferait échouer un test sur un algorithme correct, et tester seulement que les trois réponses concordent laisserait passer trois algorithmes faux de la même façon. On vérifie donc la propriété demandée : deux éléments distincts, dont la somme vaut la cible, ou aucune réponse s'il n'en existe pas. C'est une habitude à prendre pour tout algorithme à solutions multiples.

Vérification

Vérification rapideon peut se reprendre

1.Le 2-sum se résout en O(n) en moyenne par table de hachage, et en Θ(n log n) par tri. Qu'apporte le tri ?

2.Recherche linéaire dans une liste de n éléments. Quelle affirmation est juste ?

3.Dans la version par hachage, on insère x dans la table après avoir cherché son complément. Pourquoi pas avant ?

Théorie contre mesure

La théorie prédit des rapports, pas des durées. Reste à la confronter à l'expérience : mesurer sur des tailles croissantes, dans le pire cas (aucune solution), puis tracer en échelle logarithmique, où une complexité en $n^a$ devient une droite de pente $a$ .

main.py

Sortie

>_ Prêt à exécuter…

Lire la pente

En échelle log-log, un temps en $n^2$ donne une droite de pente 2 et un temps en $n$ une pente 1. Celui en $n \log n$ donne une pente légèrement supérieure à 1, environ 1,14 entre 250 et 16 000. Ce sont les trois droites de la figure du 2-sum. La pente mesurée est donc une estimation expérimentale de l'exposant : c'est la façon de vérifier une complexité annoncée sans lire le code.

Des écarts sont à prévoir. Sur de petites tailles, les constantes, le cache du processeur et le ramasse-miettes pèsent plus que l'asymptotique ; la pente du hachage monte parfois au-dessus de 1 quand la table ne tient plus dans le cache. Et le tri de Python est écrit en C, bien plus rapide que la boucle des deux pointeurs écrite en Python : sur ces tailles, c'est cette boucle linéaire qui occupe l'essentiel du temps. C'est exactement ce que veut dire « asymptotique ».

Green IT

Tout ce qui précède se compte en opérations. Or une opération n'est pas gratuite : elle occupe un processeur, qui consomme de l'électricité, produite avec des émissions. Reste à savoir ce que ce raisonnement vaut vraiment, parce qu'il est souvent tenu trop vite.

Définition

Le Green IT désigne l'ensemble des démarches visant à réduire l'empreinte environnementale du numérique : fabrication des équipements, consommation d'énergie en exploitation, et fin de vie.

Quelques ordres de grandeur. Ils sont tirés de l'actualisation par l'ADEME de son étude menée avec l'Arcep (données 2022, publiée en janvier 2025). Le numérique y représente 4,4 % de l'empreinte carbone de la France, soit 29,5 millions de tonnes équivalent CO₂. Cette empreinte se répartit entre les terminaux (50 %, fabrication et usage), les centres de données (46 %) et les réseaux (4 %). La part des centres de données a fortement augmenté par rapport à l'étude précédente, en partie parce que les centres situés à l'étranger et utilisés par des services français sont désormais comptés. Ces chiffres dépendent du périmètre retenu, et il faut les citer comme des estimations, avec leur source.

Le lien avec ce chapitre

Le temps de calcul se paie en énergie, et l'énergie en émissions. Passer un traitement quotidien de $O(n^2)$ à $O(n)$ sur un million d'enregistrements réduit le nombre d'opérations d'un facteur de l'ordre du million : aucune action sur le refroidissement d'un centre de données n'approche ce rapport.

Mais le gain en énergie est plus petit que le gain en opérations, pour deux raisons. Les constantes d'abord : le rapport asymptotique n'est pas le rapport réel. Surtout, un serveur allumé en permanence consomme une part importante de sa puissance même à vide : finir un traitement plus vite n'économise que la part qui dépend du calcul. Le gain devient entier quand il permet d'éteindre une machine, de mutualiser, ou de ne pas en acheter une nouvelle. C'est par là que l'optimisation rejoint l'essentiel, puisque la fabrication pèse lourd dans l'empreinte.

Le rapport entre les deux coûts vaut $n^2 / n = n$  : il grandit avec les données. En échelle log-log, ce rapport est l'écart vertical entre les deux droites.

Élargir jusqu'à1000

traitement en O(n) vaut 1000traitement en O(n²) vaut 1 000 000

Valeurs pour n = 1000, le bord droit de la figure.

Un traitement en O(n) contre le même en O(n²), en échelle log-log. L'écart vertical entre les deux droites gagne une décade chaque fois que les données sont multipliées par dix. À mille enregistrements, le second demande mille fois plus d'opérations ; en élargissant jusqu'à un million, le rapport atteint un million.

Ce qu'il faut y voir : les deux droites divergent, elles ne se rapprochent jamais. Un gain d'efficacité obtenu sur un algorithme ne s'use donc pas avec le temps ; il grandit à mesure que le parc de données grandit. C'est ce qui distingue une optimisation algorithmique d'un réglage de configuration.

Ce que cette figure ne dit pas

Elle compare des ordres de grandeur, pas des durées. Un algorithme en $O(n)$ avec une constante énorme peut rester plus lent qu'un $O(n^2)$ sur de petites tailles, et c'est le cas courant en dessous de quelques centaines d'éléments. La complexité décide du comportement quand $n$ grandit, elle ne décide pas de qui gagne aujourd'hui sur les données d'aujourd'hui. D'où la section précédente : théorie contre mesure.

L'effet rebond

Un traitement dix fois plus rapide ne divise pas forcément la consommation par dix. Puisqu'il ne coûte presque plus rien, on le lance toutes les heures au lieu d'une fois par jour, sur plus de données et pour plus d'utilisateurs. La consommation totale peut alors augmenter. C'est l'effet rebond, observé depuis le XIXe siècle sur le charbon, et il est la règle en informatique. Une optimisation n'est un gain environnemental que si l'usage reste maîtrisé.

Les leviers, à combiner :

Choisir le bon algorithme et la bonne structure de données. C'est, du côté du code, le levier au meilleur rapport effort/gain, et de loin.
Ne pas calculer deux fois la même chose : mise en cache, mémoïsation, calculs incrémentaux.
Déplacer les traitements lourds vers les heures où l'électricité est la moins carbonée, ce que permet précisément un réseau intelligent, qui rend la production visible en temps réel.
Dimensionner au besoin réel : un serveur surdimensionné consomme même à vide.
Allonger la durée de vie du matériel, ce que rend possible un logiciel qui n'exige pas toujours plus. À l'échelle d'un système d'information, ce levier pèse souvent davantage que tous les autres, puisque la fabrication domine l'empreinte des terminaux.

Le réseau intelligent (smart grid)

Un réseau électrique classique fait circuler l'énergie dans un seul sens, d'une production centralisée vers les consommateurs. Un smart grid y ajoute capteurs, communication et pilotage : les échanges deviennent bidirectionnels, un bâtiment produisant du solaire peut réinjecter son surplus, et la consommation peut être décalée vers les moments d'abondance.

Apparier des surplus de production avec des demandes est, dans la réalité, un problème d'optimisation plus riche que le 2-sum. Il en a pourtant la difficulté centrale : traiter en continu des centaines de milliers de relevés. Un algorithme quadratique interdirait le temps réel, et donc l'arbitrage énergétique lui-même.

Vérification rapideon peut se reprendre

1.Réduire la complexité d'un traitement a un effet Green IT parce que…

2.Un traitement nocturne passe de 2 heures à 2 minutes sur un serveur qui reste allumé jour et nuit. La consommation du serveur est-elle divisée par 60 ?

3.Après optimisation, un rapport qui coûtait une heure de calcul n'en coûte plus qu'une minute. L'équipe décide de le produire toutes les cinq minutes au lieu d'une fois par jour. Comment s'appelle ce phénomène ?

Exercices type

Donner la complexité de deux boucles imbriquées, où la seconde commence juste après la première (i de 0 à n − 1, j de i + 1 à n − 1)

Pour $i = 0$ la boucle intérieure fait $n - 1$ tours, pour $i = 1$ elle en fait $n - 2$ , et ainsi de suite jusqu'à 0. Le nombre d'itérations vaut $(n-1) + (n-2) + \dots + 1 + 0 = n(n-1)/2$ .

C'est un polynôme de degré 2, donc $\Theta(n^2)$ .

Le point à retenir : faire démarrer la seconde boucle après la première ne change pas la classe. On économise un facteur 2 par rapport à la double boucle complète, et ce facteur 2 disparaît dans la notation.

Un algorithme traite 1 000 éléments en 1 seconde. Combien pour 10 000, en

O(n)

O(n \log n)

O(n^2)

$O(n)$  : facteur 10 → 10 secondes.

$O(n \log n)$  : facteur $10 \times (\log 10000 / \log 1000) = 10 \times 4/3 \approx 13$ → 13 secondes.

$O(n^2)$  : facteur 100 → 100 secondes.

Refaire le calcul pour 1 000 000 d'éléments : $O(n)$ donne 1 000 s (17 minutes), $O(n^2)$ donne $10^6$ s, soit 11 jours et demi. L'écart ne cesse de croître, et c'est précisément ce que dit l'asymptotique.

Prouver que

T(n) = 5n^2 + 3n + 7 = O(n^2)

Pour tout $n \geq 1$ on a $n \leq n^2$ et $1 \leq n^2$ , donc :

5n^2 + 3n + 7 \leq 5n^2 + 3n^2 + 7n^2 = 15n^2

La définition est vérifiée avec $n_0 = 1$ et $k = 15$ . ∎

On peut même dire mieux : $T(n) = \Theta(n^2)$ , puisque $T(n) \geq 5n^2$ pour tout $n \geq 1$ , ce qui fournit la minoration avec $k = 5$ .

Pourquoi la recherche dans une table de hachage n'est-elle pas garantie en

O(1)

À cause des collisions. Si plusieurs clés produisent le même indice, elles s'accumulent dans la même case, et il faut les parcourir. Dans le pire cas (toutes les clés en collision) la table dégénère en liste et la recherche devient $O(n)$ .

En pratique, avec une fonction de hachage qui répartit bien et un facteur de charge tenu sous contrôle par redimensionnement, le coût reste $O(1)$ en moyenne.

Ce pire cas n'est pas qu'une hypothèse d'école : c'est un vecteur d'attaque par déni de service, où l'attaquant fabrique des clés choisies pour se percuter. Les langages modernes s'en protègent en introduisant une graine aléatoire dans la fonction de hachage.

Le tri prend

O(n \log n)

, la recherche de la paire

O(n)

. Quelle est la complexité totale ?

$O(n \log n)$ .

On additionne les étapes : $T(n) = O(n \log n) + O(n)$ . Le terme dominant l'emporte, puisque $n \log n$ croît plus vite que $n$ .

C'est la règle générale d'un enchaînement séquentiel : la complexité totale est celle de l'étape la plus coûteuse. Optimiser la recherche de la paire ne servirait donc à rien tant que le tri est là, et c'est ce qui justifie de chercher une méthode qui évite complètement de trier.

Pourquoi mesure-t-on des temps qui ne correspondent pas exactement à la théorie sur de petites tailles ?

Parce que l'analyse asymptotique décrit le comportement quand $n$ tend vers l'infini, et néglige tout le reste.

Sur de petites tailles, ce « reste » domine : constantes multiplicatives, termes d'ordre inférieur, cache du processeur, ramasse-miettes, bruit de mesure du système. Le cache pèse particulièrement : une petite structure y tient entièrement, une grande non.

Conséquence pratique, souvent contre-intuitive : un algorithme en $O(n^2)$ peut être plus rapide qu'un $O(n \log n)$ sur de petites entrées, ses constantes étant plus faibles. C'est pourquoi les tris des bibliothèques basculent sur un tri par insertion en dessous de quelques dizaines d'éléments.

La méthode

Nommer $n$ en toute première ligne. «  $n$ = nombre de relevés » : sans cela, la complexité ne veut rien dire.
Compter les opérations élémentaires, boucle par boucle, en identifiant celle qui domine.
Préciser le cas : pire, moyen ou meilleur. Par défaut, le pire.
Écrire $O$ pour une majoration, $\Theta$ quand on a l'encadrement, quel que soit le cas étudié.
Prouver une majoration en exhibant un $n_0$ et un $k$  : c'est tout ce qu'exige la définition.
Donner aussi la complexité spatiale. Un gain de temps payé en mémoire est un compromis, pas un progrès automatique.
Confronter à la mesure : répéter les mesures brèves, tracer en log-log, lire la pente, comparer à l'exposant théorique.
Conclure en énergie quand le sujet est le Green IT, sans oublier la consommation à vide et l'effet rebond.

Synthèse

On mesure comment le temps croît avec $n$ , pas combien de secondes il prend.
Opération élémentaire : coût indépendant de $n$ . Fonction de coût $T(n)$  : leur nombre.
$u = O(v)$ s'il existe $n_0$ et $k > 0$ tels que $\forall n \geq n_0, |u(n)| \leq k|v(n)|$ .
$O$ majore, $\Omega$ minore, $\Theta$ encadre. $\Theta$ est plus fort, et plus précis.
Classes usuelles : $O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)$ .
Dichotomie : une seule branche d'un arbre, $\lfloor \log_2 n \rfloor + 1$ comparaisons au pire.
Réflexe du doublement : $O(n)$ double, $O(n^2)$ quadruple, $O(2^n)$ est élevé au carré.
Le cas (meilleur, pire, moyen) et la notation ( $O$ , $\Omega$ , $\Theta$ ) sont deux choix indépendants. Pire cas par défaut ; le cas moyen exige une hypothèse sur les entrées.
Complexité spatiale : mémoire supplémentaire, pile d'appels comprise.
La complexité d'un problème est une borne sur tous les algorithmes possibles, et elle dépend des hypothèses ; celle d'un algorithme se lit dans le code.
Table de hachage : $O(1)$ en moyenne tant que le facteur de charge $\alpha$ reste borné, $O(n)$ en cas de collisions massives. Le redimensionnement est $O(1)$ amorti.
2-sum : $\Theta(n^2)$ par force brute, $\Theta(n \log n)$ par tri, $O(n)$ en moyenne par hachage. Le hachage est optimal en moyenne, le tri l'est pour une garantie au pire cas.
Dans un enchaînement, l'étape la plus coûteuse fixe le total.
En log-log, la pente estime l'exposant réel ; une opération brève se mesure en la répétant.
Green IT : le bon algorithme est le premier levier du code, mais le gain en énergie suppose d'éteindre, mutualiser ou ne pas acheter, et il est menacé par l'effet rebond.

Et ensuite

Ce chapitre a traité le coût comme un ennemi, à faire baisser. Il peut aussi se retourner en arme : s'il existe une opération facile à faire et hors de portée à défaire, elle protège un secret. Arithmétique et cryptographie construit cette asymétrie, puis s'en sert.

Ce que ce chapitre apporte

Mesurer un algorithme, pas un programme

Opération élémentaire et fonction de coût

La notation de Landau

Les classes usuelles

Meilleur cas, pire cas, cas moyen

Complexité spatiale

Complexité d'un problème, complexité d'un algorithme

Les tables de hachage

Les collisions

Le 2-sum, trois algorithmes

Force brute : $\Theta(n^2)$ en temps, $O(1)$ en espace

Tri puis deux pointeurs : $\Theta(n \log n)$ en temps, $O(n)$ en espace

Table de hachage : $O(n)$ en moyenne en temps, $O(n)$ en espace

Vérification

Théorie contre mesure

Green IT

Exercices type

La méthode

Synthèse

Et ensuite

Mettre en pratique

Complexité algorithmique et Green IT

Ce que ce chapitre apporte

Mesurer un algorithme, pas un programme

Opération élémentaire et fonction de coût

La notation de Landau

Les classes usuelles

Meilleur cas, pire cas, cas moyen

Complexité spatiale

Complexité d'un problème, complexité d'un algorithme

Les tables de hachage

Les collisions

Le 2-sum, trois algorithmes

Force brute : Θ(n2)\Theta(n^2)Θ(n2) en temps, O(1)O(1)O(1) en espace

Tri puis deux pointeurs : Θ(nlog⁡n)\Theta(n \log n)Θ(nlogn) en temps, O(n)O(n)O(n) en espace

Table de hachage : O(n)O(n)O(n) en moyenne en temps, O(n)O(n)O(n) en espace

Vérification

Théorie contre mesure

Green IT

Exercices type

La méthode

Synthèse

Et ensuite

Mettre en pratique

Force brute : $\Theta(n^2)$ en temps, $O(1)$ en espace

Tri puis deux pointeurs : $\Theta(n \log n)$ en temps, $O(n)$ en espace

Table de hachage : $O(n)$ en moyenne en temps, $O(n)$ en espace