Рубрики

ВОРОТА | GATE-CS-2015 (Mock Test) | Вопрос 10

Выберите правильную асимптотическую сложность алгоритма со временем выполнения T (n, n), где

T(x, c) = Θ(x) for c <= 2,
T(c, y) = Θ(y) for c <= 2, and
T(x, y) = Θ(x+y) + T(x/2, y/2) 

(A) Θ (nLogn)
(B) Θ (n 2 )
(С) Θ (н)
(D) Θ (n 2 Logn)

Ответ: (с)
Пояснение: повторение

T(x, y) = Θ(x+y) + T(x/2, y/2) 

Это может быть написано как ниже.

T(x, y) = Θ(x+y) + Θ((x+y)/2) + Θ((x+y)/4) +  Θ((x+y)/8)  .....
T(x, y) = Θ((x+y) + (x+y)/2 + (x+y)/4 + (x+y)/8  ..... )

Вышеприведенное выражение образует геометрический ряд с соотношением 2 и начальным элементом (x + y) / 2.

T (x, y) ограничена сверху Θ (x + y), так как сумма бесконечных рядов равна 2 (x + y). Он ограничен снизу (x + y)

Источник: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/assignments/MIT6_006F11_ps1.pdf

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

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

ВОРОТА | GATE-CS-2015 (Mock Test) | Вопрос 10

0.00 (0%) 0 votes