L’étude approfondie des structures de données constitue un pilier fondamental de l’informatique moderne, non pas simplement comme un catalogue de solutions toutes faites, mais comme une discipline intellectuelle permettant de comprendre les mécanismes profonds qui régissent l’organisation, le stockage et la manipulation de l’information dans les systèmes numériques.
Une structure de données n’est pas un objet isolé : elle représente l’interface entre un algorithme et la mémoire physique de la machine. Chaque choix de structure de données encode implicitement des hypothèses sur :
- La fréquence relative des opérations : un système qui effectue principalement des insertions en fin de séquence (écriture) n’a pas les mêmes besoins qu’un système qui effectue des recherches (lecture seul).
- La topologie des accès mémoire : accès séquentiels versus accès aléatoires, localité spatiale vs distance temporelle des accès.
- Les contraintes matérielles : hiérarchie de cache (L1, L2, L3), TLB (Translation Lookaside Buffer), latence DRAM, bande passante mémoire, quantité de mémoire et capacité de calcule.
Comprendre ces mécanismes permet de dépasser l’abstraction offerte par les langages de haut niveau et de raisonner sur le comportement réel du système, en particulier lorsque les performances deviennent critiques. Choisir la bonne structure de donnée, voir la modifier pour correspondre aux besoins métiers et matériel peut-être crutial notament dans les secteurs : millitaire, aéronotique, spatial, industriel, scientifique et jeux vidéo. Les enjeux sont liés aux temps de réaction et ux économie d’échelle potentiel (réduction des temps de calcule, exemple génération de film Disney jours -> heures).
La notation asymptotique
La notation Big-O, introduite par Paul Bachmann et Edmund Landau au tournant du XXe siècle, constitue le langage universel de l’analyse algorithmique. Elle permet de caractériser le comportement asymptotique d’un algorithme lorsque la taille de l’entrée $n$ tend vers l’infini. Le comportement peut être décrit en terme spatial, c’est‑à‑dire la quantité de mémoire utilisée, et/ou en terme temporel, c’est‑à‑dire le temps ou le nombre d’itérations nécessaires au calcul.
Soit $f : \mathbb{N} \to \mathbb{R}^+$ une fonction représentant le coût (en temps ou en espace) d’un algorithme. On dit que $f(n) = O(g(n))$ s’il existe des constantes $c > 0$ et $n_0 \geq 0$ telles que :
$$\forall n \geq n_0, \quad f(n) \leq c \cdot g(n)$$
Dit autrement, une fonction $f$ peut avoir une compléxité variable en fonction de $n$, exemple $f(1)$ prend 1s, $f(2)$ prend 0.5s, $f(3)$ prend 3s, etc. Techniquement on considèrera que la fonction $f$ a une borne supérieur en $O(n)$, c’est le pire cas. La notation Big-O fournit une borne supérieure asymptotique : elle décrit le pire cas de croissance de la fonction.
Classes de complexité courantes
Les classes de complexité ci‑dessous permettent de comparer les algorithmes selon la vitesse à laquelle leurs ressources nécessaires augmentent avec la taille de l’entrée.
| Notation | Nom | Exemple typique | Croissance |
|---|---|---|---|
| $O(1)$ | Constante | Accès direct tableau | Idéale |
| $O(\log n)$ | Logarithmique | Recherche dichotomique | Excellente |
| $O(n)$ | Linéaire | Parcours de liste | Acceptable |
| $O(n \log n)$ | Linéarithmique | Tri fusion, tri rapide | Bonne |
| $O(n^2)$ | Quadratique | Tri par sélection | Médiocre |
| $O(2^n)$ | Exponentielle | Recherche exhaustive | Prohibitive |
Les complexités constante et logarithmique sont les plus recherchées : la performance reste excellente même pour de très grandes données. La complexité linéaire reste acceptable pour la plupart des traitements séquentiels, tandis que les algorithmes quadratiques ou exponentiels deviennent rapidement impraticables : une taille d’entrée doublée peut multiplier le temps d’exécution par un facteur énorme. Ainsi, le choix d’un algorithme efficace repose souvent sur le compromis entre simplicité d’implémentation et croissance asymptotique.
Autres notations asymptotiques
En analyse d’algorithmes, on ne s’intéresse pas seulement au pire cas, mais aussi au comportement typique et au cas le plus favorable. Une connaissance profonde de l’algorithme visé permet justement de tombé dans le meilleur cas avec une probabilité plus élevé.
| Notation | Sens | Définition formelle | Interprétation |
|---|---|---|---|
| Ω(g(n)) | Borne inférieure asymptotique | Il existe des constantes $c > 0$ et $n_0$ telles que $\forall n \ge n_0, f(n) \ge c \cdot g(n)$. | Décrit le meilleur cas : la performance minimale atteignable. |
| Θ(g(n)) | Bornes asymptotiques serrées | $f(n) = O(g(n))$ et $f(n) = \Omega(g(n))$. | Décrit la complexité moyenne ou typique, lorsque le coût reste proportionnel à $g(n)$. |
| O(g(n)) | Borne supérieure asymptotique | $\forall n \ge n_0, f(n) \le c \cdot g(n)$. | Décrit le pire cas. |
Prenons l’algorithme de tri rapide (quicksort) :
- Meilleur cas : $\Omega(n \log n)$, quand les pivotages sont équilibrés.
- Cas moyen : $\Theta(n \log n)$, c’est la complexité la plus représentative.
- Pire cas : $O(n^2)$, quand les pivots sont mal choisis (liste déjà triée, par exemple).
Limites de l’analyse asymptotique
Cette notation est largement utilisé pour rapidement comparer les algorithme et prendre des décisions rapide. Elle est a connaitre notament pour cette raison mais également car elle est utilisé dans les testes de recrutement. MAIS la notation Big-O présente plusieurs limitations critiques en pratique :
- Les constantes sont ignorées : Un algorithme en $O(n)$ avec une constante de 1000 peut être largement surpassé par un algorithme en $O(n \log n)$ avec une constante de 0.01 pour des valeurs de $n$ réalistes (disons $n < 10^6$).
- Les termes d’ordre inférieur sont négligés : Pour un algorithme en $5n^2 + 100n + 50$, on écrit simplement $O(n^2)$, mais le terme $100n$ peut dominer pour $n < 50$.
- Le comportement du cache n’est pas modélisé : Deux algorithmes en $O(n)$ peuvent avoir des performances radicalement différentes selon leur pattern d’accès mémoire. Un parcours séquentiel d’un tableau bénéficie du prefetching matériel et de la localité cache, tandis qu’un parcours de liste chaînée subit des cache misses systématiques.
- La complexité en espace est souvent sous-estimée : Un algorithe peut être rapide mais consommer une mémoire prohibitive (exemple : skip lists avec $O(n \log n)$ en espace.
Donc en pratique, un expert n’utilisera pas cette notation. Il existe plusieurs exemples réel. Par exemple lorsque les enssemble manipulé sont petit la notation n’a aucun sens cas les constantes et ‘petits’ termes on été tronqué. Ceci arrive en vrai dans la majorité des cas.
Structure adaptée au cas d’usage
Un principe fondamental de l’ingénierie logicielle est qu’aucune structure de données n’est optimale pour tous les cas d’usage. Chaque structure encode un ensemble de compromis :
- Temps d’insertion vs. temps de recherche : Une liste chaînée simple (
LinkedList<E>en Java) permet des insertions en $O(1)$ en tête. Les écritures sont très rapide malgret un overhead de mémoire, mais les recherches sont en $O(n)$. Un arbre binaire équilibré offre des recherches en $O(\log n)$ donc une lecture rapide, mais nécessite des rotations coûteuses lors des insertions. - Localité mémoire vs. flexibilité : Un tableau dynamique (type
ArrayList<E>en Java) offre une excellente localité mais requiert des réallocations coûteuses lors de la croissance. Une liste chaînée évite les réallocations mais disperse les nœuds en mémoire, provoquant des cache misses. - Complexité algorithmique vs. constantes cachées : Une skip list offre une complexité théorique en $O(\log n)$ pour la recherche, mais les constantes liées aux cache misses peuvent la rendre plus lente qu’une recherche linéaire sur un tableau pour des ensembles de taille modérée ($n < 10^4$). Donc si théoriquement les skip list sont avantageuses, la réalité technique les rends peu exploitable … avec une différence jusqu’a 50x en temps de lecture.
Cette différence s’explique par :
- Cache misses : Chaque nœud de la liste nécessite un accès mémoire imprévisible, tandis que le tableau bénéficie du prefetching.
- Overhead mémoire : Chaque nœud de liste stocke des pointeurs (8 octets sur x86-64) en plus des données, réduisant l’efficacité du cache.
- Branch misprediction : Le parcours de liste implique des sauts conditionnels imprévisibles (pointeur suivant nul ou non).