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

sintaxis de recursividad

Question

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

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

edit: lo siento, quise agregar cómo obtener la altura del árbol de recursión desde la relación de recurrencia .

Answer 1

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

La pista principal que 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 2

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 3

Si la 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 recurrencia tendría árbol de profundidad lg (n) (log base 2 de n).