Chaque classe de complexité dessine une courbe
Tracer le coût en fonction de la taille d'entrée
Mettez la taille d'entrée N sur l'axe des x. Mettez le coût (opérations, temps) sur l'axe des y. Chaque classe de complexité produit une courbe distincte. Vous pouvez reconnaître le taux de croissance d'un algorithme à partir de la forme de sa courbe de performance.
O(1) — ligne horizontale plate. La fonction f(N) = 1. Aucune pente. Le coût ne change jamais quel que soit N. Recherche dans une table de hachage : que la table contienne 10 ou 10 000 000 éléments, un calcul de hachage accède directement au bon bucket.
O(log N) — courbe légèrement ascendante, pente décroissante. À N = 1 000 000 : coût ≈ 20 opérations. La courbe monte fortement pour petit N, puis s'aplatit. Chaque doublement de N ajoute exactement une unité de coût.
O(N) — ligne droite diagonale. Pente = 1 (au sens asymptotique). Le coût croît au même taux que N. Si N triple, le coût triple.
O(N log N) — diagonale plus raide avec une légère courbure ascendante. Situé au-dessus de O(N) mais en dessous de O(N²). Le facteur log ajoute un multiplicateur croissant lentement à la pente linéaire.
O(N²) — parabole s'ouvrant vers le haut. La pente augmente à mesure que N croît. À N = 10 : coût = 100. À N = 100 : coût = 10 000. À N = 1 000 : coût = 1 000 000.
L'écart croissant
Le ratio O(N²) / O(N) = N. L'écart entre la parabole et la diagonale s'élargit à mesure que N croît. À N = 10 : 10× écart. À N = 100 : 100× écart. À N = 1 000 : 1 000× écart. À N = 50 000 : 50 000× écart. L'écart égale toujours N.
Calculer l'écart d'échelle
Un grand graphe de dépendances contient 50 000 packages (N = 50 000). Un algorithme s'exécute en O(N). Un autre en O(N²). À ce N, le ratio O(N²)/O(N) = N = 50 000.
Bisection d'un segment de ligne
La recherche binaire comme bisection répétée
Un tableau trié de N éléments forme un segment de ligne de longueur N. La recherche binaire coupe ce segment en deux à plusieurs reprises :
1. Pointer vers le point médian du segment restant.
2. Si target < point médian : la moitié droite disparaît. Récursez sur la moitié gauche.
3. Si target > point médian : la moitié gauche disparaît. Récursez sur la moitié droite.
4. Si target = point médian : terminé.
Après k bisections, le segment restant a une longueur de N / 2^k. La recherche se termine quand cette longueur égale 1 :
N / 2^k = 1 → 2^k = N → k = log₂N
Donc, la recherche binaire sur N éléments nécessite au plus log₂N comparaisons.
Bisection et doublement : deux faces de la même courbe
La bisection et le doublement sont des inverses géométriques. La courbe exponentielle 2^k et la courbe logarithmique log₂N sont des réflexions l'une de l'autre à travers la ligne y = x.
Considérez le pliage de papier : une feuille commence à 0,1 mm d'épaisseur. Chaque pli double l'épaisseur. Après 42 plis : 0,1 mm × 2^42 ≈ 439 804 km — au-delà de la lune (384 400 km). La recherche binaire fonctionne de façon inverse : commencez par N éléments, chaque étape coupe le compte en deux, atteindre 1 élément en log₂N étapes.
La géométrie : la bisection est une opération auto-similaire. Chaque bisection produit deux moitiés qui ressemblent de façon identique en structure au tout. La récursion & les logarithmes partagent cette auto-similarité.
Comparaisons & doublements
Un tableau trié contient 1 048 576 éléments. Note : 1 048 576 = 2^20.
Une fonction de hachage comme mappage géométrique
Fonction de hachage comme fonction
Une table de hachage mappe une clé à un bucket en utilisant une fonction de hachage :
bucket = hash(key) mod table_size
C'est une fonction au sens strictement mathématique : elle mappe un domaine (toutes les clés possibles) à une plage (indices de bucket 0 à table_size − 1). La image géométrique : les clés occupent un espace ; les buckets occupent un autre. La fonction de hachage projette les clés sur les indices de bucket.
O(1) recherche — saut direct, pas de recherche. La fonction de hachage calcule l'index du bucket en temps constant. Sautez directement vers ce bucket. Pas de traversée, pas de boucle de comparaison.
Facteur de charge. Au facteur de charge 0,75, 75 % des buckets contiennent au moins un élément. Au-dessus de ~0,9, les collisions augmentent : deux clés se font hacher vers le même bucket, formant une chaîne d'éléments à l'intérieur de ce bucket. La recherche dans une longue chaîne se dégrade à O(N) dans le pire cas.
Qualité de la distribution comme géométrie
Une fonction de hachage bien distribuée répartit les clés uniformément sur tous les buckets. Géométriquement : la plage de la fonction couvre son codomaine de façon uniforme. Chaque bucket reçoit approximativement N / table_size clés.
Une mauvaise fonction de hachage regroupe les clés dans quelques buckets. Géométriquement : la plage de la fonction s'effondre en un sous-ensemble du codomaine — la plupart des clés se mappent aux mêmes quelques points. Les buckets restants restent vides.
Connexion à MOAD-0001
Remplacer une liste par un ensemble corrige MOAD-0001 car un ensemble utilise une table de hachage en interne. O(N) scan de liste → O(1) recherche dans la table de hachage. Géométriquement : la traversée linéaire le long d'une séquence se transforme en une projection directe via une fonction. La séquence disparaît ; la fonction la remplace.
Analyser un hachage mal distribué
Une table de hachage a 1 000 buckets & 900 éléments (facteur de charge 0,9). Une mauvaise fonction de hachage envoie 500 de ces éléments vers le même bucket.