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)

我建议阅读 Introduction to Algorithms - CLRS 中的 Master Method for Recursion| .