Explication de la complexité temporelle et spatiale d’un algorithme
Imaginez deux programmes qui effectuent exactement la même tâche. Donnez-leur mille enregistrements et vous ne pourrez pas les distinguer. Donnez-leur un milliard, en revanche, et l'un aura terminé avant même que vous ayez relâché la touche Entrée, tandis que l'autre sera encore en train de travailler mardi prochain.
Même ordinateur portable. Mêmes données. Ce qui les différencie, c'est la complexité temporelle, c'est-à-dire la vitesse à laquelle la charge de travail d'un algorithme augmente à mesure qu'on lui fournit davantage d'entrées.
Nous allons examiner la signification de ce terme, la notation Big O qui le représente, son application à un exemple concret de code et le rôle de la complexité spatiale. Enfin, nous verrons comment tout cela passe du statut de simple exercice à celui d'application concrète : les contrats intelligents.
Qu'est-ce que la complexité temporelle d'un algorithme ?
Oubliez un instant les secondes. La complexité temporelle compte les étapes. Comparaisons, affectations, un peu d'arithmétique ici et là, et vous exprimez le total en fonction de n, qui représente la taille de l'entrée.
Voici sans doute la fonction la plus ennuyeuse qui soit :
python def print_all(items): for item in items: print(item)
Dix articles ? Dix allers-retours. Dix mille ? Dix mille allers-retours.
Le travail monte en ligne droite à côté de l'entrée, nous l'appelons donc O(n).
Bon, peut-être que chaque déplacement coûte en réalité trois petites opérations au lieu d'une. Très bien, ça fait 3n. Franchement, personne ne s'en soucie, car doubler la liste double toujours le travail, et c'est cette courbe de croissance qui nous intéresse. On omet volontairement le chiffre exact.
C'est aussi pourquoi tous les cours de structures de données et d'algorithmes, ainsi que la moitié des entretiens techniques, insistent lourdement sur la complexité temporelle. Si vous pouvez évaluer la complexité d'un algorithme d'un simple coup d'œil, vous pouvez deviner son comportement sur des données d'entrée que vous n'avez jamais eu l'occasion de tester. Ce qui, en production, représente la majeure partie des données.
Pourquoi le temps d'exécution est un mauvais indicateur de la performance d'un algorithme
Alors pourquoi ne pas simplement utiliser un minuteur ? Beaucoup le font, et je comprends. Le problème, c’est que le temps d’exécution engendre une multitude de problèmes qui n’ont rien à voir avec votre algorithme :
- Matériel. Mon ordinateur portable de cinq ans et un boîtier cloud flambant neuf donneront des résultats complètement différents pour le même script.
- Langage de programmation. Écrivez la même boucle en C et en Python et vous constaterez peut-être un écart de 10 fois, voire plus.
- Charge système. Une mise à jour en arrière-plan se lance, le ramasse-miettes s'active, le cache est vide. Votre résultat est déplacé.
- Peu importe les données que vous avez saisies. Un tri ultra-rapide sur des données presque triées peut être extrêmement lent sur des données mélangées.
Un chronomètre vous donne une mesure pour une seule opération, une seule entrée. Demandez-lui une mesure 100 fois plus importante et il ne pourra rien faire.
Le nombre d'étapes est constant. Même algorithme, mêmes données d'entrée, et le nombre d'étapes reste le même, que ce soit Rust sur un serveur rack ou JavaScript sur un téléphone. C'est pourquoi la complexité temporelle est un critère de comparaison équitable entre deux solutions avant même d'avoir effectué des tests de performance. Je recommande tout de même d'effectuer des tests après coup, cela dit. C'est simplement une autre question.
Explication de la notation grand O et autres notations asymptotiques
Les manuels appellent cela la notation asymptotique, ce qui paraît plus compliqué qu'en réalité. On laisse n devenir très grand et on néglige les petites valeurs ; les multiplicateurs constants et les valeurs d'entrée infimes disparaissent, et seule la courbe de croissance subsiste. Il y en a trois qu'il est important de connaître :
| Notation | Ce que cela décrit | Signification littérale | Exemple |
|---|---|---|---|
| Grand O, O(f(n)) | Limite supérieure | L'algorithme ne croît pas plus vite que f(n). | La recherche linéaire est O(n). |
| Grand-Omega, Ω(f(n)) | limite inférieure | L'algorithme nécessite au moins f(n) de travail | Tout tri par comparaison est Ω(n log n) |
| Grand-Theta, Θ(f(n)) | Reliure serrée | Les limites supérieure et inférieure correspondent | Le tri fusion est Θ(n log n) |
En pratique, vous entendrez la notation Big O environ 95 % du temps. Elle définit une limite supérieure, ce qui signifie que le temps d'exécution ne dépassera pas le taux entre parenthèses. Lors de ma première revue de code dans un vrai emploi, un développeur senior a écrit « O(n²), veuillez corriger » à côté d'une boucle imbriquée. Il voulait dire que la complexité temporelle dans le pire des cas était quadratique et que la liste allait s'allonger considérablement.
Omega et Theta sont principalement utilisés dans les cours universitaires d'analyse des algorithmes, et je ne pense pas les avoir utilisés au travail depuis des années. Big O l'emporte car il répond à la question que l'on se pose réellement en réunion : « Quelle sera l'impact si le trafic triple ? »
Il y a un détail technique qui m'a un peu perturbé. Puisque la notation grand O ne représente qu'un plafond, une fonction O(n) est aussi O(n²), à proprement parler, de la même façon qu'une personne mesurant 1,52 m est « moins de 2,13 m ». C'est vrai, mais inutile. Chacun cite la borne la plus restrictive qu'il peut justifier, et je ferai de même.
Classes de complexité temporelle courantes avec exemples
Vous ne rencontrerez pas tant de classes dans du code réel, peut-être sept si l'on compte les plus complexes. Voici approximativement leur coût pour n = 1 000 :
| Classe | Nom | Exemple typique | Opérations à n = 1 000 |
|---|---|---|---|
| O(1) | Constante | Index de tableau, recherche dans une table de hachage | 1 |
| O(log n) | logarithmique | Recherche binaire | ~10 |
| Sur) | Linéaire | Parcourir une liste | 1 000 |
| O(n log n) | Linéaire-ithmique | Tri fusion, tri rapide (moyenne) | ~10 000 |
| O(n²) | Quadratique | Boucles imbriquées, tri à bulles | 1 000 000 |
| O(2ⁿ) | Exponentiel | Fibonacci récursif naïf | Plus que des atomes dans l'univers |
| Sur!) | Factorielle | vendeur itinérant par force brute | Encore plus grand |
O(1) : Temps constant
Que votre dictionnaire Python contienne dix clés ou dix millions, extraire une clé coûte à peu près la même chose, tout comme lire `items[5]` dans une liste. Cette platitude est le principe même du temps d'exécution constant.
O(log n) : Temps logarithmique
Je les vois comme des algorithmes du type « devinez le nombre entre 1 et 100 », où chaque tentative élimine la moitié des résultats possibles. La recherche binaire fonctionne exactement de cette manière sur une liste triée.
Python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
Avec un milliard d'éléments triés, il faut environ 30 comparaisons, alors que les examiner un par un pourrait prendre le milliard entier, et je n'ai jamais cessé de trouver ça drôle.
O(n) et O(n log n)
Un algorithme linéaire parcourt chaque élément un nombre fixe de fois, comme si vous cherchiez visuellement le plus grand nombre dans une colonne d'un tableur. La complexité O(n log n) est celle des algorithmes de tri performants. Le tri fusion divise la liste en éléments individuels (log n niveaux de division) puis effectue un passage linéaire par niveau lors de la fusion ; son temps d'exécution reste donc constant, que les données arrivent triées ou mélangées.
O(n²) et pire
Le code quadratique comporte presque toujours une boucle imbriquée dans une autre, comme cette vérification de doublons qui compare chaque paire :
Python def has_duplicate(items): for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return False
La croissance exponentielle et factorielle est bien pire. La suite de Fibonacci récursive classique résout sans cesse les mêmes sous-problèmes, si bien que chaque augmentation de n double approximativement la charge de travail. Pour n = 20, cela passe inaperçu ; pour n = 60, vous pourriez préparer le dîner, le manger, faire la vaisselle, et ce ne serait toujours pas terminé.
Comment calculer la complexité temporelle étape par étape
Il est presque toujours inutile de fournir une preuve formelle pour calculer la complexité temporelle. Je passe mentalement en revue cette liste, qui couvre la plupart des codes que je vois :
- Définissez n. Déterminez la taille de l'entrée : la longueur d'une liste, le nombre de nœuds dans un graphe, le nombre de chiffres dans un nombre.
- Comptez le travail effectué sur chaque ligne. Les instructions simples (affectations, comparaisons, arithmétiques) ont un coût O(1).
- Ajoutez des blocs séquentiels. Deux boucles l'une après l'autre, chacune sur n, donnent n + n = 2n.
- Multiplier les blocs imbriqués. Une boucle sur n à l'intérieur d'une autre boucle sur n donne n × n = n².
- Supprimez les constantes. 2n devient n, et 500 devient 1.
- Ne conservez que le terme dominant. Dans n² + n, la partie n² devient prépondérante par rapport aux autres lorsque n augmente.
Calcul rapide. On obtient T(n) = 3n² + 5n + 2. Arrondissons à un million : 3n² vaut trois billions, 5n vaut cinq millions. Erreur d'arrondi. On appelle la complexité O(n²), et c'est tout.
Les boucles qui sautent d'un élément à l'autre au lieu de passer d'un élément à l'autre sont plus sournoises :
Python def count_halvings(n): steps = 0 while n > 1: n //= 2 steps += 1 return steps
Chaque itération divise n par deux, donc cette boucle while s'arrête après environ log₂(n) itérations. C'est en résumé la réponse à la question « quand la complexité temporelle est-elle O(log n) ? » Si la valeur restante diminue d'un facteur constant à chaque étape, alors vous y êtes.
La récursivité nécessite un outil supplémentaire : une récurrence. Le tri fusion effectue deux opérations de taille réduite puis une fusion, donc T(n) = 2T(n/2) + n. Le théorème maître est un guide pratique pour les récurrences de cette forme, et pour celle-ci, il donne O(n log n).
Une règle empirique de la programmation compétitive que j'utilise souvent : une machine classique effectue environ 10⁸ opérations simples par seconde. C'est une approximation, mais suffisante pour vérifier la complexité temporelle d'une solution avant de la soumettre. Avec n = 10⁵, O(n²) correspond à environ 10¹⁰ opérations, donc le temps est dépassé. O(n log n) est inférieur à 2 millions. C'est parfait.
Analyse des scénarios les plus défavorables, les plus favorables et les plus favorables
Si on alimente un même algorithme avec des données d'entrée différentes, la charge de travail peut varier énormément. La recherche linéaire l'illustre bien :
- Dans le meilleur des cas, ce que vous voulez est juste devant. Une seule comparaison et c'est éliminé.
- Dans le pire des cas : il se trouve à la toute fin, ou n'existe pas du tout. C'est incomparable.
- Cas moyen : si la probabilité est la même partout, on vérifie en moyenne environ n/2 fois. Cela reste O(n), notez-le.
Interrogez un développeur sur la « complexité » d'un projet et il vous donnera presque toujours la complexité temporelle dans le pire des cas, car ce chiffre est une garantie sur laquelle vous pouvez vous baser pour planifier.
Supposons que votre API traite une requête en O(n) au pire. Parfait ! Vous savez maintenant comment se comporte la requête la plus lente et vous êtes protégé(e) si quelqu'un vous envoie intentionnellement des données erronées. Cela arrive fréquemment : si un attaquant découvre les clés provoquant une collision dans votre table de hachage, ce seront les seules clés auxquelles vous aurez accès pendant un certain temps.
Il est intéressant d'examiner le cas moyen, car le scénario défavorable est rare. L'algorithme Quicksort en est l'exemple type : sa complexité moyenne est de O(n log n), mais elle peut chuter à O(n²) si l'on choisit naïvement les pivots sur des données déjà triées. Les bibliothèques standard contournent ce problème en utilisant des pivots aléatoires ou en changeant d'algorithme de tri lorsque la récursion atteint une profondeur suspecte.
Qu’est-ce que la complexité spatiale et l’espace auxiliaire ?
La mémoire représente l'autre coût d'un algorithme. La complexité spatiale mesure la quantité de mémoire nécessaire en fonction de la taille des données d'entrée, et s'exprime avec la même notation Big O que la complexité temporelle.
Une partie de cette mémoire correspond aux données d'entrée elles-mêmes, que vous payez quoi que vous fassiez. La partie que vous contrôlez réellement s'appelle l'espace auxiliaire ; il s'agit des ressources supplémentaires allouées par votre code pendant son exécution, comme les variables temporaires et les nouveaux tableaux, ainsi que la pile d'appels dont on ne se souvient que lorsqu'elle nous cause des problèmes.
Quelques cas rapides :
- L'échange de deux variables nécessite quelques emplacements indépendamment de tout le reste, il s'agit donc d'un espace auxiliaire O(1).
- Copier une liste de n éléments dans une nouvelle liste vous coûte O(n) de mémoire supplémentaire.
- Une récursion de n niveaux de profondeur laisse n cadres sur la pile, ce qui représente un espace O(n) même si vous n'avez jamais construit de tableau.
J'ai vu un développeur junior perdre tout un après-midi à cause de ce problème. Sa fonction récursive semblait n'utiliser aucune mémoire, mais chaque appel inachevé était mis en attente sur la pile, attendant le retour des appels plus profonds. Avec une entrée importante, tout a planté à cause d'un dépassement de capacité de la pile.
De nombreuses optimisations consistent simplement à échanger de la mémoire contre du temps, ou inversement. La mémoïsation met en cache les résultats déjà calculés, ce qui permet de réduire la complexité temporelle de la suite de Fibonacci de O(2ⁿ) à O(n) en échange d'une consommation mémoire de O(n). Les tables de hachage permettent d'obtenir des accès en O(1) en moyenne en allouant de l'espace à des compartiments. Sur un serveur doté de 64 Go de RAM, cet échange est généralement évident, mais sur un microcontrôleur ou au sein d'un contrat intelligent, il convient d'y réfléchir à deux fois.
Complexité temporelle et spatiale des structures de données courantes
Choisir la structure de données appropriée est généralement plus judicieux que de peaufiner le code de votre boucle. Voici les coûts moyens des structures les plus fréquemment utilisées :
| structure de données | Accéder | Recherche | Insérer | Supprimer | Espace |
|---|---|---|---|---|---|
| Tableau | O(1) | Sur) | Sur) | Sur) | Sur) |
| Liste chaînée | Sur) | Sur) | O(1) | O(1) | Sur) |
| Table de hachage | n / A | O(1) | O(1) | O(1) | Sur) |
| Arbre binaire de recherche équilibré | O(log n) | O(log n) | O(log n) | O(log n) | Sur) |
| Tas binaire | O(1) pour min/max | Sur) | O(log n) | O(log n) | Sur) |
Deux remarques importantes : les insertions et suppressions dans une liste chaînée sont en O(1) uniquement si le nœud est déjà en votre possession. Quant à une table de hachage, sa complexité peut atteindre O(n) en cas de nombreuses collisions de clés.
Les algorithmes de tri varient tout autant :
| Algorithme de tri | Meilleur | Moyenne | Pire | Espace auxiliaire |
|---|---|---|---|---|
| Tri à bulles | Sur) | O(n²) | O(n²) | O(1) |
| Tri fusion | O(n log n) | O(n log n) | O(n log n) | Sur) |
| Tri rapide | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Tri par tas | O(n log n) | O(n log n) | O(n log n) | O(1) |
Le tri fusion est prévisible mais gourmand en mémoire. Le tri par tas trie sur place et conserve le même résultat dans le pire des cas. Le tri rapide, malgré un plafond moins avantageux, s'avère généralement plus performant en pratique.
Complexité temporelle dans la blockchain et les contrats intelligents
C'est là que ça devient intéressant. Sur votre propre serveur, un algorithme mal conçu gaspille des ressources CPU et peut agacer un utilisateur. Sur Ethereum ou toute chaîne EVM, il engendre des frais. Chaque opération exécutée par un contrat intelligent coûte du gaz, payé en gas, la cryptomonnaie native de la chaîne. Ainsi, le nombre de vos opérations apparaît comme une ligne sur la facture de quelqu'un. En d'autres termes, une mauvaise complexité temporelle a un coût.
Imaginez un contrat qui parcourt chaque détenteur de jetons pour distribuer les récompenses. La complexité est O(n), et les frais de gaz augmentent avec chaque nouveau détenteur. Le jour du lancement, personne ne s'en aperçoit.
La liste des détenteurs ne cesse alors de s'allonger. Un jour, le paiement nécessite plus de gaz que la limite de gaz par bloc, qui correspond à la quantité maximale de gaz qu'un seul bloc peut contenir. Dès lors, la transaction est impossible. Il ne s'agit pas d'un simple ralentissement : elle échoue systématiquement, et les fonds en attente sont bloqués. Les auditeurs classent ces boucles infinies comme des attaques par déni de service, et c'est tout à fait justifié.
Les solutions relèvent de la pensée complexe, tout simplement :
- Répartissez le travail en lots de taille fixe sur plusieurs transactions.
- Inversez le système pour que chaque utilisateur réclame sa propre récompense. Chaque appel est O(1).
- Remplacez la boucle par une épreuve Merkle.
J'adore les preuves de Merkle, car elles illustrent parfaitement l'importance du logarithme népérien (log n) sur la blockchain. Un arbre de Merkle hache un grand volume de données en un seul hachage racine.
Pour prouver qu'une entrée appartient à un ensemble de n éléments, il faut environ log₂(n) hachages. Pour un million d'entrées, cela représente environ 20 hachages, et non un million. Les airdrops s'appuient sur ce principe, et les portefeuilles Bitcoin légers utilisent la même technique pour confirmer une transaction sans télécharger le bloc entier.
Hors chaîne, même principe. Imaginez un système de paiement qui associe chaque transaction blockchain entrante à une facture en analysant toutes les factures ouvertes. La complexité est de O(n) par paiement, et elle augmente avec la taille de l'entreprise. En revanche, si vous stockez les factures dans une table de hachage indexée par adresse ou identifiant, chaque correspondance est en O(1). Et si vous préférez ne pas développer et gérer vous-même cette infrastructure, une passerelle de paiement crypto comme Plisio s'en charge.
