Complexité de la recherche dichotomique — exercice corrigé de Python (école d'ingénieur) (chapitre 6)

Complexité de la recherche dichotomique

Complexité algorithmique

Énoncé

Démontrer par récurrence que la recherche dichotomique sur une liste triée de taille $n$ effectue au plus $⌊ lo g_{2} n ⌋ + 1$ comparaisons dans le pire des cas.

def dichotomie(L, x):
    g, d = 0, len(L) - 1
    while g <= d:
        m = (g + d) // 2
        if L[m] == x:
            return m
        elif L[m] < x:
            g = m + 1
        else:
            d = m - 1
    return -1

Corrigé

Soit $C (n)$ le nombre maximal de comparaisons effectuées pour une liste de taille $n$ .

Initialisation : Pour $n = 1$ , une seule comparaison suffit. $C (1) = 1 \leq ⌊ lo g_{2} 1 ⌋ + 1 = 0 + 1 = 1$ La propriété est vraie.

Hérédité : Supposons la propriété vraie pour toutes les tailles strictement inférieures à $n$ . Pour une liste de taille $n$ , on effectue une comparaison avec l'élément central $L [m]$ . Dans le pire des cas, l'élément n'est pas trouvé et on poursuit la recherche dans l'un des deux sous-tableaux, chacun ayant une taille maximale de $⌊(n - 1) /2 ⌋$ . La relation de récurrence s'écrit : $C (n) = 1 + C (⌊ \frac{n - 1}{2} ⌋)$ Par hypothèse de récurrence : $C (⌊ \frac{n - 1}{2} ⌋) \leq ⌊ lo g_{2} (⌊ \frac{n - 1}{2} ⌋) ⌋ + 1$ Puisque $⌊ \frac{n - 1}{2} ⌋ \leq \frac{n}{2}$ , nous avons : $⌊ lo g_{2} (⌊ \frac{n - 1}{2} ⌋) ⌋ \leq ⌊ lo g_{2} (\frac{n}{2}) ⌋ = ⌊ lo g_{2} n - 1 ⌋ = ⌊ lo g_{2} n ⌋ - 1$ En injectant cette inégalité : $C (n) \leq 1 + (⌊ lo g_{2} n ⌋ - 1 + 1) = ⌊ lo g_{2} n ⌋ + 1$ La propriété est démontrée au rang $n$ .