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

La hauteur de l'arbre de récursion dépend de l'algorithme récursif en question. Tous les algorithmes de division et de conquérir n'ont pas d'arbres de hauteur en uniforme, tout comme toutes les structures d'arbres n'ont pas de 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'arborescence au moment de l'exécution, vous pouvez utiliser une variable globale à la fonction récursive, l'incrémentation de l'entrée de la fonction et de la décrémentation. sur la sortie de la fonction. Cette variable indiquera le niveau actuel de la procédure récursive. Si nécessaire, vous pouvez maintenir la valeur maximale de cette variable dans une deuxième variable.

Premièrement, s'il s'agit d'une question de devoirs, veuillez la marquer comme tel. Les images que vous connaissez pour impliquer que vous êtes au CS 455, le professeur Wisman. :)

L'indice principal que je vais donner est ceci: la hauteur de l'arbre est évidemment déterminée par lorsque vous arrivez aux "feuilles". Les feuilles d'un arbre de modélisation de la relation récurrence d'une fonction sont le boîtier de base. Ainsi, je regarderais à voir comment "rapidement" N peut rétrécir à la base de base.

Si la récurrence est sous la forme de t (n) = à (n / b) + f (n), la profondeur de l'arborescence est la base de la base B de n.

Par exemple, la récurrence 2T (N / 2) + N aurait arboré de profondeur LG (N) (base de journal 2 de N).

La profondeur de tout arbre est le plus petit nombre d'arêtes du nœud au nœud racine de l'arbre. La profondeur du nœud racine est 0.

Considérez la récursion t (n) = à (n / b) il entraîne l'arborescence de récursions suivante

Il est clair que la profondeur de l'arborescence est $ \ log_b N $ La profondeur est identique à la hauteur d'un arbre.

Quoi, ce n'est pas clairement évident em> à vous? ;) C'est une excellente question si, sans autre raison que des personnes qui aiment agiter les mains. Il devient clairement clair avec la pratique, cependant.

Voici une explication basée sur un exemple de l'introduction aux algorithmes de Cormen, et al., Section 4.4. P>

considère t (n) = 3T (n / 4) + cn ^ 2 code>. La relation raconte la complexité temporelle d'un problème (par exemple un tableau) de taille n code>. Il est important de rappeler ce que n code> représente. Étant donné que la complexité t est définie en termes de t, c'est une relation de récurrence. P>

Si la hauteur n'est pas apparente, nous pouvons suivre les conseils de Polya et essayez d'utiliser le raisonnement direct, dessinez une image ou résoudre un problème connexe. Nous pouvons utiliser le raisonnement direct en branchant simplement l'expression droite pour T dans l'endroit où T apparaît, P>

                n/4^i = 1
         log_4(n/4^i) = log_4(1)
log_4(n) - log_4(4^i) = 0
             log_4(n) = log_4(4^i)
             log_4(n) = i