Complexité algorithmique et Green IT

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

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.

Dans le pire des cas (la valeur est absente), la boucle fait $n$ tours. La variable comparaisons n'est qu'un instrument de mesure : ses propres mises à jour ne comptent pas. Chaque tour coûte en revanche trois opérations de l'algorithme : la comparaison tableau[i] = cible, celle que compte la variable, et deux autres invisibles dans le code, le test « $i$ a-t-il dépassé $n$ ? » et l'incrémentation de $i$. Trois opérations restent hors des tours : l'initialisation de $i$, le dernier test, celui qui fait sortir de la boucle, et le retour final. On obtient $T(n) = 3n + 3$ opérations.

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.

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 ». Formellement, $u(n) = \Omega(v(n))$ s'il existe $n_0$ et $k > 0$ tels que $|u(n)| \geq k\,|v(n)|$ pour tout $n \geq n_0$ : la même définition que $O$, avec l'inégalité retournée. C'est la notation des bornes inférieures, celles qui disent qu'aucun algorithme ne peut faire mieux.
• $\Theta(v)$, l'encadrement : $O(v)$ et $\Omega(v)$ à la fois, c'est-à-dire $k_1\,|v(n)| \leq |u(n)| \leq k_2\,|v(n)|$ à partir d'un certain rang. C'est la plus précise, et souvent celle qu'on veut vraiment dire.

La définition parle de courbes, et jusqu'ici elle n'en montrait aucune. Les voici : le coût mesuré, et deux plafonds candidats.

Les classes usuelles

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. Les nombres de la table prennent le logarithme en base 2, noté $\log_2$, celui qui compte les divisions par deux : $\log_2 1\,000 \approx 10$. Dans un $O$, la base ne s'écrit pas : changer de base multiplie le logarithme par une constante ($\log_2 n = \ln n / \ln 2$), et les constantes disparaissent.

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.

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, où $\lfloor \cdot \rfloor$ désigne la partie entière, l'arrondi à l'entier inférieur : 4 pour quinze valeurs, 10 pour mille, 20 pour un million, 33 pour les huit milliards d'habitants de la planète.

La table se lit mieux en la voyant. Le curseur sous la figure élargit l'axe horizontal, de trente jusqu'à cent mille : il suffit de le pousser pour voir les écarts se creuser.

Ce qu'il faut y regarder n'est pas la hauteur des courbes, mais ce que devient leur rapport quand le domaine s'élargit. À $n = 30$, le quadratique vaut trente fois le linéaire ; à $n = 3\,000$, il vaut trois mille fois le linéaire et deux cent soixante fois le quasi-linéaire. Le rapport entre deux classes n'est pas un nombre fixe : il grandit avec $n$. Sur un banc d'essai réel, les constantes peuvent masquer ce rapport tant que $n$ reste petit, et c'est là que trente éléments trompent.

Ces classes se lisent dans le code, boucle par boucle.

La courbe l'annonce, la course le fait subir. Deux tris travaillent ci-dessous sur les mêmes seize valeurs, un geste chacun par battement : l'un est quadratique, l'autre quasi-linéaire.

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, chacune avec la probabilité $1/n$. La position $p$ coûte $p$ comparaisons, d'où une moyenne de $(1 + 2 + \dots + n)/n = (n + 1)/2$ comparaisons, soit $\Theta(n)$. C'est le plus réaliste, mais il exige une hypothèse sur les entrées, qu'il faut alors écrire.

Complexité spatiale

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.

Les tables de hachage

Le contrôle des doublons pose, pour chaque paiement, une seule question : « cette référence a-t-elle déjà été vue ? ». Dans une liste, la réponse coûte un parcours de tout ce qui a déjà été vu. Une table de hachage la donne en temps constant, en moyenne. Reste à ouvrir la boîte : d'où vient ce $O(1)$, et à quelle condition tient-il ?

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 code d'un caractère est son numéro dans la table Unicode : 76 pour L, 121 pour y. 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, $2\,383\,948 = 8 \times 297\,993 + 4$ : l'indice vaut $2\,383\,948 \bmod 8 = 4$. Sur une table de 7 cases, $2\,383\,948 = 7 \times 340\,564$ : l'indice vaut 0. Quatre lettres ont suffi à produire un entier à sept chiffres : c'est cette dispersion qui fait tout l'intérêt du procédé.

La figure fait le même calcul, sans borne, 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.

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, c'est-à-dire de deux clés différentes envoyées dans la même case : le calcul projette un espace de clés immense sur $m$ cases seulement. Avec 7 cases, SiraP rejoint Lyon en case 0, et Bordeaux rejoint Nantes en case 2 : c'est le hasard ordinaire, et on ne peut pas l'empêcher.

Les collisions

Puisque les collisions sont inévitables, il faut savoir les ranger. Deux stratégies existent : le chaînage, où chaque case contient la liste des clés qui y tombent, et l'adressage ouvert, où l'on cherche la case libre suivante. La figure précédente pratique le chaînage : une collision y allonge simplement la liste de la case.

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, en général deux fois plus grand, et y range à nouveau toutes les clés.

En Python, la table de hachage est le type dict, et l'ensemble, set, en est un cas particulier : une table qui ne range que des clés. Ce sont les dictionnaires et les ensembles du parcours Python, et leur rapidité vient de là. Le programme ci-dessous cherche la même référence dans une liste et dans un ensemble de deux cent mille références.

Le rapport se compte en dizaines de milliers, et il grandit avec la liste : la recherche dans la liste la parcourt, en $O(n)$, celle dans l'ensemble calcule une case, en $O(1)$ en moyenne. Le programme répète chaque recherche avant de diviser, et c'est la règle de toute mesure : une opération brève ne se chronomètre jamais seule.

Les doublons, trois algorithmes

Le problème : étant donné une liste de références de paiement, deux d'entre elles sont-elles égales, et laquelle ? Chaque paiement y est réduit à sa référence, un numéro qui combine le fournisseur et la facture : deux saisies du même paiement portent la même référence. C'est la question posée en ouverture du chapitre. Trois algorithmes y répondent correctement, et ne s'y prennent pas du tout de la même façon ; l'écart se voit dès quelques milliers de paiements.

Double boucle : $\Theta(n^2)$ en temps, $O(1)$ en espace

On compare chaque référence à toutes celles qui la suivent. Il y a $(n-1) + (n-2) + \dots + 1 = n(n-1)/2$ paires, la somme des termes d'une suite arithmétique (le chapitre sur les suites). Le pire cas, quand aucun paiement n'est en double, les compare toutes : le comportement est bien quadratique.

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

On trie les références. Deux références égales finissent alors côte à côte, et il suffit de comparer chacune à sa voisine : $n - 1$ comparaisons. Le tri coûte $\Theta(n \log n)$ et domine le total. La mémoire vient de la copie triée que crée sorted, qui laisse la liste de départ intacte.

Ensemble : $O(n)$ en moyenne en temps, $O(n)$ en espace

Un seul parcours. Pour chaque référence, on teste si elle est déjà dans l'ensemble des références vues, puis on l'y range. L'ensemble rend ce test $O(1)$ en moyenne, et c'est tout le gain : $n$ tests au lieu de $n(n-1)/2$ comparaisons.

Les trois coûts, de dix à un million de paiements. En échelle linéaire, l'ensemble se confondrait avec l'axe dès quelques centaines de paiements. 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$, parce que $\log(c\,n^a) = \log c + a \log n$. L'écart entre les deux meilleurs reste modeste ; celui qui les sépare de la double boucle se compte en puissances de dix.

Ce qu'il faut y regarder, c'est la pente des droites, pas leur position. Deux d'entre elles montent presque au même rythme : le tri ne coûte qu'un facteur $\log_2 n$ de plus que l'ensemble, une vingtaine à un million de paiements, soit un peu plus d'une graduation d'écart, qui ne grandit que très lentement. 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.

Les trois algorithmes, écrits en Python et essayés sur quelques listes :

Sur la quatrième liste, deux paiements sont en double, et les trois algorithmes ne désignent pas le même : 7781 pour la double boucle, 3302 pour les deux autres. Tous ont raison.

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

C'est une confusion fréquente, et elle passe inaperçue tant qu'on n'a qu'un seul algorithme sous les yeux : on dit alors « ce problème est quadratique » quand seul l'algorithme l'est. Les doublons en donnent maintenant trois.

Pour le tri lui-même, la borne inférieure tient en un comptage.

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 (aucun doublon), puis tracer en échelle logarithmique, où une complexité en $n^a$ devient une droite de pente $a$.

Le programme ci-dessous chronomètre les trois algorithmes des doublons, et calcule la pente par la droite des moindres carrés sur toutes les mesures plutôt qu'entre deux seulement : le bruit d'une mesure isolée y pèse moins.

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. Un temps 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 des doublons. 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.

Les mesures s'en approchent : une pente voisine de 2 pour la double boucle, voisine de 1 pour l'ensemble, et entre les deux pour le tri, souvent un peu au-dessus de 1,14, vers 1,2 ou 1,3. Des écarts sont à prévoir. Sur de petites tailles, les constantes pèsent plus que l'asymptotique. Surtout, la mémoire n'est pas uniforme : le processeur garde les données récentes dans un cache, une petite mémoire très rapide, et une structure qui n'y tient plus coûte plus cher à chaque accès. C'est ce qui fait monter les pentes du tri et de l'ensemble quand $n$ grandit. Pour le tri, la pente mélange en outre deux étapes de vitesses très différentes : sorted, écrit en C, est rapide, et la boucle des voisins, écrite en Python, est lente. Elle prend près de la moitié du temps aux petites tailles, et encore un quart à un tiers à 16 000 éléments. La pente lue dépend donc de la plage mesurée, et c'est exactement ce que veut dire « asymptotique » : la théorie dit ce qui l'emporte quand $n$ grandit, pas ce qui pèse à une taille donnée.

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.

Quelques ordres de grandeur. Ils sont tirés de l'étude de l'ADEME et de l'Arcep sur l'empreinte environnementale du numérique en France, actualisée en janvier 2025 sur les données de 2022. 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. Sur la figure log-log des doublons, c'est l'écart vertical entre la droite de la double boucle et celle de l'ensemble, qui gagne une graduation chaque fois que les données sont multipliées par dix. 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.

Ces notions se chiffrent avec quatre outils.

Les leviers, à combiner :

1. 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.
2. Ne pas calculer deux fois la même chose : mise en cache, mémoïsation, calculs incrémentaux.
3. Déplacer les traitements lourds vers les heures où l'électricité est la moins carbonée. Le contenu en CO₂ d'un kilowattheure varie d'une heure à l'autre selon les centrales en service, et RTE le publie en temps réel pour la France sur son service éCO2mix. Un traitement qui n'a pas à répondre dans l'instant, comme le contrôle nocturne des doublons, peut attendre le moment le plus favorable ; une requête d'utilisateur, non.
4. Dimensionner au besoin réel : un serveur surdimensionné consomme même à vide.
5. 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.

Retour aux paiements

La question d'ouverture se tranche maintenant en quelques lignes de calcul. L'historique compte $n = 10^7$ paiements, et la machine fait un milliard d'opérations par seconde.

• La double boucle compare $10^7 \times (10^7 - 1) / 2 \approx 5 \times 10^{13}$ paires, soit environ 50 000 secondes : près de 14 heures. Le contrôle ne tient pas dans les huit heures de la nuit, et il tiendra moins encore quand l'historique doublera, puisque sa durée quadruplera, à plus de deux jours.
• Le tri puis les voisins demande de l'ordre de $n \log_2 n \approx 2{,}3 \times 10^8$ opérations : un quart de seconde.
• L'ensemble fait $10^7$ tests : un centième de seconde. Le rapport avec la double boucle, $(n - 1)/2$, environ cinq millions, ne doit rien à la machine.

En énergie, la réponse est plus modeste. Sur le serveur du rappel de cours, 100 W à vide et 250 W en calcul, la double boucle ajoute $150 \times 13{,}9 \approx 2\,100$ Wh par contrôle, soit environ 25 kWh par an pour douze clôtures, et au plus 37,5 kWh au compteur d'un centre de PUE 1,5. Le serveur en consomme 876 par an à vide : s'il reste allumé pour d'autres services, la bonne version n'économise qu'environ 3 % de sa consommation. Le gain devient entier s'il peut être éteint, servir à autre chose, ou ne jamais être acheté. Le bon algorithme rend le contrôle possible ; il ne devient une économie d'énergie importante que si le matériel suit.

La méthode

1. Nommer $n$ en toute première ligne. « $n$ = nombre de paiements à contrôler » : sans cela, la complexité ne veut rien dire.
2. Compter les opérations élémentaires, boucle par boucle : nombre de tours multiplié par le coût d'un tour, en identifiant la boucle qui domine.
3. Préciser le cas : pire, moyen ou meilleur. Par défaut, le pire.
4. Écrire $O$ pour une majoration, $\Theta$ quand on a l'encadrement, quel que soit le cas étudié.
5. Prouver une majoration en exhibant un $n_0$ et un $k$ : c'est tout ce qu'exige la définition.
6. Donner aussi la complexité spatiale. Un gain de temps payé en mémoire est un compromis, pas un progrès automatique.
7. Confronter à la mesure : répéter les mesures brèves, tracer en log-log, lire la pente $a = \ln(t_2/t_1) / \ln(n_2/n_1)$, comparer à l'exposant théorique.
8. Conclure en énergie quand le sujet est le Green IT : $E = P \times t$ sur la seule part au-dessus de la consommation à vide, au plus multipliée par le PUE au compteur, puis par le facteur d'émission, sans oublier l'effet rebond.

Mettre en pratique

Une complexité s'annonce en notation asymptotique et se vérifie en nombres. Le bloc ci-dessous reprend, dans un autre contexte, les rappels du chapitre : lire une boucle, la dichotomie, lire un exposant et extrapoler une durée, l'énergie et les émissions. Chaque question a son indice.

Les deux dernières réponses se lisent ensemble : 18 kilowattheures par an, moins d'un kilogramme et demi de CO₂e. Le serveur en consomme environ 700 par an à vide : rendre ce contrôle cent fois plus rapide ne changerait presque rien à sa consommation. Ce qui compte ici, c'est de pouvoir éteindre ou partager le serveur.

Chaque exercice type emploie un rappel de cours déjà donné : extrapoler une durée et lire un exposant (théorie contre mesure), la définition de $O$ (notation de Landau), l'énergie et la consommation à vide (Green IT). Un seul outil est nouveau, la règle de l'enchaînement.