Hola, escribo por una duda con respecto al tiempo de ejecución de FIND-WORD en Dictionary.
Se nos pide tiempo $\mathcal{O}(1)$, lo que entiendo que implica revisar en una tabla de hash, cosa que comenté con un profesor. Con esto me surge una duda: Calcular el hash de una palabra generalmente implica recorrer toda la palabra, lo que es tiempo $\mathcal{O}(L)$. Existen formas de calcular el hash en tiempo $\mathcal{O}(1)$, pero estas formas implican más colisiones (por ejemplo considerando una cantidad fija de caracteres) o requieren una tabla innecesariamente grande para evitar estas colisiones. Además, en cualquier caso se debe corroborar que el resultado sea el correcto, para lo que se debe comparar igual el string encontrado con el string entregado. Si bien esto se puede hacer un solo llamado a la función $\texttt{strcmp}$, esta función también recorre el string completo. En resumen, esta operación, si bien se puede esconder como $\mathcal{O}(1)$, realmente es $\mathcal{O}(L)$.
Dicho esto, yo había implementado una revisión que simplemente recorre el árbol usando cada letra del string como índice para saber a qué árbol avanzar, por lo que encuentra si la palabra existe en tiempo $\mathcal{O}(L)$ (como máximo se harán $L$ pasos, nunca más, y si la palabra no existe, entonces menos), lo que termina siendo igual o más rápido que la implementación de la tabla de hash, y mucho más eficiente en memoria.
Los tests me dan todos bien, entonces quería preguntar si es válida mi implementación (a pesar de ser $\mathcal{O}(L)$ y no $\mathcal{O}(1)$), y si puedo dejarla y mencionar la forma de hash en el informe para explicar que sí lo entiendo, o si es necesario que implemente la función de hash.
Muchas gracias!
