Рубрики

ВОРОТА | GATE CS 2008 | Вопрос 39

Рассмотрим следующие функции:

f(n) = 2n
g(n) = n!
h(n) = nlogn

Какое из следующих утверждений об асимптотическом поведении f (n), g (n) и h (n) верно?

(A) f(n) = O(g(n)); g(n) = O(h(n))
(B) f(n) = (g(n)); g(n) = O(h(n))
(C) g(n) = O(f(n)); h(n) = O(f(n))
(D) h(n) = O(f(n)); g(n) = (f(n)) 

(А) А
(Б) Б
(С) С
(D) D

Ответ: (D)
Пояснение: В соответствии с порядком роста: h (n) <f (n) <g (n) (g (n) асимптотически больше, чем f (n), а f (n) асимптотически больше, чем h (n))
Мы можем легко увидеть вышеупомянутый порядок, беря журналы данных 3 функций

   lognlogn < n < log(n!)  (logs of the given f(n), g(n) and h(n)).

Обратите внимание, что log (n!) = (NlogN)
Тест на этот вопрос

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

ВОРОТА | GATE CS 2008 | Вопрос 39

0.00 (0%) 0 votes