Describiré cómo me gusta pensar en preguntas como esta.
La recursión se puede visualizar como atravesar un árbol, donde cada nodo representa una cierta forma de romper un prefijo de la cadena, y sus hijos directos representan las posibilidades para el siguiente salto de palabra. (¡Dibuje un árbol así! Intente ver cómo el algoritmo atraviesa todas sus ramas).
Cada borde del árbol representa una subcadena de la cadena de entrada. Para cada carácter, se realiza una búsqueda en el diccionario.
- ¿Cuál es el mejor libro de texto en línea gratuito para Algorithm an Data Structure? Me refiero a un libro de texto para un estudiante principiante en la universidad.
- ¿Puede una máquina Turing aceptar una cadena de longitud 2014? ¿Por qué este problema es indecidible?
- ¿Cómo funciona el algoritmo de fijación de precios de Megabus?
- ¿Convertir el tamaño de matriz en un número primo ayuda en la implementación de la tabla hash? ¿Por qué?
- ¿Cuáles son los 10 algoritmos que uno debe conocer para resolver la mayoría de los problemas de algoritmos?
Entonces, el número total de búsquedas de diccionario es la suma de las longitudes de los bordes en el árbol .
Ahora, esto es difícil de expresar en términos de cantidades simples como la longitud de la cuerda, pero podemos simplificar sobrestimando la suma de las longitudes de los bordes por la suma de las longitudes de todos los caminos desde la raíz hasta la hoja. (Por lo tanto, estamos tratando de obtener un límite superior ahora). Ahora las cosas se vuelven más fáciles porque cada ruta tiene una longitud n (la longitud de la cadena), y el número de hojas es igual al número de soluciones s.
Entonces, el número de búsquedas de diccionario es como máximo n * s. ¡Hurra!
Finalmente, la implementación del diccionario en el sitio web vinculado es muy pobre, se repite en cada palabra del diccionario. Sea d el tamaño del diccionario, entonces esto cuesta otro factor d.
Por lo tanto, el tiempo total de cálculo es como máximo n * s * d búsquedas de diccionario de una sola palabra. Esto no es muy bueno: se podría evitar fácilmente recorrer todo el diccionario. Además, se podría guardar una gran cantidad de trabajo si se unen los nodos del árbol que representan el mismo prefijo, de modo que sus descendientes deben procesarse solo una vez. (Eso se llama programación dinámica).
