algorithm - 递归树法

Question

给定方程:T(n) = T(n/4) + T(n/2) + n^2

树模型:

              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

来自麻省理工学院算法课讲座:http://www.youtube.com/watch?v=whjt_N9uYFI

分钟:38:53

问题:如何、什么以及为什么第 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) 你得到

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