Chercher parmi un milliard d'éléments
Un milliard d'éléments triés se parcourent en 30 étapes avec la dichotomie.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
- Dichotomie, pire cas
- 30 étapes
- Recherche linéaire, pire cas
- 1 000 000 000 étapes
- Recherche linéaire, cas moyen
- 500 000 001 étapes
- Gain au pire cas
- × 33 333 333,3
La dichotomie suppose une liste déjà triée.
Le cas en détail
Un milliard est proche de 2^30. Il suffit donc de trente comparaisons pour retrouver n'importe quel élément. Le nombre d'étapes croît très lentement : multiplier la taille par mille n'ajoute que dix étapes.
À retenir : Le logarithme est la fonction qui « écrase » les grands nombres : retenez que 2^10 vaut environ mille.
L'exemple chiffré
Valeurs utilisées dans ce cas (des exemples, pas des mesures) :
- Nombre d'éléments de la liste triée : 1000000000
- Dichotomie, pire cas
- 30 étapes
- Recherche linéaire, pire cas
- 1 000 000 000 étapes
- Recherche linéaire, cas moyen
- 500 000 001 étapes
- Gain au pire cas
- × 33 333 333,3
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.