Рубрики

ВОРОТА | GATE-CS-2001 | Вопрос 16

Пусть f (n) = n 2 Logn и g (n) = n (logn) 10 две положительные функции от n. Какое из следующих утверждений является правильным?
(A) f (n) = O (g (n)) и g (n)! = O (f (n))
(B) f (n)! = O (g (n)) и g (n) = O (f (n))
(C) f (n) = O (g (n)), но g (n) = O (f (n))
(D) f (n)! = O (g (n)), но g (n)! = O (f (n))

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

Любая постоянная мощность Logn асимптотически меньше n.

Доказательство:

Учитывая, что f (n) = n 2 Logn и g (n) = n (logn) 10
В таких вопросах мы предлагаем вам сначала отменить общий фактор в обеих функциях. После их удаления у нас остаются f (n) = n и g (n) = (logn) 9 . Удаление коэффициента nlogn из обеих функций.

Теперь n очень очень большое асимптотически по сравнению с любой постоянной интегральной степенью (logn), которую мы можем проверить, подставив очень большое значение, скажем, 2100.

f (2100) = 2 100 = 1030 и g (2100) = 100 9 = 1018.

Всегда не забывайте подставлять очень большие значения n, чтобы сравнить обе эти функции. В противном случае вы получите неправильные выводы, потому что если f (n) асимптотически больше, чем g (n), это означает, что после определенного значения n, f (n) всегда будет больше, чем g (n).

Это решение предоставлено Пранджул Ахаджа .
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2001 | Вопрос 16

0.00 (0%) 0 votes