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
Réponses
-
Il semble qu'AD a déplacé ton message et y a ajouté un titre contenant une indication précieuse : dichotomie.
[Oui, j'avoue :-D AD] -
La dichotomie consiste à couper un dico en deux.
e.v.Personne n'a raison contre un enfant qui pleure. -
.
-
Que compare-t-on au sein de ce dictionnaire et jusqu'à quel terme au juste ?
Ici, c'est l'art de garder la partie retenue, pour trouver la moitié qui convient ! -
Hello Mwindman, bonjour à tous
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 -
.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres