Pire cas, cas moyen, coût amorti

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 3 — Algorithmes, programmes et complexité

Énoncé

Attribuer chacune de ces trois affirmations à la bonne notion, et dire ce qu'elle garantit.

« Sur $n$ ajouts successifs dans un tableau dynamique, le coût total est $O (n)$ . »
« Une recherche séquentielle réussie coûte en moyenne $(n + 1) /2$ comparaisons. »
« Une recherche séquentielle coûte au plus $n$ comparaisons. »

Que devient (2) si l'élément cherché n'est présent qu'avec probabilité $p$ ?

Corrigé

	Notion	Ce que l'affirmation garantit
1	coût amorti	Une garantie ferme sur le total d'une suite d'opérations. Aucune hypothèse sur les entrées, aucune probabilité. Elle n'interdit pas qu'un ajout isolé coûte $Θ (n)$ .
2	cas moyen	Une espérance, sous une loi supposée sur les entrées. Aucune garantie : si les entrées ne suivent pas cette loi, le chiffre est faux.
3	pire cas	Une garantie absolue, valable pour toute entrée, sans hypothèse.

La confusion à éviter est celle du chapitre : l'amorti n'est pas une moyenne probabiliste. (1) et (2) se ressemblent — les deux divisent un total par un nombre d'opérations — mais (1) ne suppose rien, alors que (2) suppose une loi. Si l'on donne au tableau dynamique les $n$ pires suites d'ajouts possibles, le total reste $O (n)$ ; si l'on donne à la recherche séquentielle les pires entrées, la moyenne annoncée s'effondre.

Avec une probabilité de présence $p$ . Notons $C$ le nombre de comparaisons. Si l'élément est présent (probabilité $p$ ) et sa position uniforme, $E [C ∣ pr e ˊ sent] = (n + 1) /2$ . S'il est absent (probabilité $1 - p$ ), la recherche parcourt tout : $C = n$ . D'où

$E [C] = p \frac{n + 1}{2} + (1 - p) n .$

Vérification par simulation, $n = 100$ , un million de tirages par point :

$p$	$0$	$0, 25$	$0, 50$	$0, 75$	$1$
formule	$100, 000$	$87, 625$	$75, 250$	$62, 875$	$50, 500$
mesuré	$100, 000$	$87, 625$	$75, 295$	$62, 830$	$50, 440$

La moyenne reste $Θ (n)$ pour tout $p$ : le cas moyen ne change pas l'ordre de grandeur ici, seulement la constante. C'est fréquent, et c'est une bonne raison de ne pas s'y attarder tant qu'on cherche un ordre de grandeur.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.