CHAPITRE 8 : LE PIRE, LE MEILLEUR, LA MOYENNE ET L'AMORTI

La même recherche dans la même liste peut coûter une comparaison ou dix mille, selon l'endroit où se trouve ce qu'on cherche. Il faut donc préciser de quoi on parle.

Trois situations pour un seul algorithme

def chercher(tab, x):
    for i in range(len(tab)):
        if tab[i] == x:
            return i
    return -1

Meilleur cas : x est en première position. 1 comparaison → O(1).
Pire cas : x est en dernière position, ou absent. n comparaisons → O(n).
Cas moyen : si x est présent et à une position équiprobable, on en examine n/2 en moyenne → O(n).

Notez que le cas moyen et le pire cas sont dans la même famille : le facteur 1/2 disparaît. Ce n'est pas toujours le cas : le tri rapide, lui, a bien un cas moyen et un pire cas de familles différentes.

Lequel annonce-t-on ?

Le pire cas, par défaut. Pour trois raisons.

C'est une garantie. « Jamais plus de n comparaisons » est une promesse sur laquelle on peut dimensionner un serveur.
Il arrive vraiment. Le pire cas de la recherche linéaire, c'est l'élément absent, et chercher quelque chose qui n'est pas là est une situation banale.
Le cas moyen exige une hypothèse. Moyenne sur quelle distribution ? Si l'on suppose les positions équiprobables alors que les utilisateurs cherchent surtout les mêmes dix éléments, le calcul est faux.

Le meilleur cas, lui, n'intéresse presque personne : il décrit le coup de chance, pas le service rendu.

Quand le cas moyen l'emporte quand même. Le tri rapide est O(n²) au pire et O(n log n) en moyenne. C'est pourtant lui qu'on utilise partout, parce que le pire cas est rare, surtout avec un pivot aléatoire, et que ses constantes sont excellentes. Annoncer le pire cas est la règle ; en faire le seul critère de choix serait une erreur.

Le cas amorti : une autre question

Voici un cas que les trois précédents décrivent mal. En Python, liste.append(x) est annoncé O(1). Pourtant, regardons comment un tableau dynamique fonctionne.

Le tableau a une capacité. Quand elle est atteinte, il faut en allouer un plus grand et recopier tout le contenu : un coût en O(n).

capacité 4, 4 éléments → append → nouvelle capacité 8, 4 copies
capacité 8, 8 éléments → append → nouvelle capacité 16, 8 copies
capacité 16, …         → append → nouvelle capacité 32, 16 copies

Le pire cas d'un append est donc bien O(n). Mais c'est une mauvaise façon de regarder : ce qui compte, pour une opération qu'on répète des milliers de fois, c'est le coût moyen sur la suite entière.

Le calcul

Faisons n ajouts, en partant d'une capacité 1 et en doublant à chaque fois. Les recopies ont lieu aux tailles 1, 2, 4, 8, …, et coûtent chacune leur taille :

1 + 2 + 4 + 8 + … + n < 2n

C'est une somme géométrique : son total est inférieur au double du dernier terme. Donc n ajouts coûtent n opérations « normales » plus moins de 2n recopies, soit moins de 3n au total.

Coût total < 3n pour n opérations → coût amorti O(1) par opération.

La clé est le doublement. Comme la capacité double, les recopies deviennent de plus en plus rares, exactement au même rythme qu'elles deviennent plus chères. Les deux effets s'annulent.

Ce qui se passerait avec un agrandissement fixe. Si l'on ajoutait 10 cases au lieu de doubler, il y aurait une recopie tous les 10 ajouts, de coût croissant : 10 + 20 + 30 + … + n, soit n²/20. Le coût amorti serait O(n), pas O(1). Le doublement n'est pas un détail d'implémentation, c'est ce qui rend append gratuit.

Amorti n'est pas moyen

La distinction est subtile et tombe souvent en examen.

	Cas moyen	Amorti
Porte sur	une opération, sur des entrées variées	une suite d'opérations, sur une seule structure
Repose sur	une hypothèse de probabilité	un calcul exact, sans hasard
Garantit	une espérance	un total, avec certitude

Le cas moyen dit « en général, ça devrait aller ». L'amorti dit « sur mille opérations, le total ne dépassera pas trois mille, c'est démontré ». La seconde affirmation est bien plus forte.

À retenir

Un algorithme a un meilleur cas, un pire cas et un cas moyen : préciser lequel.
Par défaut on annonce le pire cas, parce que c'est la seule garantie.
Le coût amorti répartit le prix des opérations rares et chères sur l'ensemble de la suite.
append est O(n) au pire et O(1) amorti, grâce au doublement de capacité.

Exercices d'application

Exercice 1

Donnez les trois complexités du tri par insertion.

Voir le corrigeMasquer le corrige

Meilleur cas : tableau déjà trié : O(n). Chaque élément est comparé à son voisin de gauche, le test échoue immédiatement, aucun décalage. Une seule passe.

Pire cas : tableau trié à l'envers : O(n²). Chaque élément doit remonter jusqu'au début : 1 + 2 + … + (n−1) décalages.

Cas moyen : O(n²). Chaque élément remonte en moyenne de la moitié du chemin, soit n²/4 décalages. Le facteur disparaît à la simplification.

C'est ce meilleur cas en O(n) qui rend le tri par insertion précieux : sur des données presque triées il est excellent, et c'est pour cela que Timsort, le tri de Python, l'utilise sur ses petits segments.

Exercice 2

Un tableau dynamique double sa capacité quand il est plein, et la divise par deux quand il est à moitié vide. Où est le problème ?

Voir le corrigeMasquer le corrige

Le problème est à la frontière. Imaginez un tableau de capacité 16 contenant 8 éléments, et la suite d'opérations :

append  -> 9 elements
pop     -> 8 elements, a moitie vide -> on retrecit a 8, 8 copies
append  -> 9 elements, c'est plein   -> on double a 16, 8 copies
pop     -> 8 elements                -> on retrecit, 8 copies
...

Chaque opération déclenche une recopie complète : le coût amorti remonte à O(n). On appelle cela le thrashing.

La parade est de laisser du jeu entre les deux seuils : on ne rétrécit qu'au quart de remplissage, pas à la moitié. Il faut alors beaucoup d'opérations dans le même sens pour provoquer une recopie, et l'amorti redevient O(1). C'est ce que font les implémentations réelles.

Cherchez avant d'ouvrir le corrige : c'est en butant sur les difficultes que l'on progresse.