Eficiencia parte 3 #136
-
|
Hola, quería preguntar a qué se refieren con resolver de forma eficiente este apartado. Se tiene alguna complejidad para tener en cuenta? |
Beta Was this translation helpful? Give feedback.
Replies: 1 comment 2 replies
-
|
En la pregunta numero 3 , nos referimos a que siendo n el tamaño del arbol, la busqueda debe ser O(n) . Aprovechando, también recordar que para la pregunta 1 se espera tener complejidad O(n) y no O(nL), con n el tamaño del string grande y L el del sub patrón a encontrar. Detalles de como lograrlo se puede ver en el link al paper de Rolling Hashing en el enunciado. |
Beta Was this translation helpful? Give feedback.
-
|
Súper, ¿en ese caso es posible saber con qué materia se espera responder la parte 3? Se que después subirán las cápsulas, pero para ir avanzando antes. Gracias! |
Beta Was this translation helpful? Give feedback.
-
|
hola @4n1t4 , muchas gracias por la respuesta! tengo una confusión con el enunciado, ya que dice "Deberás emplear una estrategia para encontrar estos patrones K de tamaño M en tiempo O(M × K)." En cambio, de este comentario entiendo que la complejidad tiene que ser O(N). Solo se me ocurren soluciones crecientes respecto de N pero decrecientes con respecto de M... ¿me orientarían con esto, por favor? muchas gracias de antemano! |
Beta Was this translation helpful? Give feedback.
En la pregunta numero 3 , nos referimos a que siendo n el tamaño del arbol, la busqueda debe ser O(n) .
Aprovechando, también recordar que para la pregunta 1 se espera tener complejidad O(n) y no O(nL), con n el tamaño del string grande y L el del sub patrón a encontrar. Detalles de como lograrlo se puede ver en el link al paper de Rolling Hashing en el enunciado.