Doubler la taille du tableau

Pour la fonction de recherche dichotomique dont le code est rappelé ci-dessous

Rappel du code

def dichotomie(valeur, tab):
    """
    tab -- liste d'entiers, triée en ordre croissant
    valeur -- entier

    renvoie True si valeur est dans tab, False sinon.
    La recherche est faite suivant le principe de dichotomie.
    """
    gauche, droite = 0, len(tab)-1


    while gauche <= droite:
        centre = milieu(gauche, droite)
        if tab[centre] == valeur: return True
        if tab[centre] < valeur:
            gauche, droite = centre+1, droite
        else:
            gauche, droite = gauche, centre-1

    return False

le corps de la boucle:

centre = milieu(gauche, droite)
if tab[centre] == valeur: return True
if tab[centre] < valeur:
    gauche, droite = centre+1, droite
else:
    gauche, droite = gauche, centre-1

prend un temps à peu près constant à chaque passage.

La différence de temps entre deux exécutions de l'algorithme sur deux listes sera principalement due à la différence de nombre de passages dans la boucle.

On utilise donc dans cette page le nombre de passages dans la boucle pour établir quelques propriétés du temps de calcul d'une recherche par dichotomie.

Avec le même nombre d'éléments

On dispose de deux listes (triées en ordre croissant) $L_1$ et $L_2$ contenant le même nombre d'éléments. On recherche un élément $a$ dans ces listes (en utilisant le programme rappelé ci-dessus).

Est-ce que le nombre de passages dans la boucle sera nécessairement le même pour ces deux listes ?

Solution

La réponse est non.

• Recherchons par exemple $a=7$ dans la liste L1 = [2, 3, 7, 8, 9]. Dès le premier passage dans la boucle, on a L1[centre] = a. On compte donc un seul passage dans la boucle.

• Recherchons maintenant cette même valeur $a=7$ dans la boucle L2 = [2, 3, 6, 8, 9].

  • Au premier passage, on a centre = 2, L2[centre] = 6 et (gauche, droite) 🠐 (3, 4).
  • Au second passage,centre = 3, L2[centre] = 8 et (gauche, droite) 🠐 (3, 2).

Le nombre de passages dans la boucle n'est pas donc pas constant sur les listes de même taille.

Notation

Pour des listes de taille n, on notera p(n) le nombre de passages "au pire" dans la boucle.

p(n) désigne donc le plus grand nombre de passages dans la boucle possible lorsqu'on effectue une recherche d'un élément dans les listes de n éléments.

Exemple

Avec l'exercice précédent et n = 5, on a vu que p(5) ≥ 2 puisqu'on a explicité un cas où il fallait deux passages dans la boucle.

En doublant la taille de liste

Pour les listes à 1 048 576 éléments, on a donc au pire p(1 048 576) passages dans la boucle.

On considère maintenant les listes à 2 097 153 éléments.
Pouvez-vous expliciter un lien entre p(1 048 576) et p(2 097 153) ?

Attention

Si vous avez pensé p(2 097 153) ≈ 2 × p(1 048 576) car 2 097 153 ≈ 2 × 1 048 576... vous avez mal pensé!

Réfléchissez encore.

Solution

Revenons à notre algorithme.

Au premier passage dans la boucle, si l'élément central n'est pas le bon, on cherche alors l'élément dans la moitié gauche ou dans la moitié droite de la liste.

Comme 2 097 153 = 2 × 1 048 576 + 1, chacune des sous-listes gauche et droite a une taille de 1 048 576, donc nécessitera au plus p(1 048 576) passages dans la liste.

On a donc p(2 097 153) = p(1 048 576) + 1.

Important

De façon plus générale, on retiendra ce lien pour l'algorithme de recherche dichotomique:

p(2k) ≈ p(k) +1.

En multipliant la taille de liste par 2, on ajoute environ un passage de boucle dans la recherche dichotomique (dans le cas au pire).

On retiendra également l'argument permettant de justifier cela: à chaque passage échouant à trouver l'élément, la taille de liste est divisée par environ 2. On passe donc d'une liste de taille 2k à une liste de taille k en un seul passage de boucle.

Multiplier la taille de liste par 2³

Quel lien approximatif entre p(1 000 000) et p(8 000 000) ?

Solution

En utilisant la propriété précédemment citée:

p(8 millions) ≈ p(4 millions) +1
p(4 millions) ≈ p(2 millions) +1
p(2 millions) ≈ p(1 million) + 1.

Soit p(8 millions) ≈ p(1million) + 3.

Multiplier la taille de liste par 2^k

Quel lien entre p(n) et p(n× 2^k) ?

Solution

p(n× 2^k) ≈ p(n) + k