Algorithme, dichotomie
Bonjour !
Aidez-moi ! Voici le problème.
Un dictionnaire contient (2exposant n)-1 mots.
Quel est le nombre maximal de comparaisons pour trouver un mot dans le dictionnaire contenant (2exposant 16)-1=65635 mots. En supposant qu'une comparaison prend 1 seconde, quel est le temps maximal de recherche d'un mot ?
J
Aidez-moi ! Voici le problème.
Un dictionnaire contient (2exposant n)-1 mots.
Quel est le nombre maximal de comparaisons pour trouver un mot dans le dictionnaire contenant (2exposant 16)-1=65635 mots. En supposant qu'une comparaison prend 1 seconde, quel est le temps maximal de recherche d'un mot ?
J
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
[Oui, j'avoue :-D AD]
e.v.
Ici, c'est l'art de garder la partie retenue, pour trouver la moitié qui convient !
L'info "dichotomie" est en effet précieuse.
Dans un dictionnaire de 2^16 mots la recherche par dichotomie trouvera une occurrence en maximum 16 tests (donc 16 secondes dans ton cas).
Par contre, cette méthode de recherche ne peut marcher que dans le cas où les entrées de ton dictionnaire sont triées et que tu sais déterminer si la valeur recherchée est < ou > à une entrée quelconque du dictionnaire.
Il existe d'autres techniques de recherche qui peuvent s'appliquer à un ensemble de valeurs non triées, comme les tables de hachage, qui peuvent être très performantes sur des gros volumes de données non ordonnés.
En conclusion tout dépend de comment sont organisées tes données dans le dictionnaire.
Patrick