Compter les comparaisons — exercice corrigé de Python (école d'ingénieur) (chapitre 6)

Compter les comparaisons

Complexité algorithmique

Énoncé

Soit la fonction de recherche linéaire suivante :

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

Exprimer le nombre de comparaisons effectuées dans :

Le meilleur des cas

Le pire des cas

Le cas moyen (en supposant que $x$ est présent avec probabilité $p$ et que toutes les positions sont équiprobables)

Corrigé

Soit $n = len (L)$ .

Meilleur des cas : $x$ est le premier élément de la liste ( $L [0] == x$ ). Une seule comparaison est effectuée. $C_{meilleur} = 1$

Pire des cas : $x$ est le dernier élément de la liste ou est absent. La boucle parcourt toute la liste. $C_{pire} = n$

Cas moyen : Supposons que $x$ est présent dans la liste avec une probabilité $p$ ( $0 \leq p \leq 1$ ).

Si $x$ est présent (probabilité $p$ ), il se trouve à l'index $i \in {0, \dots, n - 1}$ avec une probabilité uniforme de $1/ n$ . Trouver $x$ à l'index $i$ requiert $i + 1$ comparaisons. Le nombre moyen de comparaisons est : $E [comparaisons ∣ pr e ˊ sent] = i = 0 \sum n - 1 \frac{1}{n} \cdot (i + 1) = \frac{1}{n} \cdot \frac{n ( n + 1 )}{2} = \frac{n + 1}{2}$

Si $x$ est absent (probabilité $1 - p$ ), la recherche parcourt toute la liste et effectue $n$ comparaisons.

Le nombre moyen global de comparaisons est donc : $C_{moyen} = p \cdot \frac{n + 1}{2} + (1 - p) \cdot n = n - p \cdot \frac{n - 1}{2}$ Cas particuliers :

Si $p = 1$ (l'élément est toujours présent) : $C_{moyen} = \frac{n + 1}{2}$ .

Si $p = 0$ (l'élément n'est jamais présent) : $C_{moyen} = n$ .