Рубрики

ВОРОТА | GATE CS Mock 2018 | Набор 2 | Вопрос 56

Время выполнения алгоритма сортировки слиянием в худшем случае описывается следующим рекуррентным соотношением:

                 ⌈ 1               , if n = 1
       T(n)  =   | 2T(n/2)+ n      , otherwise
                 ⌊

Данное рекуррентное уравнение оценивается как —
(A) 2 k T (n / 2 k ) + kn
(B) 2 k T (n k / 2) + kn
(С) nk T (n / 2 k )
(D) T (n / 2 k ) + kn

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

T(n) = 2T (n/2) + n
     = 21 T(n/21) + 1.n            [ k = 1]
     = 2k-1 T(n/2k-1) + (k-1)n
     = 2k-1 (2T(n/2k + n/2k-1) + (k-1)n
     = 2k  T(n/2k) + kn

Вариант (А) является правильным.
Тест на этот вопрос

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

ВОРОТА | GATE CS Mock 2018 | Набор 2 | Вопрос 56

0.00 (0%) 0 votes