13

在处理递归运行时时如何确定递归树的高度？它与确定普通树的高度有何不同？

替代文本 http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/ch4-9.gif

编辑：对不起，我的意思是添加如何从递归关系中获取递归树的高度。

4

5 回答 5

8

如果递归的形式是 T(n) = aT(n/b) + f(n)，那么树的深度是 n 的 log base b。

例如，2T(n/2) + n 递归将具有深度 lg(n) 的树（n 的以 2 为底的对数）。

于 2009-09-25T01:29:18.047 回答
2

首先，如果这是一个家庭作业问题，请标记它。您链接的图像暗示您与 Wisman 教授一起参加 CS 455。:)

我要给出的主要提示是：树的高度显然是由你到达“叶子”的时间决定的。模拟函数递归关系的树的叶子是基本情况。因此，我希望看到 N 如何“快速”缩小到基本情况。

于 2009-08-29T05:24:04.640 回答
2

任何一棵树的深度是从该节点到树根节点的最小边数。根节点的深度为0。

考虑递归 T(n)=aT(n/b) 它导致以下递归树

在此处输入图像描述

很明显，树的深度是 $\log_b n$ 深度与树的高度相同。

于 2018-06-04T15:33:10.193 回答
2

什么，对你来说不是很明显吗？;) 这是一个很好的问题，如果没有其他原因只是人们喜欢向它挥手。然而，它确实随着实践变得清晰。

这是基于 Cormen 等人的算法简介第 4.4 节中的示例的解释。

考虑T(n) = 3T(n/4) + cn^2。该关系告诉大小为 的问题（例如数组）的时间复杂度n。重要的是要记住n代表什么。由于复杂度 T 是根据 T 定义的，因此它是递归关系。

如果高度不明显，我们可以按照Polya的建议，尝试使用直接推理，画图，或解决一些相关问题。我们可以通过简单地将 T 的右手表达式插入 T 出现的任何地方来使用直接推理，

T(n) = 3T(n/4) + cn^2
     = 3[3T( (n/4)/4 ) + c(n/4)^2] + cn^2
     = 9T(n/16) + c(n/4)^2 + cn^2
     = 9[3T( (n/16)/4 ) + c(n/16)^2] + c(n/4)^2 + cn^2
     = 27T(n/64) + c(n/16)^2 + c(n/4)^2 + cn^2
     ...

画一幅画会产生一棵树。每次递归为每个孩子产生三个分支：

Initial pass
                   ____cn^2____
                  /      |     \
                 /       |      \
            T(n/4)    T(n/4)    T(n/4)


First recursion                 
                   ____cn^2____
                  /      |     \
                 /       |      \
          cn(n/4)^2  cn(n/4)^2  cn(n/4)^2
          /   |   \  /   |   \  /   |   \
       T(n/16)          ...            T(n/16)
                         .
...on down             
                   ____cn^2____
                  /      |     \
                 /       |      \
          cn(n/4)^2  cn(n/4)^2  cn(n/4)^2
          /   |   \  /   |   \  /   |   \
       T(n/16)          ...            T(n/16)
                         .
                         .
                         .
    T(1) ...                            ...  T(1)

到什么程度？

请记住，这n是原始问题的大小（例如数组中的元素数）1。这限制了可能发生的递归次数。边界条件将取决于递归发生的情况。对于一个数组，你可以想象递归一直持续到只剩下一个元素。这将发生在 T(1)。

边界与高度有何关系？

对我来说，最大的启示是意识到树的高度与边界的高度相同。这就是波利亚所说的“相关问题”。我们可以将问题重新表述为，

树在什么级别达到边界条件？

查看关系或树，注意如何n/4重复插入连续递归。这意味着子问题大小（n原始问题大小在哪里）n/4^i处于第ith 级。在边界处，子问题大小为 1：

                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

最后一个等式告诉我们，当 时，树达到边界条件i = log_4(n)。由于树的高度是满足边界条件的级别，因此树的高度为log_4(n)。

从这里开始，只需泛化即可得出@ejel 给出的结论

如果 T(n) = aT(n/b) + f(n) 则树的深度是 n 的对数基 b。

正如@xpda 指出的那样，递归树的高度将取决于算法。可能概括的一个要点是考虑算法在其边界处的行为方式。

1 “问题”一词可以有不同的用法。首先，它可能意味着“手头的任务”，例如找到递归树的高度。然而，由于树是通过递归产生的，问题以类似的形式（即子树）再次出现，因此“问题”意味着“正在操作的集合的大小”，例如数组中的元素数量。

于 2020-09-27T16:03:06.273 回答
1

递归树的高度取决于所讨论的递归算法。并非所有分治算法都有统一的高度树，就像并非所有的树结构都具有统一的高度一样。如果您无法确定算法的最大可能高度，或者如果您需要在运行时计算树的实际高度，您可以使用递归函数的全局变量，在进入函数时将其递增，然后递减它在函数退出时。此变量将指示递归过程的当前级别。如有必要，您可以在第二个变量中保持此变量的最大值。

于 2009-08-28T16:05:10.157 回答