Écrire minimum et maximum(t) en un seul parcours, renvoyant un couple


def minimum_et_maximum(t):
    """Couple (plus petit, plus grand) en un seul parcours.

    Précondition  : t est non vide.
    Postcondition : mini <= x <= maxi pour tout x de t, et mini et maxi
                    appartiennent tous deux à t.
    """
    assert len(t) > 0, "tableau vide"
    mini = maxi = t[0]
    for i in range(1, len(t)):
        if t[i] < mini:
            mini = t[i]
        else:
            if t[i] > maxi:
                maxi = t[i]
    return mini, maxi

L'invariant tient en une phrase : avant le tour $i$ , mini et maxi sont le plus petit et le plus grand élément de t[0..i-1]. L'initialisation à t[0] — et non à une constante — est ce qui rend l'invariant vrai au départ, et c'est l'avertissement du cours.

Le décompte. Le else est essentiel : si t[i] est plus petit que le minimum, il ne peut pas être plus grand que le maximum, et la seconde comparaison est inutile. Le coût dépend donc du contenu :

pire cas — tableau croissant : la première comparaison est toujours fausse, on paie les deux à chaque tour, soit $2 (n - 1)$ . Mesuré sur $n = 100$ croissant : 198 comparaisons, et $2 \times 99 = 198$ ;
meilleur cas — tableau décroissant : une seule comparaison par tour, soit $n - 1$ . Mesuré : 99.

Peut-on faire mieux ? Oui : $⌈ 3 n /2 ⌉ - 2$ . On traite les éléments par paires. Une comparaison range les deux membres de la paire ; le plus petit ne peut alors concourir que pour le minimum, le plus grand que pour le maximum. Trois comparaisons par paire, soit $3/2$ par élément, au lieu de $2$ .

$n$	un par un	par paires	$⌈ 3 n /2 ⌉ - 2$
$10$	$18$	$13$	$13$
$100$	$190$	$148$	$148$
$1000$	$1994$	$1498$	$1498$

Les deux versions ont été comparées sur $2000$ tableaux tirés au hasard : elles rendent toujours le même couple, et le même que (min(t), max(t)).

Ce que cela vaut, honnêtement. On passe de $2 n$ à $1, 5 n$ : le gain est d'un quart, il ne change pas la loi — les deux restent linéaires. On peut démontrer qu'aucun algorithme ne descend sous $⌈ 3 n /2 ⌉ - 2$ comparaisons ; c'est donc l'optimum, et c'est un résultat de terminale.

Énoncé

Corrigé