algorithm - 再帰を解決する再帰ツリー法

Question

私はこのリンクを使用して再帰ツリーメソッドを練習していました：http ：//www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html ..最初の例は大丈夫でしたが、2番目の例では彼は木の高さをlog（base 3/2）nとして計算します。..高さの計算方法を教えてもらえますか？ばかげた質問かもしれませんが、私には理解できません！：|

Answer 1

説明してみましょう。あなたが持っている再帰式はですT(n) = T(n/3) + T(2n/3) + n。それは、あなたがそのレベルでサイズn/3、、2n/3およびコストの2つのサブツリーに分割する再帰ツリーを作成していることを示しています。n

表示されている場合、高さは最大のサブツリーの高さ（+1）によって決定されます。ここで、右側のサブツリー、2n/3要素を持つサブツリーが高さを駆動します。わかった？

上記の文章がはっきりしている場合は、身長を計算してみましょう。高さ1にn*(2/3)要素があり、高さ2にn*(2/3)^2要素があります...要素が1つ残るまで分割を続けます。つまり、高さで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を読むことをお勧めします。