tag:blogger.com,1999:blog-7415103.post1919927660962078428..comments2023-08-04T09:51:52.906+02:00Comments on reflexiones de fortran y otras basuras: Renombrando canciones 2.1fortranhttp://www.blogger.com/profile/11425459665752142514noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-7415103.post-65679592895824020442012-08-15T00:05:14.939+02:002012-08-15T00:05:14.939+02:00pues he estado pensando y no compensa, el LCS es O...pues he estado pensando y no compensa, el LCS es O(n·m) y Dijkstra es O(n²), pero aquí hay tantos nodos como pares de letras, así que sería O(n²·m²), mucho peor...<br /><br />además hay que tener en cuenta que la mayor ventaja de Dijkstra es que evita ir por aristas con mucho peso hasta que no se han explorado los caminos que son peores, pero aquí todas las aristas son de peso 1 o 0...fortranhttps://www.blogger.com/profile/11425459665752142514noreply@blogger.comtag:blogger.com,1999:blog-7415103.post-35824652898122833472012-08-14T22:58:19.537+02:002012-08-14T22:58:19.537+02:00Se agradece la tocada de huevines hombre, que hace...Se agradece la tocada de huevines hombre, que hace mucho que nadie me escribe por aquí xD<br /><br />Que conste que con esta implementación top-down del LCS si los strings son iguales (o uno es prefijo del otro) va del tirón hasta el final sin hacer ningún backtracking.<br /><br />De hecho me parece que implementarlo como una búsqueda en un grafo como dices, sería equivalente en complejidad... Me has picado, voy a probarlo :-pfortranhttps://www.blogger.com/profile/11425459665752142514noreply@blogger.comtag:blogger.com,1999:blog-7415103.post-81643340869997919962012-08-14T16:59:24.976+02:002012-08-14T16:59:24.976+02:00Sólo por tocar un poco los huevines...
¿Lo del l...Sólo por tocar un poco los huevines... <br /><br />¿Lo del longest common substring, ya que sólo te interesa su longitud, no sería más eficiente hacerlo con Dijkstra?<br /><br />x = caracteres pasados de Str1<br /><br />y = caracteres pasados de Str2<br /><br />Sería con coste 0 en igualdad, avanzando 1 en x Y en y, 1 en diferencia, avanzando 1 en x O en y.<br /><br />Luego lcs = (x_max + y_max - coste_total) / 2, o algo así... :-P<br /><br />El truco del memoize está bien para evitarse recursiones repetidas, pero explora completamente el espacio de soluciones, mientras que una búsqueda dirigida por Dijkstra puede cortocircuitar las soluciones demasiado absurdas... y el uso de memoria debería ser comparable en el peor caso.Skandalfohttps://www.blogger.com/profile/03657421926790640934noreply@blogger.com