Quelle est la complexité de la création d'un trie d'une liste de mots et quelle est la complexité de la recherche d'autres mots dans ce trie? Dois-je utiliser trie pour la recherche de chaînes, quand j'ai la hashtable?Trie complexité et la recherche
La complexité de la création d'une structure arborescente est O(W*L), où W est le nombre de mots, et L est une longueur moyenne du mot: vous devez effectuer L recherches sur la moyenne pour chacun des W mots dans l'ensemble.
Il en va de même pour rechercher des mots plus tard: vous effectuez les étapes L pour chacun des mots W.
Les insertions et les recherches de hachage ont la même complexité: pour chaque mot, vous devez vérifier l'égalité, ce qui prend O(L), pour la complexité globale de O(W*L).
Si vous avez besoin de rechercher des mots entiers, la table de hachage est plus facile. Cependant, vous ne pouvez pas rechercher les mots par leur préfixe en utilisant une table de hachage; Si les recherches par préfixe ne vous intéressent pas, utilisez une table de hachage; sinon, utilisez un trie.
Si je regarde le mot entier en hashtable, j'ai besoin d'une bonne fonction de hachage et nous devrions faire attention quand nous définissons la fonction de hachage. Corrigez-moi si je me trompe ... – Varun
@var En raison de l'utilisation généralisée des cordes comme clés des tables de hachage, de très bonnes fonctions de hachage pour les cordes ont été inventées. Une recherche rapide sur internet vous donnerait une demi-douzaine d'excellentes suggestions. Je voudrais aller avec celui que Microsoft utilise, ou celui intégré dans les chaînes Java, car ils ont été beaucoup optimisés. – dasblinkenlight