Meilleur, Pire & Cas Moyen
Trois Façons de Mesurer un Algorithme
Le coût de chaque algorithme dépend de son entrée. Deux entrées de même taille peuvent produire des temps d'exécution très différents. L'analyse de complexité formalise trois perspectives sur cette variation.
Meilleur cas — Ω (Oméga) : l'entrée qui fait terminer l'algorithme le plus rapidement. Pour une recherche linéaire sur une liste de N éléments : Ω(1) — la cible occupe la première position. Une comparaison, c'est fait.
Pire cas — O (Grand O) : l'entrée qui fait terminer l'algorithme le plus lentement. Pour une recherche linéaire : O(N) — la cible se situe en dernière position de la liste, ou n'apparaît pas du tout. Chaque élément nécessite une inspection.
Cas moyen — Θ (Thêta) : coût attendu sur toutes les entrées possibles, en supposant une distribution uniforme. Pour une recherche linéaire où la cible est également susceptible d'occuper n'importe laquelle des N positions : Θ(N/2) = Θ(N). La constante 1/2 disparaît car Thêta exprime une croissance asymptotique serrée, non des coefficients exacts.
Pourquoi le Pire Cas Domine
Les systèmes doivent gérer le pire cas. Une requête de base de données qui prend en moyenne 10 ms mais occasionnellement 60 secondes produit une défaillance visible pour l'utilisateur. Les ingénieurs conçoivent pour des bornes de pire cas afin que les performances restent prévisibles indépendamment de l'entrée. L'analyse de cas moyen a une valeur dans les contextes probabilistes, mais l'analyse de pire cas donne des garanties.
Analyse de Cas de Recherche Binaire
La recherche binaire fonctionne uniquement sur des tableaux triés. À chaque étape : comparez la cible à l'élément au point médian. Si la cible égale le point médian, renvoyez-la. Si la cible est plus petite, recurrez sur la moitié gauche. Si elle est plus grande, recurrez sur la moitié droite.
Chaque comparaison élimine la moitié des candidats restants.
Croissance de Mémoire & Échanges Temps-Espace
Compter la Mémoire, Non les Opérations
La complexité temporelle mesure le nombre d'opérations qu'un algorithme exécute. La complexité spatiale mesure la mémoire supplémentaire qu'il alloue au-delà de son entrée. Les deux sont importants dans les systèmes en production : un algorithme rapide qui alloue O(N²) de mémoire épuisera un serveur.
Espace O(1) : mémoire supplémentaire constante indépendamment de N. Un tri sur place (par exemple, tri par insertion) échange des éléments dans le tableau original. Il utilise une poignée de variables temporaires — O(1) peu importe la taille du tableau.
Espace O(N) : mémoire proportionnelle à la taille d'entrée. Créer une copie d'un tableau de N éléments nécessite N emplacements. Construire un ensemble de hachage à partir d'une liste de N chaînes stocke jusqu'à N entrées.
Espace O(N²) : mémoire proportionnelle à N². Construire une matrice d'adjacence N×N pour un graphe avec N sommets nécessite N² cellules. À N = 10 000 sommets, cela fait 10^8 entrées — des centaines de mégaoctets pour une simple grille booléenne.
Échanges Temps-Espace
Un des mouvements fondamentaux de la conception d'algorithmes : échanger l'espace contre le temps, ou le temps contre l'espace.
Les tables de hachage utilisent l'espace O(N) supplémentaire pour atteindre une recherche O(1). Sans la table de hachage, une analyse sur une liste atteint une recherche O(N) avec un espace O(1) supplémentaire. La table de hachage paie de la mémoire pour acheter de la vitesse.
La mémorisation stocke les résultats précédemment calculés (espace O(N) ou plus) pour éviter de les recalculer. Fibonacci récursive sans mémorisation s'exécute en temps O(2^N). Avec mémorisation : temps O(N) & espace O(N). L'investissement spatial rétrécit le temps exponentiellement.
Dictionnaire de Hachage vs Liste Triée
Comparez deux stratégies pour compter les occurrences de mots dans un document de N mots :
Stratégie A : un dictionnaire (table de hachage). Insérez chaque mot ; incrémentez son compte.
Stratégie B : maintenez une liste triée de mots vus ; utilisez la recherche binaire pour vérifier l'appartenance avant d'insérer.
Analyse Amortie : Étaler le Coût
Quand une Dépense Occasionnelle Ne Ruine Pas la Performance Moyenne
Certaines opérations sont occasionnellement coûteuses mais bon marché en moyenne sur une séquence. L'analyse amortie calcule le coût moyen par opération sur l'ensemble de la séquence — non le coût pire cas d'une seule opération.
Tableau dynamique (liste Python, ArrayList Java) : commence à capacité 1. Quand plein, double la capacité. Le doublement copie tous les éléments existants : travail O(N) pour une insertion. Mais les doublements sont rares. Après N insertions totales, combien d'opérations de copie totales se sont produites ?
Les doublements se produisent aux tailles 1, 2, 4, 8, ..., N/2. Comptages de copies : 1 + 2 + 4 + ... + N/2. Cela s'ajoute à une série géométrique totalisant N − 1 copies sur les N insertions. Copies moyennes par insertion : (N − 1) / N < 1, donc O(1) amorti par insertion malgré un coût pire cas O(N) par doublement.
Pourquoi l'Analyse Amortie Importe
Un système qui ocasionnellement s'arrête pour redimensionner, rééquilibrer ou compacter une structure peut sembler avoir des opérations individuelles alarmantes du pire cas. L'analyse amortie révèle que l'alarme est fausse : les événements rares coûteux sont payés par les nombreux bon marché. Comprendre le coût amorti empêche la sur-ingénierie : ajouter de la complexité pour éviter une opération O(N) rare qui ne contribue qu'à O(1) amorti est du travail gaspillé.
Aller plus loin : Le cours unhamming applique l'analyse de complexité aux défauts du monde réel dans les logiciels en production. Voir Le Chapitre Manquant : Complexité Algorithmique & MOAD-0001 : Le Défaut Sédimentaire.
Insertion de Table de Hachage Amortie
Une table de hachage commence vide & double sa capacité chaque fois que le facteur de charge dépasse 0,75. L'insertion de 1 000 éléments déclenche exactement 10 doublements à des capacités 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.