Comment déterminer la hauteur d'un arbre de récurrence à partir d'une relation de récurrence?

Question

Comment peut-on déterminer la hauteur d'un arbre de récursion, construit en cas de récurrence? En quoi diffère-t-il de la détermination de la hauteur d'un arbre régulier?

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

edit: désolé, je voulais ajouter comment obtenir la hauteur de l'arbre de récursivité de la relation de récurrence.

Answer 1

La hauteur de l'arbre de récurrence dépend de l'algorithme récursif en question. Tous les algorithmes de division et de conquête n'ont pas des arbres en hauteur uniformes, tout comme toutes les structures arborescentes n'ont pas des hauteurs uniformes. Si vous ne pouvez pas déterminer la hauteur maximale possible de l'algorithme, ou si vous devez calculer la hauteur réelle de l'arbre au moment de l'exécution, vous pouvez utiliser une variable globale à la fonction récursive, l'incrémenter à l'entrée de la fonction et la décrémenter sur la sortie de la fonction. Cette variable indiquera le niveau actuel de la procédure récursive. Si nécessaire, vous pouvez conserver la valeur maximale de cette variable dans une deuxième variable.

Answer 2

Premièrement, s'il s'agit d'une question de devoirs, veuillez la marquer comme telle. Les images que vous liez impliquent que vous êtes dans CS 455, avec le professeur Wisman. :)

L'indice principal que je donnerai est ceci: La hauteur de l'arbre est évidemment déterminée par quand vous arrivez aux "feuilles". Les feuilles d'un arbre modélisant la relation de récurrence d'une fonction sont le cas de base. Ainsi, je regarderais pour voir comment N "rapidement" peut rétrécir au cas de base.

Answer 3

Si la récurrence est sous la forme de T (n) = aT (n/b) + f (n) alors la profondeur de l'arbre est la base logarithmique b de n. Par exemple, la récurrence de 2T (n/2) + n aurait l'arbre de profondeur lg (n) (base log 2 de n).