Рекуррентное соотношение T (n) = 3T (n-1) + n - PullRequest
Новая
       66

Рекуррентное соотношение T (n) = 3T (n-1) + n

0 голосов
/ 29 апреля 2018

Я пытаюсь решить рекуррентное отношение T (n) = 3T (n-1) + n, и я думаю, что ответ O (n ^ 3), потому что каждый новый узел порождает три дочерних узла в дереве рекуррентности. Это правильно? И, с точки зрения дерева повторений, есть ли более математический способ приблизиться к нему?

1 Ответ

0 голосов
/ 16 июня 2018

Уравнения повторения - просто математика: разверните, суммируйте и упростите. 

T(n) = 3T(n-1) + n = 3 (3 T(n - 2) + (n-1)) + n 
     = 3^2 T(n - 3) + 3^2(n-2) + 3(n-1) + n) 
     = ...
     = 3^i T(n - i) + Σ_(j=0..i-1) 3^j * (n-j)
     = Σ_(j=0..n-1) 3^j * (n-j)          // assuming T(0) = 0

Теперь мы можем найти различные верхние границы в зависимости от того, насколько мы хотим думать об этом: 

T(n) = Σ_(j=0..n-1) 3^j * (n-j)
     < n * Σ_(j=0..n-1) 3^j
     = n * (3^n - 1)

Итак T(n) = O(n*3^n).

Вы также можете получить более жесткий предел, разделив сумму на две части: 

T(n) = Σ_(j=0..n-1) 3^j * (n-j)
     < n * Σ_(j=0..n-x) 3^j * (n-j)     +   x * Σ_(j=n-x..n-1) 3^j
     = n (3^(n-x+1) - 1)  + x * (3^n - 3^(n-x+1))

используя x = log_3(n) вы получите T(n) = O(3^n * log(n)).

Вы также можете приблизить сумму Σ(n-i)3^i с помощью интеграла и получить точную сложность Θ(3^n).

...