Complexité et recherche de Trie

Quelle est la complexité de la création d'un trie d'une liste de mots et de ce qu'est la complexité de la recherche d'autres jeu de mot qui trie?
Dois-je utiliser trie pour la chaîne de la recherche, quand j'ai de table de hachage?

source d'informationauteur Varun

  1. 17

    La complexité de la création d'un trie est O(W*L)où W est le nombre de mots, et L est une longueur moyenne du mot: vous devez effectuer L des recherches sur la moyenne pour chaque W mots dans le jeu.

    En va de même pour la recherche de mots plus tard: vous effectuez L étapes pour chacun des W mots.

    De hachage insertions et les recherches ont la même complexité: pour chaque mot, vous devez vérifier l'égalité, qui prend O(L)pour l'ensemble de la complexité de O(W*L).

    Si vous avez besoin de chercher des mots entiers, à la table de hachage est plus facile. Cependant, vous ne pouvez pas rechercher des mots par leur préfixe à l'aide d'une table de hachage; Si le préfixe de la base de recherches sont d'aucun intérêt pour vous, d'utiliser une table de hachage; sinon, utilisez un trie.