Lección 20: Árboles de recursión:
Un árbol de recursión es útil para visualizar lo que sucede cuando se repite una recurrencia. Diagrama el árbol de llamadas recursivas y la cantidad de trabajo realizado en cada llamada.
Por ejemplo, considere la recurrencia
T (n) = 2T (n / 2) + n2 .
- Dada la matriz a [n + 1] de elementos 1 <= a [i] <= n, ¿de cuántas maneras podemos elegir k de n + 1 sin repetición?
- He pensado en un algoritmo simple y cómo algunas empresas podrían usarlo. ¿Cómo puedo ganar dinero con eso?
- Cómo entender el algoritmo maestro del documento sobre la resolución del isomorfismo gráfico en tiempo cuasi polinomial
- ¿Qué define una solución óptima con respecto al problema de la mochila 0-1?
- ¿Por qué necesitamos un árbol AVL en informática?
El árbol de recursión para esta recurrencia tiene la siguiente forma:
En este caso, es sencillo sumar a través de cada fila del árbol para obtener el trabajo total realizado en un nivel dado:Esta es una serie geométrica, por lo tanto, en el límite, la suma es O (n2) . La profundidad del árbol en este caso realmente no importa; La cantidad de trabajo en cada nivel está disminuyendo tan rápidamente que el total es solo un factor constante más que la raíz.
Los árboles de recursión pueden ser útiles para ganar intuición sobre la forma cerrada de una recurrencia, pero no son una prueba (y de hecho es fácil obtener la respuesta incorrecta con un árbol de recursión, como es el caso con cualquier método que incluya ” … ” tipos de razonamiento). Como vimos la última vez, una buena forma de establecer una forma cerrada para una recurrencia es hacer una suposición educada y luego demostrar por inducción que su suposición es realmente una solución. Los árboles de recurrencia pueden ser un buen método para adivinar.
Consideremos otro ejemplo,
T (n) = T (n / 3) + T (2n / 3) + n .Expandiendo los primeros niveles, el árbol de recurrencia es:
Tenga en cuenta que el árbol aquí no está equilibrado: el camino más largo es el más a la derecha y su longitud es log3 / 2 n . Por lo tanto, nuestra suposición para la forma cerrada de esta recurrencia es O (n log n) .
