How to determine the height of a recursion tree fr

问题:

How does one go about determining the height of a recursion tree, built when dealing with recurrence run-times? How does it differ from determining the height of a regular tree?

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

edit: sorry, i meant to add how to get the height of the recursion tree from the recurrence relation.

回答1:

If recurrence is in the form of T(n) = aT(n/b) + f(n) then the depth of the tree is log base b of n.

For example, 2T(n/2) + n recurrence would have tree of depth lg(n) (log base 2 of n).

回答2:

Firstly, if this is a homework question, please mark it as such. The images you link to imply that you're in CS 455, with Professor Wisman. :)

The main hint I'll give is this: The height of the tree is obviously determined by when you get to the "leaves". The leaves of a tree modelling the recurrence relation of a function are the base case. Thus, I would look towards seeing how "quickly" N can shrink to the base case.

回答3:

The depth of any tree is the smallest number of edges from the node to the tree root node.The depth of root node is 0.

Consider the recursion T(n)=aT(n/b) It results in the following recursion tree

It is clear that depth of tree is $\log_b n$ Depth is same as height of a tree.

回答4:

The height of the recursion tree depends on the recursive algorithm in question. Not all divide and conquer algorithms have uniformed height trees, just as not all tree structures have uniform heights. If you cannot determine the maximum possible height of the algorithm, or if you need to calculate the actual height of the tree at run time, you can use a variable global to the recursive function, increment it upon the entry to the function, and decrement it upon the function exit. This variable will indicate the current level of the recursive procedure. If necessary, you can maintain the maximum value of this variable in a second variable.