Chercher un mot dans un dictionnaire d'un million d'entrées
Dans un million d'éléments triés, la dichotomie trouve en 20 étapes, contre un million au pire pour un parcours simple.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
- Dichotomie, pire cas
- 20 étapes
- Recherche linéaire, pire cas
- 1 000 000 étapes
- Recherche linéaire, cas moyen
- 500 001 étapes
- Gain au pire cas
- × 50 000
La dichotomie suppose une liste déjà triée.
Le cas en détail
Un million d'éléments se divisent par deux 20 fois avant d'arriver à 1. La différence est colossale : 50 000 fois moins d'étapes au pire. C'est ce qui permet aux bases de données de répondre instantanément.
À retenir : Les index des bases de données reposent sur des structures voisines de la dichotomie.
L'exemple chiffré
Valeurs utilisées dans ce cas (des exemples, pas des mesures) :
- Nombre d'éléments de la liste triée : 1000000
- Dichotomie, pire cas
- 20 étapes
- Recherche linéaire, pire cas
- 1 000 000 étapes
- Recherche linéaire, cas moyen
- 500 001 étapes
- Gain au pire cas
- × 50 000
La dichotomie suppose une liste déjà triée.
Modifiez les champs ci-dessus pour adapter le calcul à votre situation : le résultat se met à jour tout de suite.
Comment ça se calcule
La recherche dichotomique compare l'élément cherché au milieu de la liste triée et élimine la moitié à chaque étape : au pire, il faut plancher(log2 n) + 1 étapes. La recherche linéaire parcourt la liste : au pire n étapes, en moyenne environ n / 2 si l'élément est présent.
Les résultats sont fournis à titre indicatif, sans valeur de conseil juridique, fiscal ou financier.