¿Cómo se determina la altura de un árbol de recursión a partir de una relación de recurrencia?

Question

¿Cómo se puede determinar la altura de un árbol de recursión, construido cuando se trata de recurrencia de tiempos de ejecución? ¿Cómo difiere de la determinación de la altura de un árbol regular?

alt text http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/ch4-9.gif

Edit: Lo siento, me refiero a añadir cómo obtener la altura del árbol recursividad de la relación de recurrencia.

Answer 1

La altura del árbol de recursión depende del algoritmo recursivo en cuestión. No todos los algoritmos de división y conquista tienen árboles de altura uniformados, del mismo modo que no todas las estructuras de los árboles tienen alturas uniformes. Si no puede determinar la altura máxima posible del algoritmo, o si necesita calcular la altura real del árbol en tiempo de ejecución, puede usar una variable global para la función recursiva, incrementarla a la entrada de la función y disminuirla sobre la salida de la función. Esta variable indicará el nivel actual del procedimiento recursivo. Si es necesario, puede mantener el valor máximo de esta variable en una segunda variable.

Answer 2

En primer lugar, si esta es una pregunta para la tarea, márquela como tal. Las imágenes que vinculan implican que está en CS 455, con el profesor Wisman. :)

La pista principal que voy a dar es esta: la altura del árbol está obviamente determinada por cuando llegas a las "hojas". Las hojas de un árbol que modelan la relación de recurrencia de una función son el caso base. Por lo tanto, miraría hacia ver cómo "N" rápidamente puede reducirse al caso base.

Answer 3

Si recurrencia tiene la forma de T (n) = aT (n/b) + f (n), entonces la profundidad del árbol es log base b de n.

Por ejemplo, 2T (n/2) + n periodicidad tendrían árbol de profundidad lg (n) (base de registro 2 de n).