Основная теорема и метод замены на (n-1)

Какой метод следует использовать для решения этого повторения?

 T(n)= {  Θ(1)             if n = 1
       {  T(n-1) + Θ(n)    if n > 1

recurrence substitution math master-theorem
person rismo    schedule 06.02.2014    source источник
comment
Возможный дубликат Как решить: T (n) = T (n - 1) + н   -  person Salvador Dali    schedule 16.12.2015

Ответы (2)


arrow_upward
1
arrow_downward

Вы можете решить это, используя метод итерации. Как подсказка, это решает (n2).

Надеюсь это поможет!

person templatetypedef    schedule 22.05.2014

arrow_upward
0
arrow_downward

Используя мастер-матод, мы можем найти, что:

a = 1, b = 1 и d = 1, тогда a = b^d.

Итак, T(n) = (количество уровней) * (работа на уровне) = n * n.

person Lerner Zhang    schedule 11.04.2019