Ce que le cours couvrait et ce qu’il a omis
Le cours de Hamming couvrait : la conversion analogique-numérique, la correction d’erreurs, la simulation, les statistiques, l’analyse numérique et la géométrie n-dimensionnelle. Il pensait de manière computationnelle — le traitement du signal, la théorie du codage et le filtrage numérique exigent tous un raisonnement computationnel.
Il n’a jamais enseigné systématiquement la complexité algorithmique.
Pourquoi l’écart existait
Le modèle mental de Hamming s’est formé à une époque où les goulets d’étranglement matériels dominaient. La question était : combien de transistors par puce ? L’algorithme s’exécutait sur le matériel disponible. À N=100, un algorithme O(N²) coûte 10 000 opérations. À N=1 000, il coûte 1 000 000. À N=10 000 (courant aujourd’hui dans les graphes de dépendances, les réseaux sociaux et les gestionnaires de paquets) : il coûte 100 000 000. La différence entre O(N) et O(N²) était invisible aux échelles auxquelles Hamming travaillait, et catastrophique aux échelles que ses étudiants allaient habiter.
Donald Knuth a publié The Art of Computer Programming à partir de 1968 — la même année où Hamming était à pleine productivité de recherche. La notation Big O est devenue le vocabulaire algorithmique standard dans les années 1970 et 1980. Le cours de Hamming date de 1995, mais son modèle mental du calcul s’est formé plus tôt. Il n’a jamais mis à jour ce chapitre.
Un fondamental selon le propre test de Hamming
Le test de Hamming pour un fondamental : (1) il a duré longtemps, (2) le reste du domaine peut en être dérivé à l’aide de méthodes standard.
Big O passe les deux tests. L’analyse des taux de croissance existe depuis Knuth. À partir d’elle, on dérive le choix d’algorithme, le choix de structure de données et la prédiction de performance — la majeure partie de l’informatique pratique découle de la question « comment le coût évolue-t-il quand N augmente ? » Hamming a manqué le fondamental le plus durable de son propre domaine.
Big O en tant que fondamental
Hamming enseignait que les fondamentaux survivent aux technologies spécifiques. Il prenait le calcul comme exemple : inventé une fois, applicable à la physique, l’ingénierie, l’économie et la biologie pendant des siècles. Les outils périphériques vont et viennent ; les fondamentaux s’accumulent.
Comment le Coût Croît
Big O mesure comment le coût croît lorsque l’entrée croît. Pas le facteur constant — le taux. Deux algorithmes qui s’exécutent tous deux en « quelques millisecondes » à N=100 peuvent diverger d’un facteur de 10 000 à N=10 000, si l’un s’exécute en temps O(N) et l’autre en O(N²).
Les Classes de Complexité Courantes
O(1) — Constant. Même coût quel que soit N. Exemples : recherche dans une table de hachage par clé, accès à un tableau par index, push/pop sur une pile. Doubler N ne change rien.
O(log N) — Logarithmique. Chaque étape divise par deux le travail restant. Exemples : recherche dichotomique dans un tableau trié, requête spatiale BVH dans un moteur de jeu, opérations sur un arbre binaire équilibré. Pour N=1 000 000 : log₂(1 000 000) ≈ 20 étapes.
O(N) — Linéaire. Le coût augmente avec la taille de l’entrée. Exemples : parcours linéaire d’une liste, lecture d’un fichier, comptage d’éléments dans une collection. Pour N=10 000 : 10 000 opérations.
O(N log N) — Linéarithmique. Presque linéaire, légèrement pire. Exemples : tri fusion, algorithmes efficaces de plus court chemin (Dijkstra avec un tas). Pour N=10 000 : environ 133 000 opérations.
O(N²) — Quadratique. Le coût explose. Exemples : list.contains() appelé dans une boucle sur la même liste, tri à bulles, comparaison naïve de toutes les paires. Pour N=1 000 : 1 000 000 opérations. Pour N=10 000 : 100 000 000 opérations.
O(2^N) — Exponentiel. Inutilisable à toute échelle significative. Exemples : combinatoire par force brute, recherche de tous les sous-ensembles. À N=30 : plus d’un milliard d’opérations.
L’échelle qui le rend visible
Comparaisons pour N=10 :
O(N) : 10
O(N²) : 100
ratio: 10x
N=1 000 comparaisons :
O(N) : 1 000
O(N²) : 1 000 000
ratio : 1 000x
N=10 000 comparaisons :
O(N): 10,000
O(N²): 100,000,000
ratio: 10,000xÀ N=10, la différence est à peine perceptible. À N=10,000, l’algorithme O(N²) s’exécute 10,000 fois plus lentement. C’est pourquoi MOAD-0001 est resté invisible pendant des décennies : les graphes sur lesquels il tournait en 1993 comptaient 50 nœuds. En 2020, le même code s’exécutait sur des graphes de dépendances comptant 50,000 nœuds.
Classer trois opérations
Appliquez les classes de complexité à des opérations concrètes. La question clé pour chacune : combien d’opérations cela prend-il lorsque N augmente ?
Code Correct, Mauvaise Courbe de Croissance
Un code correct qui s'exécute en temps O(N²) produit des résultats identiques à un code O(N). Les tests passent. La sortie correspond. Aucune exception ne se déclenche. Le défaut se cache dans la courbe de croissance.
Cette propriété rend les défauts O(N²) sédimentaires : ils se calcifient à l'intérieur d'un code fonctionnel et ne deviennent visibles que lorsque N dépasse un certain seuil. Le code n'a pas changé. Le monde autour de lui a changé.
MOAD-0001 : Le Défaut Sédimentaire
L'exemple le plus répandu : visited = [] à l'intérieur d'une boucle de parcours de graphe.
visited = []
for node in graph:
if node not in visited: # scan O(N) à chaque appel
visited.append(node)
process(node)Chaque appel not in visited parcourt de 0 à len(visited)-1 éléments. N appels × N/2 éléments scannés en moyenne = O(N²) au total. La solution : une seule ligne.
visited = set() # test d'appartenance O(1)
for node in graph:
if node not in visited: # recherche par hachage O(1)
visited.add(node)
process(node)Même comportement. Même sortie. Même tests réussis. Le taux de croissance passe de O(N²) à O(N). À N=1 000 : 1 000× plus rapide. À N=10 000 : 10 000× plus rapide.
Pourquoi l'époque de Hamming a semé ce problème
Dans les premiers Java et C, ArrayList (tableau dynamique) était le conteneur séquentiel par défaut. Les ensembles existaient mais n'étaient pas idiomatiques — les développeurs utilisaient ce qui leur était familier. Un parcours de graphe en 1993 à N=50 s'exécutait en microsecondes avec visited = []. Ce code est entré dans le contrôle de version, a été copié, encapsulé dans des bibliothèques, distribué via des gestionnaires de paquets. En 2020, le même motif s'exécutait sur des graphes de dépendances de 50 000 nœuds.
Le code était correct en 1993. Il est devenu coûteux quand le monde autour a changé. L'époque de Hamming a semé cette classe de défaut en n'ayant jamais nommé la question du taux de croissance.
Diagnostiquer & Corriger
Appliquez le diagnostic : trouvez le motif O(N²), identifiez la correction.
Quels changements de nom
Avant que Big O ait un nom, les programmeurs constataient « ça tourne lentement ». Ils profilaient. Ils réécrivaient. Mais ils ne pouvaient pas enseigner le motif — ils ne pouvaient que pointer des instances. Un motif sans nom ne peut pas se propager.
Une fois que Big O a eu un nom, un ingénieur senior pouvait dire « c’est O(N²), remplacez-le par un set » et un ingénieur junior pouvait comprendre, appliquer et transmettre le motif à son tour. Le nom a fait du motif une unité de connaissance transférable.
Hamming connaissait cette dynamique dans d’autres domaines. Il a décrit comment nommer le « spaghetti code » dans les années 1960 a permis à la communauté de reconnaître, discuter et finalement éradiquer une classe de défaut que tout le monde avait rencontrée mais que personne n’avait nommée. Le même mécanisme s’applique aux classes de complexité.
Unhamming ajoute le vocabulaire que Hamming avait omis : O(1), O(log N), O(N), O(N log N), O(N²), O(2^N). Ces noms vous permettent de voir la courbe de croissance dans le code que vous lisez, de prédire les performances à grande échelle et de communiquer les corrections avec précision. Ils satisfont au propre critère de Hamming pour un concept fondamental : durable et générateur de la majeure partie du reste du domaine. [TITLE who_coined_big_o/]
De la théorie des nombres à l'informatique
La notation Big O n'est pas née en informatique. Elle trouve son origine dans les mathématiques pures — plus précisément dans la théorie des nombres — 74 ans avant que Donald Knuth ne l'adapte aux algorithmes.
Paul Bachmann, 1894
Paul Bachmann, mathématicien allemand, a introduit la notation O dans son ouvrage de 1894 Die Analytische Zahlentheorie (Théorie analytique des nombres). Il avait besoin d'un moyen concis d'exprimer qu'une quantité ne croît pas plus vite qu'une autre, à un facteur constant près. Écrire « f(n) = O(g(n)) » signifiait : f croît au plus aussi vite que g. Cela permettait aux théoriciens des nombres de raisonner sur les termes d'erreur dans les approximations sans suivre les constantes exactes.
Bachmann ne pensait pas aux boucles, aux structures de données ou au temps d'exécution. Il réfléchissait à la distribution des nombres premiers — plus précisément aux termes d'erreur dans le théorème des nombres premiers.
Edmund Landau, 1909
Edmund Landau, autre mathématicien allemand, a popularisé la notation dans son ouvrage de 1909 Handbuch der Lehre von der Verteilung der Primzahlen (Manuel sur la distribution des nombres premiers). Landau a également introduit la notation associée o (petit-o) et a utilisé la famille des symboles asymptotiques de manière si extensive que celle-ci est devenue connue sous le nom de notation de Bachmann-Landau ou simplement notation de Landau.
Pendant six décennies, la notation O est restée exclusivement dans le domaine des mathématiques. Aucun programmeur n'y pensait.
Donald Knuth, 1968 & 1976
Donald Knuth a traduit la notation en informatique. Dans The Art of Computer Programming (Vol. 1, 1968), Knuth a utilisé la notation O pour décrire le temps d'exécution des algorithmes — un transfert direct de l'outil de Bachmann vers un nouveau domaine. Il fut le premier à l'appliquer systématiquement à l'analyse d'algorithmes.
En 1976, Knuth publia un court article dans SIGACT News intitulé « Big Omicron and Big Omega and Big Theta ». Il introduisit Omega (Ω) pour les bornes inférieures et Theta pour les bornes serrées, complétant le vocabulaire à trois symboles que l'informatique utilise aujourd'hui. Il plaida également pour la standardisation de l'utilisation de ces symboles dans le domaine — un acte de normalisation délibérée qui accéléra leur adoption.
Au début des années 1980, Big O apparaissait dans tous les manuels d'algorithmes. Dans les années 1990, il était devenu le vocabulaire standard des entretiens.
Un voyage de 74 ans
1894 — Bachmann introduit O en théorie des nombres
1909 — Landau popularise O, o et la famille complète de notations
1953 — Hamming commence ses recherches aux Bell Labs (n’apprend jamais le Big O en tant qu’outil informatique)
1968 — Knuth applique O à l’analyse d’algorithmes dans TAOCP Vol. 1
1976 — Knuth ajoute Omega et Theta ; plaide pour une standardisation
1980s — Le Big O entre dans tous les programmes d’études en informatique
1993 — La couche sédimentaire MOAD-0001 se forme dans le code de production
1995 — Hamming donne la dernière version de son cours ; n’y aborde jamais le Big O
2026 — MOAD-0001 trouvé dans plus de 1 000 projets open-sourceL'outil de Bachmann passa 74 ans en mathématiques pures, visible pour tous les mathématiciens mais invisible pour tous les programmeurs. Knuth en vit le potentiel. Hamming — travaillant à la même époque, collaborant avec la même communauté informatique — ne l'intégra jamais à son cours.
Pourquoi la standardisation de Knuth a compté
L'article de Knuth de 1976 fit plus que simplement introduire Omega et Theta. Il soutint que le domaine avait besoin d'une notation cohérente et que l'incohérence était réellement nuisible. Différents manuels utilisaient O pour signifier des choses différentes — parfois une borne supérieure, parfois une approximation, parfois sans préciser si les constantes comptaient. Knuth clarifia tout cela.
C'est la dynamique de dénomination de modèles de Hamming appliquée à la notation elle-même. Avant que Knuth ne standardise les symboles, les ingénieurs ne pouvaient pas communiquer précisément les affirmations de complexité entre manuels, articles ou équipes. Après la standardisation, « ceci s'exécute en O(N log N) » portait exactement une seule signification, peu importe qui le disait.
Knuth contribua également à la traduction informelle : « O(f(n)) signifie que le temps d'exécution est au plus un multiple constant de f(n), pour tous les n suffisamment grands. » Cette interprétation — borne supérieure, jusqu'à un facteur constant, pour les grandes entrées — devint l'intuition standard que tout programmeur apprend.