Рубрики

ВОРОТА | GATE-CS-2004 | Вопрос 90

Рекуррентное уравнение

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

оценивает
(A) 2 n + 1 — n — 2
(B) 2 n — n
(С) 2 n + 1 — 2n — 2
(D) 2 n + n

Ответ: (А)
Объяснение: Если нарисовать рекурсивное дерево, мы можем заметить, что всего выполнено:
T (n) = n + 2 (n-1) + 4 (n-2) + 8 (n-3) + 2 n-1 * (n-n + 1)
T (n) = n + 2 (n-1) + 4 (n-2) + 8 (n-3) + 2 n-1 * 1

Чтобы решить эту серию, воспользуемся нашей школьной уловкой, умножим T (n) на 2 и вычтем после смещения членов.

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

Мы получаем

2T(n) - T(n) =  -n + 2 + 4 + 8 + ..... 2n
T(n) = -n + 2n+1 - 2 [Applying GP sum formula for 2, 4, ...]
     = 2n+1 - 2 - n
Alternate Way to solve is to use hit and try method.
Given T(n) = 2T(n-1) + n and T(1) = 1

For n = 2, T(2) = 2T(2-1) + 2 
                = 2T(1) + 2 
                = 2.1 + 2 = 4

Now when you will put n = 2 in all options, 
only 1st option 2^(n+1) - n - 2 satisfies it. 

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2004 | Вопрос 90

0.00 (0%) 0 votes