在处理递归运行时时如何确定递归树的高度?它与确定普通树的高度有何不同?
替代文本 http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/ch4-9.gif
编辑:对不起,我的意思是添加如何从递归关系中获取递归树的高度。
在处理递归运行时时如何确定递归树的高度?它与确定普通树的高度有何不同?
替代文本 http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/ch4-9.gif
编辑:对不起,我的意思是添加如何从递归关系中获取递归树的高度。
如果递归的形式是 T(n) = aT(n/b) + f(n),那么树的深度是 n 的 log base b。
例如,2T(n/2) + n 递归将具有深度 lg(n) 的树(n 的以 2 为底的对数)。
首先,如果这是一个家庭作业问题,请标记它。您链接的图像暗示您与 Wisman 教授一起参加 CS 455。:)
我要给出的主要提示是:树的高度显然是由你到达“叶子”的时间决定的。模拟函数递归关系的树的叶子是基本情况。因此,我希望看到 N 如何“快速”缩小到基本情况。
任何一棵树的深度是从该节点到树根节点的最小边数。根节点的深度为0。
考虑递归 T(n)=aT(n/b) 它导致以下递归树
很明显,树的深度是 $\log_b n$ 深度与树的高度相同。
什么,对你来说不是很明显吗?;) 这是一个很好的问题,如果没有其他原因只是人们喜欢向它挥手。然而,它确实随着实践变得清晰。
这是基于 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
处于第i
th 级。在边界处,子问题大小为 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 “问题”一词可以有不同的用法。首先,它可能意味着“手头的任务”,例如找到递归树的高度。然而,由于树是通过递归产生的,问题以类似的形式(即子树)再次出现,因此“问题”意味着“正在操作的集合的大小”,例如数组中的元素数量。
递归树的高度取决于所讨论的递归算法。并非所有分治算法都有统一的高度树,就像并非所有的树结构都具有统一的高度一样。如果您无法确定算法的最大可能高度,或者如果您需要在运行时计算树的实际高度,您可以使用递归函数的全局变量,在进入函数时将其递增,然后递减它在函数退出时。此变量将指示递归过程的当前级别。如有必要,您可以在第二个变量中保持此变量的最大值。