Рекуррентное соотношение: решение большого O T (n-1)

Я решаю некоторые проблемы рекуррентного соотношения для Большого O, и до сих пор до этой точки только встретились с рекуррентными соотношениями, которые включили эту форму:

T(n) = a*T(n/b) + f(n)

Для вышеупомянутого для меня довольно легко найти Большую нотацию O. Но я был недавно брошен финт со следующим уравнением:

T(n) = T(n-1) + 2

Я не действительно уверен, как обойти решение этого для Большого O. Я на самом деле попытался включить уравнение как, что следует:

T(n) = T(n-1) + 2
T(n-1) = T(n-2)
T(n-2) = T(n-3)

Я не совсем уверен, корректно ли это, но я застреваю, и нуждаются в некоторой помощи.Спасибо!

6
задан Bill the Lizard 15 December 2012 в 16:22
поделиться

2 ответа

Предполагая, что T(1) = 0

T(n) = T(n-1) + 2
 = (T(n-2) + 2) + 2
 = T(n-2) + 4
 = (T(n-3) + 2) + 4
 = T(n-3) + 6
 = T(n-k) + 2k

Установите k в n-1, и вы получите

T(n) = 2n - 2

Следовательно, это O(n)

18
ответ дан 8 December 2019 в 12:18
поделиться

T(n) = 2*n = 2*(n-1)+2 = T(n-1)+2

Значит T(n) = 2*n, что подразумевает O(n)

0
ответ дан 8 December 2019 в 12:18
поделиться
Другие вопросы по тегам:

Похожие вопросы: