Version imprimable
Bonjour,
je suis amené a construire un tableau contenant une liste de chaîne : Array("A",AB","Améthyste","Avion","Aviron","Bébé","Journal",....) , celui-ci sera trié alphabétiquement et comprendra au max 5000 éléments, j'aimerais savoir comment m'y prendre et avec quel algo afin de pouvoir rechercher tous les éléments commençant par une chaine de recherche donnée sans avoir à parcourir l'ensemble du tableau et avoir les meilleurs temps de réponse possible...
Merci d'avance de votre aide.
t'as pas une fonction "find"?
Si tu as le choix dans la structure de données, tu peux stocker tous les mots en utilisant un arbre lexicographique
La ieme génération dans l'arbre représente la ième lettre du mot....
plus d'info sur le premier lien "arbre lexicographique" dans google. http://www.enseignement.polytechniqu...1/TD/td_6.html
La complexité de la recherche ou l'insertion est en N comparaisons où N est le nombre de lettres du mot.
Si le tableau est imposé, une recherche dichotomique devrait suffire...
Le tableau est imposé mais des éléments peuvent être supprimés/ajoutés.
Je recherche surtout la performance mais j'utlise un langage de script qui ne possède pas de fonction find par exemple; par contre je peux utiliser des expressions régulières...
Dans ces conditions une recherche dichotomique m'apportera t elle la réponse la plus rapide?
Sans structure additionnelle, c'est vraissemblable.Citation:
Envoyé par LEK
Merci de vos réponses.