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 une 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 une 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 une 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 occasionnellement prend 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 Binaires
La recherche binaire fonctionne uniquement sur des tableaux triés. À chaque étape : comparez la cible avec l'élément au milieu. Si la cible est égale au milieu, retournez-la. Si la cible est plus petite, récurez sur la moitié gauche. Si plus grande, récurez 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 exécutées par un algorithme. La complexité en espace mesure la mémoire supplémentaire allouée en plus de son entrée. Les deux comptent 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, le tri par insertion) échange des éléments à l'intérieur de l'array original. Il utilise une poignée 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, c'est 10^8 entrées - des centaines de mégaoctets pour une 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 O(1). Sans la table de hash, une recherche dans une liste nécessite O(N) pour obtenir O(1) de mémoire supplémentaire. La table de hash paie en mémoire pour obtenir 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 espace 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 hachage). Insérer chaque mot ; augmenter son comptage.
Stratégie B: maintenir une liste triée des mots vus ; utiliser la recherche binaire pour vérifier l'appartenance avant d'insérer.
Analyse amortie : répartir les coûts
Lorsque les 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 pire cas 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 doublage copie tous les éléments existants : O(N) de travail pour une insertion. Mais les doublures sont rares. Après N insertions totales, combien d'opérations de copie ont eu lieu ?
Les doublures ont lieu aux tailles 1, 2, 4, 8, ..., N/2. Nombre de copies : 1 + 2 + 4 + ... + N/2. Cela représente une série géométrique sommant N - 1 de copies totales sur tous les N inscriptions. Coût moyen de copies par inscription : (N - 1) / N < 1, donc O(1) amorti par inscription malgré un coût pire cas de O(N) par doublure.
Pourquoi l'analyse amortie compte
Un système qui cesse parfois de redimensionner, de rebalancer ou de compacter une structure peut paraître avoir des opérations individuelles avec un coût pire cas alarmant. 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 la surenchère : ajouter de la complexité pour éviter un rare O(N) d'opération qui ne contribue qu'à 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 par être 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.