递归树解决复发的方法

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)

我建议从算法简介 - CLRS中读取递归的主方法.