1NSI: Algorithmique - Recherche par Dichotomie⚓︎
Contenus | Capacités Attendues | Commentaires |
---|---|---|
Recherche dichotomique dans un tableau trié |
Montrer la terminaison de la recherche dichotomique à l’aide d’un variant de boucle. |
Des assertions peuvent être utilisées. La preuve de la correction peut être présentée par le professeur. |
Introduction⚓︎
Problématique⚓︎
Comment rechercher efficacement dans un Tableau (une liste en Python) préalablement TRIÉ ?
Rappel : Parcours Séquentiel d'un Tableau (NON trié)⚓︎
Rappelons que lorsqu'un Tableau n'est pas trié, nous disposons déjà de l'algorithme de Parcours Séquentiel d'un Tableau (non trié).
L'entier \(n\) désignant la taille du tableau, càd le nombre d'éléments qu'il contient.
La complexité/coût de cet algorithme était linéaire (en \(n\)), càd en \(O(n)\).
La méthode que nous allons utiliser implique que les valeurs aient été triées auparavant.
Un Exemple : le Jeu du Nombre Mystère⚓︎
Le Jeu⚓︎
On souhaite jouer au jeu suivant, dit "du nombre Mystère" : si je choisis un nombre entre \(1\) et \(100\), quelle est la stratégie optimale pour deviner ce nombre le plus vite possible ? (à chaque étape, une indication -trop grand, trop petit- permet d'affiner la proposition suivante)
Réponse attendue
Intuitivement, la meilleure stratégie est de couper en deux à chaque fois l'intervalle d'étude. On démarre de 50, puis 75 ou 25, etc.
Il convient toutefois de remettre en question cette méthode qui paraît naturellement optimale : si je propose 90 comme nombre de départ, j'ai certes moins de chance que le nombre soit entre 90 et 100, mais s'il l'est, j'ai gagné un gros avantage car mon nouvel intervalle est très réduit.
On peut alors rappeler la notion d'espérance probabiliste.
Exp
On lance un dé, s'il tombe sur le 6 vous recevez 2 euros, sinon vous me donnez 1 euro. Voulez-vous jouer ?
Quelques Statistiques de Jeu⚓︎
Le graphique ci-dessous représente le nombre de coups moyens (sur 10 000 parties simulées)
- si le choix se porte toujours sur le nombre situé à la moitié de l'intervalle (0.5), le nombre de coups moyen avant la victoire (sur 10 000 parties) est environ 6.
- si le choix se porte toujours sur le nombre situé à 90 % de l'intervalle (0.9), le nombre de coups moyen avant la victoire (sur 10 000 parties) est environ 11.
- l'asymétrie de la courbe (qui devrait être symétrique) est due aux arrondis par défaut dans le cas de nombres non entiers.
Conclusion⚓︎
La stratégie optimale est donc bien de diviser en deux à chaque étape l'intervalle d'étude. On appelle cela une méthode par dichotomie, du grec ancien διχοτομία, dikhotomia (« division en deux parties »).
La méthode de dichotomie fait partie des méthodes dites Diviser Pour Régner ou quelquefois Diviser pour mieux Régner.
En algorithmique 1, les méthodes diviser pour régner (du latin « Divide ut imperes », divide and conquer en anglais) sont des techniques qui se décomposent usuellement en \(3\) étapes :
Diviser càd découper un problème initial en sous-problèmesRégner càd résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits)Combiner càd calculer une solution au problème initial à partir des solutions des sous-problèmes.
Généralisation à un Tableau Trié⚓︎
Animation⚓︎
- Modifiez (ou pas) la Valeur Cible (à rechercher dans la liste aléatoire)
- Cliquez sur le bouton
Étape Suivante pour réaliser la comparaison suivante - Répétez l'
Étape Suivante autant de fois que nécéssaire, jusqu'à atteindre la valeur cible (ou pas, si elle n'est pas dans la liste) - Cliquez sur le bouton
Reset pour réinitialiser les entiers aléatoires. Vous pouvez en profiter pour modifier une nouvelle Valeur Cible.
Principe de la Recherche Dichotomique⚓︎
Le Principe de la Recherche par Dichotomie dans un Tableau Trié / Algorithme de Recherche Dichotomique (dans un Tableau trié) / Algorithme par Dichotomie (dans un Tableau trié), ou Binary Search (in ordered Table) est la généralisation de la méthode précédente du nombre mystère. Mais Comment la réaliser en pratique ?
Considérons par exemple la liste L suivante :
L = [2, 3, 6, 7, 11, 14, 18, 19, 24]
L'objectif est de définir un algorithme de recherche efficace d'une valeur cible (arbitrairement choisie à l'avance) présente dans cette liste.
Détaillons un exemple spécifique⚓︎
Par exemple, Recherchons par Dichotomie la valeur \(14\) dans notre liste triée L
.
Étape \(1\) Toute la liste est initialement à traiter. Dans le cas (comme initialement ici) d'un nombre impair (\(9\)) d'éléments restant à traiter (correspondant à des indices compris entre \(0\) et \(8\) inclus), il existe un élément central qui tombe juste (ici \(11\)), qui sépare la partie strictement à sa gauche ([2,3,6,7]
) et la partie strictement à sa droite ([14,18,18,24]
) en deux listes exactement de même taille. Ici, l'indice (\(milieu=4\)) de l'élément central (\(11\)). Mais comment a-t-on calculé cet indice \(milieu=4\) ? On utilise :- La formule mathématique :
\(milieu = \lfloor \dfrac{gauche+droite}{2} \rfloor\) - ce qui s'écrit en Python :
milieu = (gauche + droite) // 2
milieu
l'indice central du prochain élément/valeur à tester (au "milieu" de gauche et droite)gauche
désigne l'indice le plus à gauche / extrémité gauche des éléments restants (à traiter) de la listedroite
désigne l'indice le plus à droite / extrémité droite des éléments restants (à traiter) de la liste- \(\lfloor x \rfloor\) désigne la partie entière du flottant/réel \(x\)
(par exemple : \(\lfloor 4,8 \rfloor=4\); \(\lfloor 2,35 \rfloor=2\); \(\lfloor 3 \rfloor=3\); \(\lfloor -1,3 \rfloor=-2\))
- L'indice \(milieu=4\) qui correspond au prochain élément/valeur à tester, (\(11\)) de la liste, se calcule donc par la formule :
\(milieu = \lfloor \dfrac{0+8}{2} \rfloor = \lfloor 4 \rfloor = 4 \Rightarrow\) le prochain est l'élément d'indice \(4\) dans la liste
- La formule mathématique :
Étape \(2\) On compare \(11\), d'indice \(4\), à la valeur cible recherchée (\(14\)) : or \(14 \gt 11\), donc il faut garder tout ce qui est (strictement) supérieur à \(11\). On pose doncgauche=5
etdroite=8
. Il reste donc un nombre pair (\(4\)) éléments à tester.Étape \(3\) Dans le cas d'un nombre pair (ici, \(4\)) d'éléments restants à tester, il n'y a pas réellement d'élément central (cela ne tombe pas juste). Néanmoins, la même méthode peut s'appliquer pour calculer l'indice (milieu
) de l'élément/valeur suivant à tester :
\(milieu = \lfloor \dfrac{gauche+droite}{2} \rfloor = \lfloor \dfrac{5+8}{2} \rfloor = \lfloor \dfrac{13}{2} \rfloor = \lfloor 6,5 \rfloor = 6 \Rightarrow\) Le prochain élément/valeur à tester correspond à l'indice \(6\) : c'est le nombre \(18\)Étape \(4\) On compare la valeur \(18\), d'indice \(6\), à la valeur cible recherchée (\(14\)). Or \(18>14\) donc on garde ce qui est à gauche (en se souvenant tout de même que \(14>11\)). On pose doncgauche=5
etdroite=5
: Il n'y a plus qu'une seule valeur à tester : c'est le nombre \(14\) qui se trouve à l'indice \(5\)Étape \(5\) On se place sur la valeur \(14\) (car \(milieu = \lfloor \dfrac {5+5}{2} \rfloor = \lfloor \dfrac {10}{2} \rfloor = \lfloor 5 \rfloor=5\)) et on compare avec \(14\). La valeur cible (\(14\)) a bien été trouvée!
Résumé⚓︎
Résumé d'un Algorithme de Recherche par Dichotomie :
- on se place au milieu de la liste.
- on regarde si la valeur cible recherchée est inférieure ou supérieure à la valeur du milieu.
- on ne garde que la bonne moitié de la liste restante qui nous intéresse, et
- on recommence jusqu'à trouver la valeur cible. ou pas (si elle n'est pas dans la liste..)
L'Algorithme de Recherche Dichotomique en Python⚓︎
Contre-intuitivement, Bien que les idées derrière l'Algorithme de Dichotomie semblent simples et directes par rapport à d'autres, les détails de son implémentation pratique peuvent étonnamment poser des problèmes d'une difficulté inattendue (Ce n'est pas moi qui le dit, c'est quelqu'un d'intelligent..)
Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky
Donald Knuth, 1998, Searching an ordered Table
Nous allons travailler avec deux variables gauche
et droite
qui vont délimiter les indices de la liste à étudier. Ces indices sont représentés en bleu sur la figure ci-dessous. La valeur du milieu
(représenté en rouge) sera égale à (gauche + droite) // 2
Le programme s'arrête lorsque la valeur cherchée a été trouvée, ou lorsque droite
devient strictement inférieur à gauche
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
L = [2, 3, 6, 7, 11, 14, 18, 19, 24]
print(recherche_dico(L,14))
print(recherche_dico(L,2))
print(recherche_dico(L,24))
print(recherche_dico(L,1976))
5
0
8
None
En cas de problème de visualisation, cf l'animation sur cette page du site PythonTutor
Terminaison de l'algorithme⚓︎
Est-on sûr que l'algorithme va se terminer ?
La boucle while
utilisée doit nous inciter à la prudence, il y a en effet plusieurs risques (voir cours sur la boucle while
) :
- de ne jamais entrer dans la boucle
while
- de ne jamais sortir de la boucle
while
(càd de rentrer dans une boucle infinie)
Alors pourquoi est-on sûr que ce n'est pas le cas ?
On note
Nous allons montrer que cette quantité est un Variant de Boucle, càd qu'il vérifie les conditions suivantes :
- \(v\) est un nombre entier
- \(v\) est initialement strictement positif, car initialement:
- \(gauche=0\) et \(droite\ge 0\), donc
- \(v = droite-gauche+1 = droite-0+1 \ge 0 + 1>0\)
- \(v=droite-gauche+1\) décroit d'au moins un cran à chaque itération (ou bien on a trouvé la valeur cible), car on est forcément dans l'une des \(3\) situations suivantes :
- ou bien c'est la gauche qui augmente d'au moins \(1\) cran (Ligne \(11\)), car \(milieu+1\ge gauche+1\), et pendant ce temps la droite est inchangée. Auquel cas, la valeur \(v=droite-gauche+1\) diminue d'au moins 1 cran (car on enlève davantage)
- ou bien c'est la droite qui diminue d'au moins \(1\) cran (Ligne \(13\)), car \(milieu-1\le droite-1\), et pendant ce temps la gauche est inchangée. Auquel cas, \(v=droite-gauche+1\) diminue d'au moins \(1\) cran.
- ou bien on a trouvé la bonne solution (ligne \(15\))
- la condition \(v\le 0 \Leftrightarrow droite-gauche+1 \le 0 \Leftrightarrow droite -gauche \le -1 <0\) correspond bien à la sortie de la boucle
Correction de l'Algorithme⚓︎
L'algorithme fait-il ce qu'il censé faire? Est-il correct?
Notons provisoirement g=gauche
, d=droite
et m=milieu
.
L'algorithme est plus subtil qu'il n'y paraît de prime abord.
Commençons par montrer que l'algorithme ne va pas échouer en raison d'un dépassement (trop à gauche ou trop à droite) des bornes du tableau L :
- Tout d'abord, remarquons que chacune des inégalités
g>=0
etd <= n-1
est un invariant de boucle - Ensuite, à l'intérieur de la boucle (puisque
g <= d
, on a toujours :0 <= g <= d <= n-1
- Enfin, le tableau
L
n'est accédé que par la valeur dem=(g+d)//2
qui est le milieu de gauche et droite (arrondi à l'entier inférieur), ce qui garantit un accès légal au tableau
On note C
ne peut se trouver que dans L[g..d]
»
Montrons qu'il s'agit bien d'un invariant de boucle :
- Initialisation : Inv est vrai initialement, car on a initialisé les variables à
g=0
etd=n-1
- Hérédité/Conservation : Supposons que Inv soit vrai en entrant dans une certaine itération :
- Si
g
est modifié, parg=m+1
alors l'invariant Inv est préservé, car le tableau est trié etC>L[m]
- Si
d
est modifié, pard=m-1
alors l'invariant Inv est préservé, car le tableau est trié etC<L[m]
- Il y a donc bien conservation en fin d'itération, donc en début de la suivante
- Si
- Terminaison :
- soit, durant une certaine itération, on renvoie un entier
m
(ligne 12) qui vérifie alors obligatoirementL[m]=C
d'après les 2 tests précédents (à la ligne 7 et ligne 9), doncm
est bien le bon indice correspondant àC
dansL
. Ceci prouve que l'algorithme est correct dans le cas où la valeur cibleC
appartienne bien au tableauL
. - soit, on renvoie
None
: Remarquons que dans ce cas on est obligatoirement allé jusqu'au bout de la boucle while le plus longtemps possible, et que dans ce cas forcément, on avaitg=d
durant le dernier tour (sinon, si on avaitd>=g+1
, alors on aurait pu refaire encore un tour). De plus, on sait d'après l'hérédité queC
se trouve obligatoirement dansL[g..d]=L[g..g]
, ceci prouve que si on renvoieNone
, c'est que ce dernier test a échoué durant la dernier itération (doncC!= L[g]
etL[g]
était la dernière valeur restante à tester). Ensuite, on sort de la boucle (en incrémentantg
de 1, ou décrémentantd
de 1 selon la situation) pour parvenir à la ligne \(13\). Cela prouve donc que la valeur cibleC
n'appartient pas au tableauL
, et donc que l'algorithme est correct dans le cas où la valeurC
n'appartienne pas au tableauL
.
- soit, durant une certaine itération, on renvoie un entier
Complexité de l'Algorithme⚓︎
Calcul de la Complexité/Coût⚓︎
A une constante multiplicative près, il revient au même de compter le nombre d'opérations que le nombre d'étapes. Nous nous concentrerons sur le nombre d'étapes réalisées : mais combien d'étapes (au maximum, càd dans le pire des cas) sont-elles nécessaires pour arriver à la fin de l'algorithme ?
Ce qui suit est un raisonnement plus qu'une démonstration. Nous nous en satisferons.
Imaginons que la liste initiale possède \(8\) valeurs :
- Après \(1\) étape, il ne reste que \(4\) valeurs à traiter
- Après \(2\) étapes, il ne reste que \(2\) valeurs
- Après \(3\) étapes, il ne reste qu' \(1\) seule valeur
A chaque étape, le nombre de valeurs restantes à traiter est divisée par \(2\). Il y a donc \(3\) étapes avant de trouver la valeur cherchée, car \(2^3=8\).
Ex
-
Remplissez le tableau ci-dessous :
taille de la liste 1 2 4 8 16 32 64 128 256 nombre d'étapes _ _ _ 3 _ _ _ _ _ -
Pouvez-vous deviner le nombre d'étapes nécessaires pour une liste de \(4096\) termes ?
- Pour une liste de \(2^p\) termes, quel est le nombre d'étapes ?
- Pour une liste de \(n\) termes, quel est le nombre d'étapes ?
Notation
On note
Ce nombre est appelé le logarithme binaire de \(n\), ou logarithme en base \(2\) de \(n\).
Le nombre d'étapes nécessaires, càd la complexité/coût en temps de l'Algorithme par Dichotomie, est donc (un multiple de) \(log_2(n)\).
Ex
Créer une fonction log2(n:int)->int
qui renvoie le logarithme binaire \(p=log_2(n)\) d'un entier \(n\)
Une démonstration plus mathématique? + Master Theorem
Nous allons montrer qu'à chaque nouvelle itération (en supposant qu'on ne trouve pas C
au milieu à cette itération), on divise par \(2\) le nombre de possibilités restantes à tester (en arrondissant à l'entier directement inférieur).
Notons provisoirement L[g..d]
, càd le nombre d'éléments restants à tester à une certaine itération.
- Ou bien, la valeur
C
est la valeur au milieu entreg
etd
, càd queC
est la valeur cible et elle sera trouvée à l'itération suivante. Cela correspond au cas oùC = L[m]
oùm=(g+d)//2
. Dans ce cas, pas besoin d'étudier la diminution de la taille du tableau des éléments restants à traiter entre eux itérations, puisque l'algorithme s'arrête à l'itération suivante. Nous supposerons que nous ne sommes pas dans ce cas. - Ou bien
C
n'est pas la valeur située au milieu deg
etd
(càd supposons queC!=L[m]
avecm = (g+d)//2
), il ne reste alors plus que deux possiblités:- soit
C>L[m]
auquel casC
se trouve forcément dansL[m+1..d]
, donc le nombre d'éléments restants au tour suivant est un nombre entier \(n'\) tel que \(n'=d-(m+1)+1=d-m\). Ensuite, De deux choses l'une:- Ou bien \(n=d-g+1=2p\) est un nombre pair, auquel cas, \(n'=d-m=\dfrac{n}{2}=p \leq \dfrac{n}{2}\)
- Ou bien \(n=d-g+1=2p+1\) est un nombre impair, auquel cas, \(n'=d-m=\dfrac{n-1}{2}=p \leq \dfrac{n}{2}\) Dans tous les cas (pair ou impair), au tour suivant, il reste au maximum \(\dfrac{n}{2}\) : La taille des éléments à tester a donc été divisée par \(2\)
- soit
C<L[m]
auquel casC
se trouve forcément dansL[g..m-1]
, donc le nombre d'éléments restants au tour suivant est un nombre entier \(n'\) tel que \(n'=(m-1)-g+1=m-g\). Ensuite, De deux choses l'une:- Ou bien \(n=d-g+1=2p\) est un nombre pair, auquel cas, \(n'=m-g\lt \dfrac{n}{2}\)
- Ou bien \(n=d-g+1=2p+1\) est un nombre impair, auquel cas, \(n'=m-g=\dfrac{n-1}{2}=p \leq \dfrac{n}{2}\) Dans tous les cas (pair ou impair), au tour suivant, il reste au maximum \(\dfrac{n}{2}\) nombres à traiter: La taille des éléments à tester a donc été divisée par \(2\) à chaque nouvelle itération.
- Conclusion : Le nombre d'éléments restants à tester à l'itération suivante a été divisé par \(2\) par rapport à l'itération précédente.
- soit
- Notons \(n\) la taille des données en entrée de l'algorithme, càd le nombre d'éléments (déjà triés) dans le tableau initial, et
\(C(n)\) la complexité/coût en temps de l'algorithme, càd le nombre total d'itérations à réaliser pour terminer l'algorithme. Le résultat précédent montre que \(C(n)\) vérifie la relation: \(C(n)=C\left( \dfrac{n}{2} \right)+1\), ou ce qui revient au même :
\(C(2n)=C(n)+1\)
D'après le master theorem, on sait que cette relation correspond à une complexité logarithmique, en \(O(log_2(n))\) : il s'agit donc d'une recherche rapide
Pte
Pour l'algorithme par Dichotomie, la taille des données en entrée, càd le nombre d'entiers restants à traiter, est divisé par \(2\) à chaque nouvelle itération. On dit dans ce cas que l'Algorithme par Dichotomie a une complexité/coût/vitesse logarithmique, càd en \(O(log_2(n)\). Cette dernière notation veut dire que le nombre total d'étapes (d'opérations) pour terminer l'algorithme est égal à une certaine constante multipliée par \(log_2(n)\).
Vérifications Expérimentales⚓︎
Nous allons comparer les complexités/coûts en temps, dans le pire des cas, de l'algorithme par Dichotomie avec celle de l'Algorihtme de parcours séquentiel (par balayage). Dans les deux algorithmes, le pire des cas correspond au cas où l'on recherche le dernier élément (le plus à droite).
Recherche dans 100 000 Valeurs triées⚓︎
Récupérer la liste de 100 000 valeurs⚓︎
Télécharger localement le fichier input_centmille.txt
, et placer-le dans le même répertoire que votre script Python.
# Le snippet suivant permet de transformer le contenu du fichier `input_centmille.txt`
# en une liste L de 100 000 entiers.
f = open("input_centmille.txt",'r')
l = f.readlines()
L = []
for k in l :
L.append(int(k[:-1]))
100 000 valeurs avec Parcours Séquentiel⚓︎
def parcours_sequentiel(C, L) :
for k in range(len(L)) :
if L[k] == C:
return k
return "non trouvé"
Mesurons le temps nécessaire pour trouver l'indice de la dernière valeur de la liste (qui est \(299474\)) avec la méthode de parcours séquentiel :
from timeit import timeit
C = 299474
centmille_sequentiel = timeit("parcours_sequentiel(C, L)", globals=globals(), number=1000) # par défaut : number = 1000000,
print("Temps Parcours Séquentiel = ", centmille_sequentiel)
100 000 valeurs par Dichotomie⚓︎
Mesurons le temps nécessaire pour trouver l'indice de la dernière valeur de la liste (qui est \(299474\)) avec la méthode par dichotomie :
# from timeit import timeit
# C = 299474
centmille = timeit("recherche_dicho(C, L)", globals=globals(), number=1000) # number = 1000000,
print("Temps Algo par Dichotomie = ", centmille)
Comparaison Dichotomie vs Parcours Séquentiel⚓︎
# Pour 100 000 valeurs
Temps Parcours Séquentiel = 0.2935811650022515
Temps Algo par Dichotomie = 0.00019076699391007423
L'algorithme dichotomique est bien plus rapide que l'algorithme de parcours séquentiel :
Pour \(n=100\,000=10^5\) valeurs à trier, le quotient \(\dfrac{temps \,\, séquentiel}{temps \,\, dichotomie}=\dfrac{n}{log_2(n)}\) a pour ordre de grandeur environ \(10^3\).
En effet, \(\dfrac{n}{log(n)} = \dfrac{10^5}{log_2(10^5)} \approx 6020.60\) et \(\dfrac{0.2935811650022515}{0.00019076699391007423} \approx 1538.95\)
Pour cent mille valeurs à trier, l'algorithme par dichotomie est environ \(1\,000\) fois plus rapide que l'algorithme de parcours séquentiel.
Recherche dans 1 000 000 Valeurs triées⚓︎
Récupérer la liste de 1 000 000 de valeurs⚓︎
Télécharger localement le fichier input_million.txt
, et placer-le dans le même répertoire que votre script Python.
# Le snippet suivant permet de transformer le contenu du fichier `input_million.txt`
# en une liste L de 1 000 000 entiers.
f = open("input_million.txt",'r')
l = f.readlines()
L = []
for k in l :
L.append(int(k[:-1]))
1 000 000 valeurs avec Parcours Séquentiel⚓︎
Mesurons le temps nécessaire pour trouver l'indice de la dernière valeur de la liste (qui est \(2999306\)) avec la méthode de parcours séquentiel :
from timeit import timeit
C = 2999306
million_sequentiel = timeit("parcours_sequentiel(C, L)", globals=globals(), number=1000) # par défaut : number = 1000000,
print("Temps Parcours Séquentiel = ", million_sequentiel)
1 000 000 valeurs par Dichotomie⚓︎
Mesurons le temps nécessaire pour trouver l'indice de la dernière valeur de la liste (qui est \(2999306\)) avec la méthode par dichotomie :
# from timeit import timeit
# C = 2999306
million = timeit("recherche_dicho(C, L)", globals=globals(), number=1000) # number = 1000000,
print("Temps Algo par Dichotomie = ", million)
Comparaison Dichotomie vs Parcours Séquentiel⚓︎
# Pour 1 000 000 valeurs
Temps Parcours Séquentiel = 2.6699887700015097
Temps Algo par Dichotomie = 0.0001729260038700886
L'algorithme dichotomique est bien plus rapide que l'algorithme de parcours séquentiel :
Pour \(n=1\,000\,000=10^6\) valeurs à trier, le quotient \(\dfrac{temps \,\, séquentiel}{temps \,\, dichotomie} = \dfrac{n}{log_2(n)}\) a pour ordre de grandeur environ \(10^4\).
En effet, \(\dfrac{n}{log_2(n)} = \dfrac{10^6}{log_2(10^6)} \approx 50171.67\) et \(\dfrac{2.6699887700015097}{0.0001729260038700886} \approx 15440.07\)
Pour un million de valeurs à trier, l'algorithme par dichotomie est environ \(10\,000\) fois plus rapide que l'algorithme de parcours séquentiel.
Taille de la liste & Vitesse de chaque méthode⚓︎
- méthode avec parcours séquentiel: la recherche dans une liste 10 fois plus grande prend environ \(10\) fois plus de temps : la vitesse de l'algorithme est bien proportionnelle à la taille \(n\) de la liste. \(\dfrac{10^6}{10^5} = 10\) et \(\dfrac{2.6699887700015097}{0.2935811650022515} \approx 9.09\)
- méthode par dichotomie: la recherche dans une liste \(10\) fois plus grande prend environ \(1,2\) fois plus de temps : la vitesse de l'algorithme est bien proportionnelle au logarithme de la taille \(n\) de la liste : \(\dfrac{log_2(1\,000\,000)}{log_2(100\,000)} = 1.2\) et \(\dfrac{0.0001729260038700886}{0.00019076699391007423} \approx 0.91\)
Précaution Finale⚓︎
Il ne faut toutefois pas oublier que la méthode dichotomique, bien que beaucoup plus rapide, nécessite que la liste ait été auparavant triée. Ce qui rajoute du temps de calcul ! (cf tri par insertion ou tri par sélection )
Références & Notes⚓︎
Références⚓︎
- Cette page est inspirée de Programmation de la méthode de dichotomie, Gilles Lassus
- L'animation est inspirée de Binary Search, by Yong Daniel Liang