Дерево рекурсии, когда сумма уровня одинакова - PullRequest
Новая
       93

Дерево рекурсии, когда сумма уровня одинакова

0 голосов
/ 26 января 2019

Я пытался решить вопросы, используя метод дерева повторений, и обычно мы можем найти суммы уровней и получить GP, где мы можем применить бесконечную сумму GP и, следовательно, получить ее окончательное значение Big-O.

Что мы делаем для дел с одинаковой суммой уровня, например -

T (n) = 3T (n / 3) + cn

Ответ на следующий вопрос - Theta (nlogn)

1 Ответ

0 голосов
/ 26 января 2019

Во-первых, пусть T (1) = 1, n = 3 ^ k и c = 1: 

  T(n)   = 3T(n/3) + cn
= T(3^k) = 3T(3^(k-1)) + 3^k
         = 3(3T(3^(k-2)) + 3^(k-1)) + 3^k
         = 3^2T(3^(k-2)) + 3^k + 3^k
         = 3^2(3T(3^(k-3)) + 3^(k-2)) + 3^k + 3^k
         = 3^3T(3^(k-3)) + 3^k + 3^k + 3^k
         = ...
         = 3^kT(1) + k*3^k 
         = nT(1) + n*log3n
         = n + n*log3n

Можете ли вы доказать по индукции отсюда?

@ Edit

Рассмотрим следующее расширение дерева: 

                    n                     = n
    n/3            n/3            n/3     = n
n/9 n/9 n/9    n/9 n/9 n/9    n/9 n/9 n/9 = n
                   ...                    = n

Каждая строка суммирует до n.Если вы предполагаете, что n = 3 ^ k, дерево сбалансировано и имеет высоту k = log3n, следовательно, сложность равна Theta (n * log3n).

...