рекуррентное соотношение: итерации решения

Question

Существует рекуррентное соотношение следующим образом:

T(n) = 2 T(n-1) + O(1) for n > 1 
otherwise, its T(n) = O(1) 

По итерации, до сих пор я, как,

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

Я не уверен, что делать дальше, чтобы найти сложность времени сверху. Может ли кто-нибудь помочь мне в этом.

Answer 1

Посмотрите на шаге 4

T(n) = 2(2(2(2(2T(n-5) + 1) + 1) + 1) + 1) +1 ----- 4 
T(n) = 2(2(2(2(2T(n-5))))) + 16 + 8 + 4 + 2 +1 = 
T(n) = 2^4* 2T(n-5) + 2^4 + 2^3 + 2^2 + 2^1 + 2^0 = 
T(n) = 2^4* 2T(n-5) + 2^5 -1 = 

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

T(n) = 2^5 *2T(n-6) + 2^5 + 2^5-1 
T(n) = 2^5 * 2T(n-6) + 2^6-1 

В настоящее время мы можем понять, что если мы не будем развивать его до основания T (1), получаем:

T(n) = .... = 2^(n) -1 

Обратите внимание, что этот метод дает интуицию только для решения проблемы и ИТ НЕ ДОКАЗАТЕЛЬСТВО.

---

Чтобы формально доказать утверждение, вы можете использовать индукцию, и утверждают гипотезу T(n) = 2^n -1:

Основание: T(1) = 1 = 2^1 -1

Индукционная гипотеза: Для всех k<n, T(k) = 2^k-1

Доказательство:

T(n) = 2T(n-1) +1 =(i.h.) 2* (2^(n-1) -1) + 1 = 2^n -2 + 1 = 2^n - 1 

Примечание: Основное предложение T (1) на самом деле C, и аналогично T(n) = 2T(n-1)+C для некоторой константы, а не 1, но я использую 1 для простоты. Логика вообще не изменяет при изменении ее на C.

Answer 2

По определению O(1), мы знаем, что для некоторых постоянных N и c, для всех n >= N

T(n+1) <= 2 T(n) + c 

Итак, признающего образец геометрической прогрессии,

T(N+1) <= 2 T(N) + c 
T(N+2) <= 2 T(N+1) + c <= 4 T(N) + 2 c + c 
T(N+3) <= 2 T(N+2) + c <= 8 T(N) + 4 c + 2 c + c 
... 
T(N+k) <= 2^k T(N) + (2^k-1) c 

Тогда замена N + k по n,

T(n) <= 2^(n-N) T(N) + (2^(n-N)-1) c <= 2^n (2^(-N) (T(N) + c)) 

, что подтверждает, что T(n) является O(2^n).