Recherche par interpolation vs Recherche binaire

Afficher la discussion

Améliorer l’article

Enregistrer l’article

J’aime l’article

Afficher la discussion

Améliorer l’article

Enregistrer l’article

J’aime l’article

Recherche d’interpolation fonctionne mieux que la recherche binaire pour un objet trié et Réparti uniformément déployer.

La recherche binaire va à l’élément du milieu pour vérifier quelle que soit la clé de recherche. D’autre part, la recherche d’interpolation peut aller à différents endroits en fonction de la clé de recherche. Si la valeur de la clé de recherche est proche du dernier élément, la recherche d’interpolation est susceptible de commencer la recherche vers la fin.

En moyenne, la recherche par interpolation fait des comparaisons d’environ log(log(n)) (si les éléments sont uniformément distribués), où n est le nombre d’éléments à rechercher. Dans le pire des cas (par exemple lorsque les valeurs numériques des clés augmentent de façon exponentielle), il peut faire jusqu’à O(n) comparaisons.

Article de recherche d’interpolation

Sources:
http://en.wikipedia.org/wiki/Interpolation_search

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *