L'algorithme minmax utilise 3n/2-2
comparaisons pour trouver
le minimum et maximum de n nombres (n pair).
- Combien sont utilisées quand n est impair?
- Pour l'algorithme plus naif qui compare chaque nombre
après le deuxième
avec le maximum des précédents et (s'il était
inférieur au maximum)
avec le minimum, le nombre de comparaisons dépend de l'ordre des
données;
Quels sont les nombres minimum et maximum de comparaisons?
- On veut démontrer que tout algorithme basé sur
les comparaisons
doit utiliser au moins le même nombre que minmax.
On va utiliser une méthode de l'adversaire :
chaque fois que l'algorithme effectue une comparaison, l'adversaire
donne une réponse qui est cohérente avec les
réponses précédentes
mais choisie afin d'obliger l'algorithme à prendre le maximum de
temps;
ici l'adversaire devrait essayer de garder le plus grand nombre
possible
d'éléments du tableau qui pourraient être le
minimum et/ou le maximum.
Donner une stratégie pour l'adversaire qui oblige tout
algorithme à
effectuer au moins le nombre de comparaisons de minmax.
Conclure que tout algorithme nécessite ce nombre,
au moins dans le pire cas.
- Pour étudier le comportement d'un algorithme en
moyenne, on peut supposer
que tous les n! ordres possibles des n données ont la même
probabilité;
avec cette supposition, est-il vrai que tout algorithme doit faire
autant
de comparaisons que minmax en moyenne?