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

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)