рекурсии дерева Метод

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 

С Лекция MIT Алгоритм Класс: 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)