Complexité algorithmique et Green IT

Où on va

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, et il finit là où le bloc veut en venir : du temps de calcul économisé, c'est de l'énergie économisée.

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. Change n'importe lequel de ces facteurs, et 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 :

Algorithme

Fonction Rechercher(tableau, cible)

Pour i de 0 à n-1 Faire

Si tableau[i] = cible Alors

Retourner i

FinSi

FinPour

Retourner -1

FinFonction

Dans le pire des cas (la valeur est absente) la boucle fait $n$ tours, avec par tour une comparaison d'indice, une comparaison de valeur et une incrémentation : $T(n) = 3n + 2$ 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

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, |u(n)| \leq k |v(n)|$

Trois notations, et il faut savoir laquelle on emploie :

$O(v)$  : majoration : « ne croît pas plus vite que ». C'est la plus utilisée, parce qu'on veut garantir un pire cas.
$\Omega (v)$  : minoration : « croît au moins aussi vite que ». C'est celle des bornes inférieures, donc des théorèmes d'impossibilité.
$\Theta (v)$  : 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 Θ(n) est aussi, formellement, en O(n²), et en O(n¹⁰⁰). La majoration reste vraie, elle est simplement mauvaise.
Quand tu affirmes une complexité, dis si c'est une majoration ou un encadrement. Écrire Θ quand tu le sais est plus fort, plus précis, et signale que tu as compris la différence.

Une preuve, parce qu'on en attend une

Montrons que $T(n) = 3n + 2 = O(n)$ .

Prenons $n_0 = 1$ et $k = 5$ . 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. Exhiber un couple suffit, c'est tout ce que demande la définition.

Les classes usuelles

Complexité	Nom	Exemple typique	$n = 1 000$	$n = 1 000 000$
$O(1)$	constante	accès à une case, à une clé de dictionnaire	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, tri rapide	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 de grandeur qui rend la table concrète

À un milliard d'opérations par seconde, un algorithme en O(n²) traite un million d'éléments en environ 11 jours. Le même problème en O(n log n) demande 20 millisecondes. Ce n'est pas une optimisation, c'est la différence entre faisable et infaisable.
Et O(2ⁿ) avec n = 100 dépasse le nombre d'atomes de l'univers observable : aucune machine, jamais, ne le fera.

Le réflexe du doublement

« Si je double la taille de mes données, que devient le temps ? » O(n) : il double. O(n²) : il quadruple. O(log n) : il augmente d'une constante. O(2ⁿ) : il est élevé au carré.
C'est aussi la façon la plus simple de deviner la complexité d'un code inconnu : mesure sur n, puis sur 2n, et regarde 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.

Meilleur cas : $\Omega (1)$ ici. Rarement intéressant : il décrit un coup de chance.
Pire cas : $O(n)$ . C'est la garantie, donc ce qu'on annonce par défaut.
Cas moyen : $\Theta (n/2) = \Theta (n)$ . Le plus réaliste, mais il exige une hypothèse sur la distribution des entrées, qu'il faut alors écrire.

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

Son pire cas est O(n²) : sur une liste déjà triée avec un pivot mal choisi. Son cas moyen est Θ(n log n), et c'est celui qu'on observe en pratique. C'est pourquoi il reste le tri le plus utilisé malgré un pire cas médiocre : annoncer le seul pire cas donnerait ici une image fausse de son comportement réel.

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 : c'est exactement ce que fera la table de hachage plus bas, en consommant $O(n)$ de mémoire pour ramener une recherche de $O(n)$ à $O(1)$ .

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 : O(n²) par force brute, O(n log n) par tri et deux pointeurs, O(n) par table de hachage.
La complexité du problème, elle, est Θ(n) : on ne peut pas faire mieux que lire l'entrée une fois, et l'algorithme par hachage atteint cette borne. Le problème est donc résolu de façon optimale, chercher un algorithme plus rapide reviendrait à espérer ne pas lire toutes les données.

Les tables de hachage

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.

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.

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 taux de remplissage maîtrisé, le coût amorti reste O(1). Mais on écrit « O(1) en moyenne », jamais « O(1) » tout court.

En Python, la table de hachage est le type dict, et l'appartenance à un set en est un cas particulier.

main.py

Sortie

>_ Prêt à exécuter…

Et une fonction de hachage écrite à la main, pour voir d'où viennent les collisions :

main.py

Sortie

>_ Prêt à exécuter…

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

Relance 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 rapidesans note, on 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.Réduire la complexité d'un traitement a un effet Green IT parce que…

Le 2-sum, trois algorithmes

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

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

On essaie toutes les paires. Il y en a $n(n-1)/2$ , ce qui donne bien un comportement quadratique.

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

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.

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

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

main.py

Sortie

>_ Prêt à exécuter…

Pourquoi comparer les sommes 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. On vérifie donc la propriété demandée (« la somme vaut la cible ») et non une réponse particulière. C'est une habitude à prendre pour tout algorithme à solutions multiples.

Théorie contre mesure

La théorie prédit des rapports, pas des durées. Confrontons-la à l'expérience : on mesure sur des tailles croissantes, dans le pire cas (aucune solution), et on trace en échelle logarithmique, où une complexité en nᵃ devient une droite de pente $a$ .

main.py

Sortie

>_ Prêt à exécuter…

Lire la pente

En échelle log-log, un temps en n² donne une droite de pente 2, un temps en n une pente 1, et n log n une pente légèrement supérieure à 1. 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.
Attends-toi à des écarts sur les petites tailles, les constantes, le cache du processeur et le ramasse-miettes y pèsent plus que l'asymptotique. C'est normal, et c'est exactement ce que veut dire « asymptotique ».

Green IT

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.

Un point de repère souvent rappelé : la fabrication des terminaux pèse une part majoritaire de l'empreinte du numérique, devant la consommation électrique d'usage. Les chiffres précis varient selon le périmètre retenu par chaque étude, et il faut les citer comme des estimations ; l'ordre de grandeur, lui, est stable d'une source à l'autre.

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²) à O(n) sur un million d'enregistrements ne divise pas la facture par deux : il la divise par un facteur de l'ordre du million. Aucune action sur le refroidissement d'un centre de données n'atteint ce rapport.
Corollaire moins confortable : allonger la durée de vie du matériel pèse souvent davantage que le code, puisque la fabrication domine. Un algorithme efficace permet de garder un serveur plus longtemps, c'est par là que l'optimisation rejoint l'essentiel.

Quelques pratiques, du plus au moins efficace :

Choisir le bon algorithme et la bonne structure de données. C'est 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.

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.
C'est ce qui donne son sens au problème du 2-sum : apparier des surplus de production avec des demandes suppose de 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.

Exercices type

Donner la complexité de deux boucles imbriquées où la seconde va de $i$ à $n$

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 : imbriquer à partir de $i$ 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)$ et $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.

Refais le calcul pour 1 000 000 d'éléments : $O(n)$ donne 1 000 s (17 minutes), $O(n^2)$ donne 10⁶ 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 taux de remplissage tenu sous contrôle par redimensionnement, le coût amorti reste $O(1)$ .

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 : les constantes multiplicatives, les termes d'ordre inférieur, le cache du processeur (une petite structure y tient entièrement, une grande non), le ramasse-miettes, et le bruit de mesure du système.

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 industriels basculent sur un tri par insertion en dessous d'une quinzaine d'éléments.

La méthode

Nomme $n$ en toute première ligne. «  $n$ = nombre de relevés », sans cela, la complexité ne veut rien dire.
Compte les opérations élémentaires, boucle par boucle, en identifiant celle qui domine.
Précise le cas : pire, moyen ou meilleur. Par défaut, le pire.
Écris $O$ pour une majoration, $\Theta$ quand tu as l'encadrement.
Prouve quand on te le demande : exhibe un $n_0$ et un $k$ , c'est tout ce qu'exige la définition.
Donne aussi la complexité spatiale. Un gain de temps payé en mémoire est un compromis, pas un progrès automatique.
Confronte à la mesure : trace en log-log, lis la pente, compare à l'exposant théorique.
Conclus en énergie quand le sujet est le Green IT : un facteur de complexité est un facteur sur la consommation.

En résumé

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)$ .
Réflexe du doublement : $O(n)$ double, $O(n^2)$ quadruple, $O(2^n)$ est élevé au carré.
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 inférieure ; celle d'un algorithme se lit dans le code.
Table de hachage : $O(1)$ en moyenne, $O(n)$ en cas de collisions massives.
2-sum : $O(n^2)$ brute, $O(n \log n)$ par tri, $O(n)$ par hachage, qui atteint l'optimum du problème.
Dans un enchaînement, l'étape la plus coûteuse fixe le total.
En log-log, la pente estime l'exposant réel.
Green IT : le bon algorithme est le premier levier de sobriété, et il prolonge la vie du matériel.

Et ensuite ? Le 2-sum se contentait d'une liste de nombres. Le dernier problème du bloc porte sur des données qui ont une structure de relations, quelles tâches se chevauchent, quels serveurs peuvent les partager. C'est l'objet de la théorie des graphes.

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 : O(n2)O(n^2)O(n2) en temps, O(1)O(1)O(1) en espace

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

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

Théorie contre mesure

Green IT

Exercices type

La méthode

En résumé

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

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

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