再帰ツリー方法

Question

を考えると、式：ツリーのT(n) = T(n/4) + T(n/2) + n^2

モデル：http://www.youtube.com/watch?v=whjt_N9uYFI

分：：38:53

質問：MITアルゴリズムクラスの講義から

   T(n)     -- Level 1 
      / \ 
     T(n/4)  T(n/2)   -- Level 2 
     / \  / \ 
T(n/16) *T(n/8) T(n/4) *T(n/8) -- Level 3 

方法、なぜ第3レベルがn/8になるのか？再帰ツリーを作成する明示的な式は何ですか？

これは途中で宿題の問題ではありません。

Answer 1

元ツリーはこれです：あなたが最初の分岐を展開すると

T(n) = n^2 -> T(n/4) 
        -> T(n/2) 

、あなたが置換n = n/4を作るので、あなたが得る：

第二分岐用

T(n/4) = (n/4)^2 -> T((n/4)/4) 
         -> T((n/4)/2) 

      = (n/4)^2 -> T(n/16) 
         -> T(n/8) 

と同様に、n = n/2

を

T(n/2) = (n/2)^2 -> T(n/8) 
         -> T(n/4) 

この拡張をに戻してくださいあなたは、これは宿題である場合、あなたはそのようにタグ付けする必要があり

T(n) = (n^2) -> (n/4)^2 -> T(n/16) 
            -> T(n/8) 
         -> (n/2)^2 -> T(n/8) 
            -> T(n/4)