algorithm - Trie complejidad y búsqueda.

data-structures time-complexity

Question

¿Cuál es la complejidad de crear una lista de palabras y la complejidad de buscar otro conjunto de palabras en esa lista? ¿Debo usar trie para la búsqueda de cadenas, cuando tengo la tabla hash?

Answer 1

La complejidad de crear un trie es O(W*L) , donde W es el número de palabras y L es una longitud promedio de la palabra: debe realizar L búsquedas en el promedio de cada una de las palabras W en el conjunto .

Lo mismo ocurre con la búsqueda de palabras más adelante: realiza L pasos para cada una de las W palabras.

Las inserciones de hash y las búsquedas tienen la misma complejidad: para cada palabra que necesita para verificar la igualdad, que toma O(L) , para la complejidad general de O(W*L) .

Si necesitas buscar palabras completas, hash table es más fácil. Sin embargo, no puede buscar palabras por su prefijo utilizando una tabla hash; Si las búsquedas basadas en prefijos no le interesan, use una tabla hash; de lo contrario, use un trie.