Рубрики

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 49

Данная диаграмма показывает блок-схему для рекурсивной функции A (n). Предположим, что все операторы, кроме рекурсивных вызовов, имеют O (1) временную сложность. Если сложность по времени для этой функции в наихудшем случае равна O (n α ), то наименьшее возможное значение (с точностью до двух десятичных позиций) α составляет __________

(А) от 2,2 до 2,4
(В) от 3,2 до 3,4
(С) от 0 до 1,8
(D) 1

Ответ: (А)
Пояснение: временная сложность рекуррентного отношения — наихудшая временная сложность. Сначала мы должны узнать количество вызовов функций в худшем случае из блок-схемы.
Наихудший случай будет, когда все условия (алмазные ящики) повернуты к невозвратным путям, укорененным с самым длинным корнем. На самом длинном пути у нас есть 5 вызовов функций.

Таким образом, отношение повторения будет —
A (n) = 5A (n / 2) + O (1) (O (1), поскольку остальные операторы имеют сложность O (1).)
Решение этого рекуррентного отношения с помощью основной теоремы —
a = 5, b = 2, f (n) = O (1), n log b a = n log 2 5 (основная теорема случая 1)
A (n) = n log b a
значение log 2 5 равно 2.3219, поэтому наилучшим вариантом является вариант a

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

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 49

0.00 (0%) 0 votes