Рубрики

ВОРОТА | GATE-CS-2014- (Set-2) | Вопрос 65

Что из следующего правильно определяет решение рекуррентного соотношения с T (1) = 1?

T(n) = 2T(n/2) + Logn 

(A) Θ (n)
(B) Θ (nLogn)
(C) Θ (n * n)
(D) Θ (log n)

Ответ: (А)
Объяснение:

 T(n) = 2T(n/2) + log n
 T(1) = 1
Substitute n = 2^k

T(2^k)  = k + 2T(2^(k-1))
T(2^k)  = k + 2(k-1) + 4T(2^(k-2))
        = k + 2(k-1) + 4(K-2) + 8T(2^(k-3))
        = k + 2(k-1) + 4(K-2) + 8(k-3) + 16T(2^(k-4))
        = k + 2(k-1) + 4(K-2) + 8(k-3) + ...... + 2^kT(2^(k-k))
        = k + 2(k-1) + 4(K-2) + 8(k-3) + .......+ 2^kT(1)
        = k + 2(k-1) + 4(K-2) + 8(k-3) + .......+ 2^k  --------(1)

2T(2^k) =     2k     + 4(k-1) + 8(K-2) + ...... + 2*2^k + 2^(k+1) --------(2)

Subtracting 1 from 2, we get below
T(2^k) = - k + 2 + 4 ......    2^(k-2) + 2^(k-1) + 2^k + 2^(k+1)
           = - k + 2 * (1 + 2 + 4 + ..... 2^k)
           = -k + [2*(2^k - 1)] / [2-1]
           = -k + [2*(2^k - 1)]

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

T(n)  = Θ(n) 

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

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

ВОРОТА | GATE-CS-2014- (Set-2) | Вопрос 65

0.00 (0%) 0 votes