Correction terminaison complexité de la dichotomie

I. Terminaison de l'algorithme de recherche dichotomique

Est-on sûr que l'algorithme va se terminer ?
La boucle while qui est utilisée doit nous inciter à la prudence.
Il y a en effet le risque de rentrer dans une boucle infinie.
Pourquoi n'est-ce pas le cas ?

Aide : observer la position des deux flèches bleues lors de l'exécution de l'algorithme

La condition de la boucle while est indice_debut <= indice_fin, qui pourrait aussi s'écrire indice_fin >= indice_debut.
Au démarrage de la boucle, on a :

🐍 Script Python

    indice_debut = 0
    indice_fin = len(L) - 1

Ceci qui nous assure donc de bien rentrer dans la boucle.

Ensuite, à chaque étape, les deux variables indice_debut et indice_fin vont se rapprocher jusqu'à ce que le programme rencontre un return ou bien jusqu'à ce que indice_fin devienne inférieur à indice_debut.

Ceci nous assure donc que le programme va bien se terminer.

Variant de boucle

On dit que la valeur indice_fin - indice_debut représente le variant de boucle de cet algorithme. Ce variant est un nombre entier, d'abord strictement positif, puis qui va décroître jusqu'à la valeur 0.

II. Complexité de l'algorithme de recherche dichotomique

Nous allons considérer que la complexité est due au nombre d'étapes nécessaires pour obtenir le résultat.

Le pire des cas

Quel est le pire des cas de recherche dichotomique d'une valeur dans une liste triée ?

Solution

Le pire des cas est lorsque l'élément n'est pas présent dans la liste.

Combien d'étapes (au maximum) sont-elles nécessaires pour arriver à la fin de l'algorithme ?
Imaginons que la liste initiale possède 8 valeurs. Après une étape, il ne reste que 4 valeurs à traiter. Puis 2 valeurs.
Puis une seule valeur.
Il y a donc 3 étapes avant de trouver la valeur cherchée.

Nombres d'étapes

1. Remplissez le tableau ci-dessous :

taille de la liste	1	2	4	8	16	32	64	128
nombre d'étapes	_	_	_	3	_	_	_	_

Solution

taille de la liste	1	2	4	8	16	32	64	128
nombre d'étapes	0	1	2	3	4	5	6	7

2. Pouvez-vous deviner le nombre d'étapes nécessaires pour une liste de 4096 termes ?

Solution

12 étapes

3. Pour une liste de \(2^n\) termes, quel est le nombre d'étapes ?

Solution

\(n\) étapes

Nombres d'étapes pour une liste de taille \(n\)

Sachant qu'à chaque itération de la boucle on divise à peu près (division entière) le tableau en \(2\), cela revient donc à se demander combien de fois faut-il diviser le tableau en \(2\) pour obtenir, à la fin, un tableau comportant un seul élément ?
🙃 Autrement dit, combien de fois faut-il diviser n par 2 pour obtenir 1 ?

Le logarithme en base 2

une mesure de la complexité est donc le nombre \(k\) tel que \(2^k=n\).

Nous n'allons pas rentrer dans les détails, mais il faut savoir qu'il existe une fonction mathématique (réciproque de la fonction qui à \(x\) associe \(2^x\)) qui permet de résoudre ce problème :
la fonction "logarithme en base 2" notée \(\text{log}_2\)

\(k=\text{log}_2(n)\)

La courbe en rouge correspond à la complexité de la recherche dichotomique (logarithmique en base 2), et la droite verte à celle de la recherche séquentielle (linéaire).

💚 A retenir

La recherche dichotomique se fait avec une complexité logarithmique.

On rencontrera parfois la notation \(O(\log_2(n))\).

Le \(O\) se prononce "grand O" (la lettre)

Cette complexité est bien meilleure qu'une complexité linéaire. Le nombre d'opérations à effectuer est très peu sensible à la taille des données d'entrée, ce qui en fait un algorithme très efficace.

⚠️ 🌵 Attention cependant, n'oubliez pas que dans le cas de la recherche dichotomique, le tableau doit être trié !

III. Temps de calcul.

Recopier et exécuter le code suivant dans votre éditeur python local (pas en ligne)

🐍 Script Python

from timeit import timeit

def dicho(tableau: list, x: int) -> bool :
    """
    :param tableau: une liste d'entiers triés par ordre croissant
    :param x: de type int
    :returns: bool : True si x est dans tableau, False sinon

    >>> dicho([1, 3, 4, 9], 4)
    True
    >>> dicho([1, 3, 4, 9], 11)
    False
    """
    deb = 0
    fin = len(tableau) - 1
    mil = (deb + fin) // 2

    while deb <= fin :

        if tableau[mil] ==  x:
            return True
        elif tableau[mil] < x:
            deb = mil + 1
        else :
            fin = mil - 1
        mil = (deb + fin) // 2
    return False

tailles = [500, 2500, 12500, 62500]

# tref est le temps de calcul pour une liste de taille 100
liste_ref = [i for i in range(100)]
tref = timeit("dicho(liste_ref, -1)", number = 1000, globals = globals())
print("n = 100 -> tref = ",round(tref, 6))

for n in tailles :
    print("n =", n, end='')
    tab = [i for i in range(n)]
    # Calcul du temps pour des listes triées de tailles n
    t = timeit("dicho(tab, -1)", number = 1000, globals = globals())

    print('\t-> temps = ',round(t, 6), '\t x', round(t/tref, 2) )
    tref = t

Que remarque-t-on?

A chaque étape, n est multilié par 5, et on voit dans le tableau que le temps est multiplié par un nombre très inférieur à 5.

IV. Un exemple spectaculaire de l'efficacité de la recherche par dichotomie

Imaginons un annuaire qui contienne les noms, prénoms, adresses.....des 7 milliards d'êtres humains vivant sur la terre.

🤔 Quel est le nombre maximum d'étapes pour trouver un individu ?

Plaçons nous dans le pire des cas.

Comme à chaque étape on divise le nombre de personne par 2, la question revient à : combien de fois faut-il que je divise 7 milliards par 2 pour qu'il n'en reste qu'un ?

Cela revient à trouver \(n\) tel que \(\dfrac{7000000000}{2^n}=1\) , c’est à dire \(2^n=7000000000\) .

A la calculatrice on voit que \(2^{32}=4294967296\) et que \(2^{33}=8589934592\).

Il faut donc au maximum 33 étapes

🌵 Un algorithme qui balaye la liste du début à la fin aurait fait 1 étape pour la première personne et 7 milliards d'étapes pour la dernière !

Un algorithme par parcours séquentiel de liste aurait nécessité, dans le pire des cas 7 milliards d’étapes. L’algorithme par dichotomie qui n'en nécessite que 33 est donc énormément plus efficace.

Cependant

Cependant, il ne faut pas perdre de vue que dans le cas de la recherche dichotomique, il est nécessaire d'avoir un tableau trié.

Attention

Si au départ le tableau n'est pas trié, il faut rajouter la durée du tri.

V. Le logarithme en base 2

Attention calculatrices

les calculatrices ont une touche log et une touche ln qui donnent respectivement le logaritme en base 10, et le logarithme en base \(\text{e}\).
On peut obtenir le résultat du logarithme en base 2 d'un nombre de la façon suivante, par exemple pour calculer \(\text{log}_2(1024)\) :
( log 1024 ) \(\div\) log 2
ou bien
( ln 1024 ) \(\div\) ln 2

Complément sur les fonctions logarithme

• La fonction \(\text{log}_2\) est la fonction réciproque de celle qui à tout réel \(x\) associe \(2^x\)
• La fonction \(\text{log}\) est la fonction réciproque de celle qui à tout réel \(x\) associe \(10^x\)
• La fonction \(\text{ln}\) est la fonction réciproque de celle qui à tout réel \(x\) associe \(\text{e}^x\)

Le logarithme en base 2 en Python

En Python, il suffit d'importer la fonction log2

Tester le script ci-dessous :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)

Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)

Entrer ou sortir du mode "plein écran"
(Esc)

Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)

Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Exécuter le code
(Ctrl+S)TéléchargerTéléverserRéinitialiser l'éditeurSauvegarder dans le navigateur

VI. Crédits

Auteurs : Gilles Lassus, Jean-Louis Thirot et Mireille Coilhac