Algorithmes et structures de données : repères 2026 pour devs

Tout développeur ouvre un jour son premier projet sérieux et tombe sur une fonction qui rame. La page met huit secondes à se charger, l’API renvoie un timeout, le batch nocturne ne finit plus avant l’arrivée de l’équipe. Neuf fois sur dix, le coupable n’est pas le serveur ni la base : c’est un algorithme inadapté, ou une structure de données mal choisie. Trier un million d’éléments avec une boucle imbriquée, chercher un client par un parcours linéaire alors qu’un dictionnaire ferait l’affaire, recalculer le même résultat dans chaque itération d’une boucle — voilà les vraies sources de lenteur. Cet article fait le tour des notions et des outils que tout développeur doit comprendre pour écrire du code qui tient la charge, et il sert de point d’entrée vers les tutoriels d’implémentation pas à pas.

Pourquoi les algorithmes restent décisifs en 2026

L’argument classique consiste à dire que le matériel est devenu si rapide que la complexité algorithmique compte moins qu’avant. C’est faux. Les processeurs ont gagné en parallélisme, pas en vitesse mono-cœur : un cœur Intel Core de 2026 tourne autour de 5 GHz, soit le même ordre de grandeur qu’un Core 2 Duo de 2008. Ce qui a changé, c’est la quantité de données. Une requête SQL qui balayait 10 000 lignes en 2008 en balaye 10 millions en 2026, et l’écart entre une recherche linéaire en O(n) et une recherche logarithmique en O(log n) y devient brutal — on parle de quelques millisecondes contre plusieurs secondes.

Les frameworks modernes masquent cette réalité. React, Django, Spring Boot s’occupent du gros œuvre, et le développeur croit qu’il suffit de connaître l’API. Jusqu’au jour où il faut comprendre pourquoi useEffect déclenche une boucle infinie, pourquoi un JOIN sur deux grosses tables s’effondre, pourquoi un Lambda AWS dépasse son timeout. Toutes ces questions se résolvent en raisonnant sur les structures de données sous-jacentes — tableau, dictionnaire, arbre, graphe — et sur le coût des opérations qu’on leur applique. La maîtrise des algorithmes n’est pas un savoir académique réservé aux entretiens FAANG : c’est l’outil quotidien qui distingue un développeur autonome d’un développeur qui colle des bouts de Stack Overflow.

Les concepts fondamentaux à maîtriser

La notation Big-O et la pensée asymptotique

La notation Big-O décrit la croissance du temps d’exécution (ou de l’espace mémoire) en fonction de la taille de l’entrée. Quand on dit qu’un algorithme est en O(n), cela signifie que doubler la taille de l’entrée double approximativement le temps. En O(n²), doubler la taille quadruple le temps. En O(log n), doubler la taille n’ajoute qu’une constante. Et en O(1), le temps ne dépend pas du tout de la taille — c’est l’idéal qu’on vise pour les opérations critiques.

Concrètement, voici l’échelle qu’il faut avoir en tête : pour n = 1 000 000, un algorithme en O(n) traite l’entrée en environ une seconde sur une machine moderne, un O(n log n) en quelques secondes, un O(n²) en plusieurs heures, et un O(2ⁿ) ou O(n!) ne finit jamais. C’est cette échelle qui explique pourquoi le choix d’un algorithme adapté change tout. Une boucle imbriquée innocente sur deux listes de 100 000 éléments fait 10 milliards d’opérations — ce n’est pas du code lent, c’est du code qui ne finira pas dans la journée.

Les structures linéaires : tableau et liste chaînée

Le tableau (en Python : la list, en C : int arr[]) stocke ses éléments dans un bloc de mémoire contigu. L’accès par index est en O(1) parce qu’on calcule l’adresse en mémoire par une simple multiplication. En revanche, insérer un élément au début coûte O(n) : il faut décaler tous les autres. Côté Python, la list est en réalité un tableau dynamique — CPython sur-alloue au moment du redimensionnement avec un facteur d’environ 1,125, ce qui rend l’append en O(1) amorti, malgré les redimensionnements ponctuels en O(n).

La liste chaînée propose le compromis inverse. Chaque nœud contient une donnée et un pointeur vers le suivant, donc insérer en tête est en O(1) trivial : on crée le nouveau nœud, on fait pointer son next vers l’ancienne tête, et on remplace la tête. En revanche, accéder au n-ième élément coûte O(n) parce qu’il faut suivre la chaîne. Le choix entre tableau et liste chaînée n’est donc pas une question de mode : c’est une question de profil d’utilisation. Beaucoup d’accès aléatoires par index ? Tableau. Beaucoup d’insertions en milieu de liste avec un pointeur déjà acquis ? Liste chaînée.

Les structures associatives : dictionnaire et table de hachage

La table de hachage est probablement la structure la plus utilisée dans le code moderne, sans que beaucoup de développeurs sachent ce qu’il y a dessous. En Python, dict est implémenté avec adressage ouvert : la clé est passée à une fonction de hachage (SipHash13 pour les chaînes depuis Python 3.11) qui produit un index dans un tableau interne. Si l’index est libre, la paire (clé, valeur) y est stockée ; sinon, l’algorithme sonde les positions suivantes selon une stratégie déterministe jusqu’à trouver une case libre. CPython redimensionne la table dès que le facteur de charge dépasse 2/3, ce qui maintient les opérations en O(1) en moyenne.

L’intuition à retenir : si vous avez besoin de chercher des éléments par une clé naturelle (un identifiant, un nom de variable, une URL), un dictionnaire ramène la recherche à O(1) là où une boucle sur une liste serait en O(n). Cette transformation simple est probablement l’optimisation qui a sauvé le plus de projets web dans l’histoire. Le tutoriel pas à pas Coder une table de hachage en Python dans cette série montre comment l’implémenter de zéro, en passant par les détails sales : collisions, sondage linéaire, redimensionnement, fonction de hachage maison.

Les structures hiérarchiques : pile, file et arbre

La pile (LIFO — dernier entré, premier sorti) sous-tend tout ce qui ressemble à une exécution imbriquée : les appels de fonction, l’évaluation d’expressions, le retour arrière dans un parcours. La file (FIFO — premier entré, premier sorti) modélise les attentes : tâches d’un worker, paquets réseau, événements à traiter. Les deux sont triviales à implémenter sur un tableau dynamique ou sur une liste chaînée. En Python, on utilise collections.deque qui offre des opérations en O(1) aux deux extrémités, là où list.pop(0) serait en O(n).

L’arbre généralise la liste chaînée à plusieurs branches. L’arbre binaire de recherche stocke les données dans un ordre qui permet une recherche en O(log n) en moyenne, à condition que l’arbre reste équilibré. Quand il ne l’est plus — insertions toujours croissantes — il dégénère en liste chaînée et la recherche retombe à O(n). Les arbres équilibrés (AVL, rouge-noir, B-tree) résolvent ce problème en réorganisant la structure à chaque opération. PostgreSQL et MySQL, par exemple, utilisent des B-trees pour leurs index, ce qui garantit des recherches logarithmiques même sur des tables de plusieurs milliards de lignes.

Les graphes : la structure des relations

Un graphe est un ensemble de sommets reliés par des arêtes. Cette définition simple modélise une variété énorme de problèmes : un réseau social (sommets = utilisateurs, arêtes = amitiés), une carte routière (sommets = villes, arêtes = routes avec un poids), un graphe de dépendances (sommets = paquets, arêtes = imports). Les deux représentations canoniques sont la matrice d’adjacence (un tableau de booléens V × V, simple mais gourmand en mémoire pour les graphes peu denses) et la liste d’adjacence (un tableau où chaque sommet pointe vers la liste de ses voisins, plus compact dans le cas général).

Les deux algorithmes de parcours qu’il faut connaître par cœur sont le parcours en largeur (BFS) et le parcours en profondeur (DFS). Tous deux s’exécutent en O(V + E) sur une liste d’adjacence, où V est le nombre de sommets et E le nombre d’arêtes. Le BFS sert à trouver le plus court chemin en nombre d’arêtes — c’est ce que fait, en simplifiant, l’algorithme qui compte les degrés de séparation sur LinkedIn. Le DFS sert pour la détection de cycles, le tri topologique, ou la recherche de composantes connexes. Le tutoriel Implémenter le parcours BFS sur un graphe dans cette série montre l’implémentation complète avec une file et un ensemble de visités.

Vue d’ensemble des algorithmes classiques

Trier : du tri à bulles à Powersort

Le tri est probablement le problème algorithmique le plus étudié de toute l’histoire de l’informatique. Les tris naïfs (insertion, sélection, à bulles) sont en O(n²) et ne tiennent que sur des entrées petites — quelques dizaines d’éléments. Les tris efficaces (fusion, tri rapide, tri par tas) sont en O(n log n), ce qui est la borne théorique pour un tri par comparaison. Le tri rapide, inventé par Tony Hoare en 1959 et publié en juillet 1961 dans Communications of the ACM, reste la référence pratique : il a en moyenne O(n log n) avec des constantes très basses, mais peut dégénérer en O(n²) sur certaines entrées si le pivot est mal choisi.

En 2026, la fonction sorted() de Python n’utilise ni quicksort ni mergesort directement. Depuis la version 2.3, elle utilisait Timsort, un hybride développé par Tim Peters en 2002 qui exploite les sous-séquences déjà triées dans l’entrée. Depuis Python 3.11, sortie en octobre 2022, l’algorithme a été remplacé par Powersort, une variante de Timsort avec une politique de fusion plus robuste qui garantit des bornes théoriques meilleures. Pour comprendre les mécanismes du partitionnement par pivot, le tutoriel Programmer le tri rapide en Python dans cette série implémente quicksort de zéro, avec le choix du pivot et l’analyse de la pile d’appels.

Chercher : recherche linéaire et recherche dichotomique

Chercher un élément dans une liste non triée coûte O(n) au pire cas. Si la liste est triée, la recherche dichotomique (ou binaire) ramène le coût à O(log n) en divisant l’intervalle de recherche par deux à chaque étape. Pour 1 million d’éléments, c’est la différence entre 1 million de comparaisons et 20. La condition est forte cependant : il faut que la structure soit triée et permette l’accès aléatoire en O(1) — donc un tableau, pas une liste chaînée. Le module standard bisect de Python propose une recherche dichotomique optimisée que tout développeur Python devrait connaître.

Quand on cherche par clé dans une structure adaptée — dictionnaire, ensemble, table de hachage — le coût retombe à O(1) en moyenne. C’est pour cette raison qu’on transforme souvent une liste en dictionnaire au début d’un traitement : payer une fois le coût O(n) de construction pour ensuite faire des milliers de lookups en O(1). Cette transformation est l’astuce d’optimisation la plus rentable du quotidien, devant la mise en cache et l’élimination des appels redondants.

Algorithmes sur les graphes

Au-delà de BFS et DFS, deux algorithmes méritent d’être connus pour la culture générale du métier. Dijkstra calcule les plus courts chemins depuis une source dans un graphe avec des poids positifs ; sa complexité avec un tas binaire est en O((V + E) log V). C’est l’algorithme derrière les calculs d’itinéraires sur Google Maps, en version très optimisée. Et le tri topologique, qui ordonne les sommets d’un graphe orienté acyclique pour que chaque arête aille de gauche à droite, sert dans les systèmes de build (Make, Bazel), dans la résolution de dépendances de paquets (npm, pip), et dans les pipelines de tâches (Airflow).

Diviser pour régner, programmation dynamique, glouton

Trois grandes familles de stratégies algorithmiques structurent la majorité des solutions efficaces. Diviser pour régner consiste à découper le problème en sous-problèmes indépendants, les résoudre récursivement, puis combiner les résultats. Le tri fusion et le tri rapide en sont les exemples canoniques. La programmation dynamique mémorise les résultats intermédiaires pour éviter de les recalculer ; elle convient quand les sous-problèmes se chevauchent, comme dans le calcul de la distance d’édition entre deux chaînes ou le problème du sac à dos. Les algorithmes gloutons font à chaque étape le choix qui paraît localement optimal, sans revenir en arrière ; ils sont rapides mais ne donnent pas toujours l’optimum global — il faut prouver qu’ils le donnent pour le problème considéré.

Tutoriels de la série

Pour chaque structure ou algorithme ci-dessous, un tutoriel pas à pas est disponible. L’ordre suggéré commence par les structures linéaires, monte vers les structures associatives, puis enchaîne sur les algorithmes classiques.

• Liste chaînée en Python — implémentation pas à pas avec insertion, suppression, parcours, et la classe Node minimale qu’il faut écrire avant tout reste.
• Table de hachage en Python — construction d’un dictionnaire de zéro avec adressage ouvert, fonction de hachage maison, gestion des collisions et redimensionnement.
• Tri rapide (quicksort) en Python — partition de Hoare, choix du pivot, version récursive et version itérative, analyse du pire cas.
• Parcours BFS sur un graphe en Python — représentation du graphe en liste d’adjacence, parcours avec une deque, calcul du plus court chemin en nombre d’arêtes.

Comment choisir une structure de données dans la vraie vie

La théorie ne suffit pas — il faut un raisonnement applicable au moment où vous écrivez le code. La grille à utiliser est simple : pour chaque opération que vous allez faire fréquemment dans votre boucle chaude, demandez-vous quelle est sa complexité avec la structure que vous envisagez. Si vous insérez beaucoup et lisez peu, une liste chaînée ou un tableau dynamique conviennent. Si vous lisez par clé, c’est un dictionnaire. Si vous voulez le minimum ou le maximum à chaque tour, c’est un tas (file de priorité). Si vous gérez des relations un-à-plusieurs avec parcours, c’est un graphe en liste d’adjacence.

Le piège classique consiste à choisir la structure par habitude plutôt que par profil d’usage. Beaucoup de développeurs utilisent list partout en Python parce que c’est ce qu’ils connaissent. Or pour 100 000 vérifications d’appartenance, x in liste coûte 100 000 × O(n), tandis que x in ensemble coûte 100 000 × O(1). Sur un million d’éléments, on passe de plusieurs minutes à quelques millisecondes par un simple set(...). Cette différence est invisible dans un test unitaire avec dix éléments, et catastrophique en production.

Erreurs fréquentes à éviter

Erreur	Cause	Solution
Boucle imbriquée sur deux grandes listes	Recherche linéaire dans la boucle interne	Pré-construire un dictionnaire ou un ensemble pour ramener la recherche à O(1)
list.pop(0) dans une boucle de file d’attente	list.pop(0) est en O(n) en Python	Utiliser collections.deque avec popleft() en O(1)
Concaténation de chaînes par += dans une boucle	Crée une nouvelle chaîne à chaque itération — O(n²) au total	Accumuler dans une liste et finir par "".join(liste)
Recherche par clé dans une liste de tuples	Boucle linéaire à chaque appel	Construire un dict en début de fonction
Tri à chaque comparaison	Trier dans une boucle qui s’exécute n fois — O(n² log n)	Trier une fois avant la boucle
Récursion sans mémoïsation	Recalcul exponentiel des mêmes sous-problèmes (Fibonacci naïf)	@functools.cache ou table de mémoïsation explicite

Outils pour profiler et mesurer

Avant d’optimiser, il faut mesurer. Le module standard cProfile de Python donne une vue par fonction du temps cumulé et du nombre d’appels — c’est la première chose à lancer sur un script lent. timeit mesure précisément le temps d’une expression isolée, utile pour comparer deux implémentations. line_profiler (paquet externe pip install line-profiler) descend à la ligne et révèle souvent qu’une seule ligne consomme 90 % du temps. Pour la mémoire, tracemalloc intégré à la stdlib trace les allocations.

L’erreur classique consiste à optimiser à l’aveugle, en se fiant à l’intuition. Cette intuition trompe presque toujours. La règle de Donald Knuth tient encore : premature optimization is the root of all evil — mais une fois la mesure faite, l’optimisation guidée par les données se justifie pleinement. Profiler avant, comparer après, garder le code lisible.

Foire aux questions

Faut-il connaître les algorithmes par cœur pour passer un entretien technique ?

Cela dépend de l’entreprise. Les grandes structures (Google, Meta, Amazon, et leurs équivalents européens) testent encore systématiquement les algorithmes classiques sur LeetCode-like. Beaucoup de PME et startups privilégient désormais les exercices proches de la stack réelle. Dans tous les cas, comprendre les structures de données reste indispensable pour éviter d’écrire du code lent, bien au-delà de l’entretien.

Quelle est la différence entre algorithme et structure de données ?

Une structure de données est une manière d’organiser des informations en mémoire (tableau, dictionnaire, arbre). Un algorithme est une suite d’étapes pour résoudre un problème (trier, chercher, parcourir un graphe). Les deux sont liés : un algorithme efficace exploite la bonne structure, et une structure n’a d’intérêt que par les opérations qu’elle permet. Un livre de référence comme Introduction to Algorithms de Cormen, Leiserson, Rivest et Stein (CLRS) couvre les deux ensemble.

O(log n) ou O(n) sur une recherche : la différence est-elle vraiment visible ?

Sur 1 000 éléments, presque pas. Sur 1 milliard, c’est 30 comparaisons contre 1 milliard. Aujourd’hui, beaucoup de tables et d’index dépassent ces tailles. Quand votre code travaille sur des entrées qui peuvent grossir en production, raisonner en complexité asymptotique n’est plus un luxe.

Faut-il implémenter ses propres structures de données dans du code de production ?

Non, presque jamais. La list de Python, HashMap de Java, std::vector de C++ sont écrits par des dizaines d’experts et optimisés pour l’architecture moderne. Les implémenter à la main sert à comprendre ce qu’il y a sous le capot, à mieux choisir entre les structures existantes, et à intervenir quand la stdlib n’a pas la bonne primitive (par exemple un tas avec mise à jour des priorités). Les tutoriels de cette série font cet exercice pédagogique, ce qui ne signifie pas qu’il faut copier ces classes en production.

Quels sont les meilleurs livres pour approfondir ?

Trois références couvrent l’essentiel. Introduction to Algorithms (CLRS) est la bible académique, exigeante mais complète. The Algorithm Design Manual de Steven Skiena est plus pratique, avec des études de cas. Algorithms de Robert Sedgewick et Kevin Wayne, qui accompagne le cours en ligne de Princeton, équilibre théorie et code. Pour un démarrage doux, Grokking Algorithms d’Aditya Bhargava reste le meilleur premier livre pour qui n’est pas à l’aise avec les maths.

Vaut-il mieux apprendre en C, en Python, ou dans un autre langage ?

Python est plus rapide à apprendre et facilite le focus sur les idées, ce qui est pédagogiquement préférable au début. C oblige à gérer la mémoire et apprend des choses utiles ensuite (pointeurs, allocations, alignement). L’idéal est d’écrire d’abord en Python pour vérifier qu’on a compris l’algorithme, puis de le réimplémenter en C ou en Rust pour comprendre ce qui se passe sous le capot. Tous les tutoriels de cette série utilisent Python par souci d’accessibilité.

Ressources et références

• Documentation officielle Python — module collections
• Python Wiki — complexité des opérations sur les types intégrés
• Wikipedia — Quicksort (article complet, références historiques)
• Wikipedia — Timsort et Powersort (Python 3.11+)
• MIT OpenCourseWare — cours 6.006 Introduction to Algorithms
• CACM Vol. 4 (1961) — Algorithm 64 : Quicksort par C.A.R. Hoare (article original)
• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (4e édition, MIT Press, 2022)
• Steven Skiena — The Algorithm Design Manual (3e édition, Springer, 2020)