-
|
Hola, ya habían preguntado sobre la complejidad y dijeron que a nivel global se tendría nlogn +MxK, lo que implicaría aproximadamente recorrer cada cadena que se busca (largo M por K veces). Mi duda va a que en la cápsula dijeron que para manejar colisiones, se debería crear otra función que compruebe cada coincidencia por si se dio la casualidad de tener el mismo hash. ¿El uso de esta función tendría que tomar una complejidad menor a M para cumplir con lo esperado? Y si es así ¿se cuenta alguna cantidad esperada de colisiones para la complejidad de tal función? (ya que la usaría C veces por cadena, donde C es la cantidad de colisiones) Al final pregunto si C es despreciable en comparación a M, ya que en ese caso se seguiría una complejidad aprox de M por cada consulta. |
Beta Was this translation helpful? Give feedback.
Replies: 1 comment 2 replies
-
|
Hola, al final la idea es que crees una tabla de hash lo suficientemente grande para manejar las colisiones. |
Beta Was this translation helpful? Give feedback.
-
|
Yaa, gracias. Con respecto a eso también me surge la duda de la función auxiliar para comprobar colisiones. Como pueden haber subárboles distintos con mismo hash, debo ocupar esta función auxiliar para que verifique si es en verdad la que busco. ¿Esta debería tener complejidad O(M)? ya que yo pensaría que en esas instancias se debería revisar caracter por caracter (siendo que son M caracteres a comprobar). Es una función que se ocuparía C (cantidad de colisiones) veces por consulta, es decir cada consulta tendría complejdad aprox O(C*M), pero no sé si está bien que esta función auxiliar sea así o debo buscar otra que tenga complejidad menor. Gracias de antemano. |
Beta Was this translation helpful? Give feedback.
-
|
Si, creo que lo que dices es correcto, pero como te dije arriba, la idea es crear una funcion de hash que permita distribuir lo más uniformemente posible los valores dentro de la tabla de hash, cosa que si te quedan C colisiones, este número no sea significativo para aumentar la complejidad de búsqueda |
Beta Was this translation helpful? Give feedback.
Hola, al final la idea es que crees una tabla de hash lo suficientemente grande para manejar las colisiones.
Con un buen tamaño de tabla y una buena función de hash, puedes lograr que los valores de los árboles se distribuyan uniformemente a lo largo de la tabla.
Igual puedes tener colisiones, pero ojo con el número, por ejemplo, si guardas todos los árboles de altura 2 en una misma celda de la tabla ya te pasarías de la complejidad.
Se entiende?