Рубрики

ВОРОТА | Gate IT 2008 | Вопрос 42

Когда n = 2 2k для некоторого k ≥ 0, рекуррентное соотношение

T (n) = √ (2) T (n / 2) + √n, T (1) = 1

оценивает:
(A) √ (n) (log n + 1)
(B) √ (n) (log n)
(C) √ (n) log √ (n)
(D) n log √ (n)

Ответ: (А)
Пояснение: Обратите внимание, что вопрос касается точного решения. Основная теорема дает результаты в виде асимптотических обозначений . Поэтому мы не можем применить теорему Мастера здесь Мы можем решить это повторение, используя простое расширение или метод дерева повторений.

T(n) = √(2) T(n/2) + √n
     = √(2) [√(2) T(n/4) + √(n/2) ] + √n
     = 2 T(n/4) + √2 √(n/2) +√n
     = 2[ √2 T(n/8) + √(n/4) ]+√2 √(n/2)+√n
     = √(2^3) T(n/8)+ 2 √(n/4) + √2 √(n/2) +√n
     = √(2^3) T(n/8)+√n +√n +√n
     = √(2^3) T(n/(2^3))+3√n
     .............................................
     = √(2^k) T(n/(2^k))+k√n
     = √(2^logn) + logn √n
     = √n + logn √n
     = √n(logn +1)

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

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

ВОРОТА | Gate IT 2008 | Вопрос 42

0.00 (0%) 0 votes