Решение рекуррентного соотношения методом итерации

как решить T(n) = T(n-1) + n с помощью итеративного метода, и ответ theta(n^2)


recurrence algorithm
person Santhosh    schedule 20.03.2011    source источник

Ответы (2)


arrow_upward
7
arrow_downward 

T(n) = T(n-1) + n = T(n-2) + n-1 + n = ... = 1+ 2 + ... + n = (n+1)n/2 = theta(n^2)


обратите внимание на предположение, что T(0) = 0 (у вас должна быть база для рекурсии)
надеюсь, что то, что вы имели в виду

person amit    schedule 20.03.2011

arrow_upward
1
arrow_downward

Иногда вы также можете использовать метод уравнений характеристик для решения рекуррентных соотношений. Это предполагает определение частного интеграла и полного решения.

Подробнее здесь: решение рекуррентных отношений

person Community    schedule 20.03.2011