algorithm - 求解递归的递归树法

Question

我正在使用此链接练习递归树方法：http ://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html .. 第一个示例还可以，但在第二个示例中，他将树的高度计算为 log(base 3/2) n .. 谁能告诉我他是如何计算高度的？可能是一个愚蠢的问题，但我无法理解！:|

Answer 1

让我试着解释一下。您拥有的递归公式是T(n) = T(n/3) + T(2n/3) + n. 它说，您正在创建一个递归树，该树在该级别分为大小为 、 和成本的两个子n/3树2n/3。n

如果您看到高度是由最大子树的高度（+1）决定的。这里是右子树，带有2n/3元素的那个将驱动高度。好的？

如果上面这句话对你来说很清楚，让我们计算高度。在高度 1 处，我们将有n*(2/3)元素，在高度 2 处，我们有n*(2/3)^2元素，......我们将继续分裂直到剩下一个元素，因此在高度h

 n*(2/3)^h <= 1
 (take log both side)
 log(n) + h*log(2/3) <= 0
 (log is an increasing function)
 h*log(3/2) >= log(n)
 h >= log(n)/log(3/2)
 h >= log3/2 (n)

我建议阅读 Master Method for Recursion from Introduction to Algorithms - CLRS。