解決遞歸的遞歸樹方法

Question

我正在練習使用此鏈接的遞歸樹方法：http://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html ..第一個例子是好的，但在第二個例子中，他計算樹的高度爲log（base 3/2）n ..誰能告訴我他是如何計算身高的？可能是一個愚蠢的問題，但我不明白！ ：|

Answer 1

讓我試試解釋一下。你有的遞歸公式是。它說，你正在製作一個遞歸樹，該樹被分成兩個大小爲n/3，​​的子樹，並且在該級別上的成本爲n。

如果您看到高度由最大子樹（+1）的高度確定。這裏右子樹，與​​元素的一個將驅動高度。好？

如果上面的句子對你很清楚，讓我們來計算身高。在身高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。