如何根据递归关系确定递归树的高度？
如何确定在处理递归运行时时构建的递归树的高度？它与确定普通树的高度有何不同？
替代文本 http://homepages.ius.edu/rwisman /C455/html/notes/Chapter4/ch4-9.gif
编辑：抱歉，我的意思是添加如何从递归关系中获取递归树的高度。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
如果递归的形式为 T(n) = aT(n/b) + f(n)，则树的深度是 n 的对数底 b。
例如，2T(n/2) + n 递归将具有深度 lg(n) 的树（n 的以 2 为底的对数）。
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).
什么，这对你来说不是明显？ ;) 这是一个很好的问题，如果没有其他原因，只是人们喜欢对此挥手。然而，随着实践，它确实变得清晰起来。
以下是基于 Cormen 等人的《算法简介》第 4.4 节中的示例进行的解释。
考虑
T(n) = 3T(n/4) + cn^2。该关系表明大小为 n 的问题（例如数组）的时间复杂度。记住n代表什么很重要。由于复杂度 T 是根据 T 定义的，因此它是一个递推关系。如果高度不明显，我们可以遵循 Polya 的建议并尝试使用直接推理，画一幅画，或者解决一些相关的问题。我们可以通过简单地将 T 的右侧表达式插入到 T 出现的地方来使用直接推理，
绘制图片会生成一棵树。每次递归都会为每个子级生成三个分支：
向下到什么？
请记住，
n是原始问题的大小（例如数组中的元素数量）1。这限制了可能发生的递归次数。 边界条件将取决于递归发生的情况。对于数组，您可以想象递归一直持续到只剩下一个元素为止。这将在 T(1) 发生。边界与高度有何关系？
对我来说，最大的启示是认识到树的高度与边界所在的高度相同。这就是波利亚所说的“相关问题”。我们可以将问题重新表述为：
树在什么级别达到边界条件？
查看关系或树，注意
n/4如何重复插入连续的递归中。这意味着第 i 层的子问题大小（其中n是原始问题大小）为n/4^i。在边界处，子问题大小为 1：最后一个方程告诉我们，当 i = log_4(n) 时，树达到边界条件。由于树的高度是满足边界条件的级别，因此树的高度为
log_4(n)。从这里开始，只需概括即可得出 @ejel 给出的结论
正如@xpda 指出的，递归树的高度将取决于算法。一个可能概括的要点是考虑算法在其边界处的行为方式。
1“问题”一词可以有不同的使用方式。首先，它可能意味着“手头的任务”，例如找到递归树的高度。然而，由于树是通过递归产生的，因此问题会以类似的形式（即子树）重新出现，因此“问题”意味着“正在操作的集合的大小”，例如数组中元素的数量。
What, it's not clearly obvious to you? ;) This is a great question if for no other reason than people like to wave their hands at it. It does become clear with practice, however.
Here's an explanation based on an example from the Introduction to Algorithms by Cormen, et al., Section 4.4.
Consider
T(n) = 3T(n/4) + cn^2. The relation tells the time complexity of a problem (e.g. an array) of sizen. It's important to remember whatnrepresents. Since the complexity T is defined in terms of T, it's a recurrence relation.If the height isn't apparent, we can follow the advice of Polya and try to use direct reasoning, draw a picture, or solve some related problem. We can use direct reasoning by simply plugging the right-hand expression for T in wherever T appears,
Drawing a picture produces a tree. Each recursion produces three branches for each child:
On down to what?
Remember that
nis the size of the original problem (e.g. the number of elements in an array)1. This bounds the number of recursions that can happen. The boundary conditions will depend on the situation in which the recursion came about. For an array, you can imagine the recursion continuing until only a single element remains. This would happen at T(1).How might the boundary be related to the height?
To me, the grand revelation is realizing that the height of the tree is the same as the level at which the boundary is met. This is that "related problem" Polya talks about. We can reformulate the question to be,
At what level does the tree reach the boundary condition?
Looking at the relation or the tree, notice how
n/4is repeatedly plugged into successive recursions. This means the subproblem size (wherenis the original problem size) isn/4^iat theith level. At the boundary, the subproblem size is 1:The last equation tells us that the tree reaches the boundary condition when
i = log_4(n). Since the height of the tree is the level where the boundary condition is met, the tree has heightlog_4(n).From here, it's only a matter of generalizing to reach the conclusion @ejel gives that
As @xpda points out, the height of recursion tree will depend on the algorithm. One take-away which likely generalizes is to consider how the algorithm behaves at its boundaries.
1 The word "problem" may be used in different ways. Foremost, it may mean "the task at hand", such as finding the height of the recursion tree. However, since the tree arises through recursion, the problem reappears in similar form (i.e. subtrees) so that "problem" comes to mean "the size of the set being operated on", such as the number of elements in an array.
首先，如果这是一个家庭作业问题，请标记为家庭作业问题。您链接到的图像暗示您与 Wisman 教授一起在 CS 455 中。 :)
我要给出的主要提示是：树的高度显然是由到达“叶子”的时间决定的。对函数的递归关系进行建模的树的叶子是基本情况。因此，我希望看到 N 能够如何“快速”收缩到基本情况。
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.
任何树的深度都是从该节点到树根节点的最小边数。根节点的深度为 0。
考虑递归 T(n)=aT(n/b) 得到以下递归树
< img src="https://i.sstatic.net/b9msu.jpg" alt="在此处输入图像描述">
很明显，树的深度为 $\log_b n$ 深度与树的高度相同。
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.
递归树的高度取决于所讨论的递归算法。并非所有分治算法都具有统一高度的树，就像并非所有树结构都具有统一高度一样。如果无法确定算法的最大可能高度，或者需要在运行时计算树的实际高度，则可以使用递归函数的全局变量，在进入函数时递增它，并递减它在函数退出时。该变量将指示递归过程的当前级别。如有必要，您可以在第二个变量中维护该变量的最大值。
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.