Meilleur, Pire et Moyenne
Trois Manières de Mesurer un Algorithme
Le coût d'un algorithme dépend de son entrée. Deux entrées de la même taille peuvent produire des temps d'exécution sauvagement différents. L'analyse de complexité formalise trois perspectives sur cette variation.
Meilleur cas — Ω (Omega): l'entrée qui fait que l'algorithme termine le plus rapidement. Pour la recherche linéaire sur une liste de N éléments: Ω(1) — la cible occupe la première position. Une comparaison, terminé.
Pire cas — O (Grand O): l'entrée qui fait que l'algorithme termine le plus lentement. Pour la recherche linéaire: O(N) — la cible se trouve à la fin de la liste, ou ne figure pas du tout. Chaque élément nécessite une inspection.
Cas moyen — Θ (Theta): coût attendu sur tous les entrées possibles, en supposant une distribution uniforme. Pour la recherche linéaire avec la cible également susceptible d'occuper n'importe l'une des N positions: Θ(N/2) = Θ(N). La constante 1/2 disparaît car Theta exprime la croissance asymptotique étroite, pas les 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 qui prend occasionnellement 60 secondes produit une échec visible par l'utilisateur. Les ingénieurs conçoivent pour les bornes du pire cas afin que les performances restent prévisibles quel que soit l'entrée. L'analyse de cas moyen a de la valeur dans les contextes probabilistes, mais l'analyse de cas pire donne des garanties.
Analyse des Cas de Recherche Binaire
La recherche binaire fonctionne uniquement sur des tableaux triés. À chaque étape : comparez la cible à l'élément situé au milieu. Si la cible est égale au milieu, retournez-la. Si la cible est plus petite, récursez sur la moitié gauche. Si plus grande, récursez sur la moitié droite.
Chaque comparaison élimine la moitié des candidats restants.
Croissance de la mémoire et échanges temps-espace
Compter la mémoire, pas les opérations
La complexité en temps mesure le nombre d'opérations effectuées par un algorithme. La complexité en espace mesure la mémoire supplémentaire allouée en plus de l'entrée. Les deux sont importants dans les systèmes de production : un algorithme rapide qui alloue O(N²) de mémoire épuisera un serveur.
O(1) espace : mémoire constante supplémentaire indépendante de N. Un tri en place (par exemple l'insertion) échange des éléments à l'intérieur de l'array original. Il utilise un nombre limité de variables temporaires - O(1) peu importe la taille de l'array.
O(N) espace : mémoire proportionnelle à la taille de l'entrée. Créer une copie d'un array de N éléments nécessite N cases. Construire un ensemble de hash à partir d'une liste de N chaînes stocke jusqu'à N entrées.
O(N²) espace : 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 représente 10^8 entrées - des centaines de mégaoctets pour un simple grille booléenne.
Échanges temps-espace
L'une des manœuvres fondamentales en conception d'algorithme : échanger l'espace pour le temps, ou le temps pour l'espace.
Les tables de hash utilisent O(N) de mémoire supplémentaire pour obtenir un accès en O(1). Sans la table de hash, une recherche dans une liste nécessite O(N) pour un accès en O(1) de mémoire supplémentaire. La table de hash paie en mémoire pour acheter de la vitesse.
La mémoïsation stocke les résultats précédemment calculés (O(N) ou plus de mémoire) pour éviter de les recalculer. Fibonacci récursif sans mémoïsation fonctionne en O(2^N) en temps. Avec mémoïsation : O(N) en temps et O(N) en mémoire. L'investissement en mémoire réduit exponentiellement le temps.
Dictionnaire de hash vs Liste triée
Comparer deux stratégies pour compter les occurrences de mots dans un document de N mots :
Stratégie A: un dictionnaire (tableau de hash). Insérer chaque mot; augmenter son comptage.
Stratégie B: maintenir une liste triée des mots vus; utiliser une recherche binaire pour vérifier l'appartenance avant d'insérer.
Analyse amortie : répartir le coût
Lorsque des dépenses occasionnelles ne ruinent pas la performance moyenne
Certaines opérations sont parfois 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 - et non le coût le pire d'une opération unique.
Tableau dynamique (liste Python, ArrayList Java) : commence avec une capacité de 1. Lorsqu'elle est pleine, elle double la capacité. Le doublement copie tous les éléments existants : O(N) de travail pour une insertion. Mais les doubles sont rares. Après N insertions totales, combien d'opérations de copie ont eu lieu au total ?
Les doubles ont lieu aux tailles 1, 2, 4, 8, ..., N/2. Nombre de copies : 1 + 2 + 4 + ... + N/2. C'est une série géométrique sommant à N - 1 opérations de copie au total sur tous les N insertions. Coût moyen de copies par insertion : (N - 1) / N < 1, donc O(1) amorti par insertion malgré un coût pire de O(N) par doublure.
Pourquoi l'analyse amortie compte
Un système qui s'arrête parfois pour redimensionner, rééquilibrer ou compacter une structure peut paraître avoir des opérations individuelles à coût le pire. L'analyse amortie révèle que l'alarme est fausse : les événements coûteux occasionnels sont payés par les nombreux autres qui sont bon marché. Comprendre le coût amorti empêche l' surenchère : ajouter de la complexité pour éviter une opération O(N) rare qui contribue seulement O(1) amorti est du travail gaspillé.
En profondeur : Le cours non Hamming applique l'analyse de complexité à des défauts réels dans le logiciel en production. Voir [Le chapitre manquant : La complexité algorithmique](/fr/un/unhamming_algorithmic_complexity) & [MOAD-0001 : La défectuosité sédimentaire](/fr/un/unhamming_moad_sedimentary).
Coût amorti d'insertion dans une table de hachage
Une table de hachage commence vide et double sa capacité lorsque le facteur de charge dépasse 0,75. L'insertion de 1 000 éléments déclenche exactement 10 redoublements à des capacités de 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.