Рубрики

ВОРОТА | GATE-CS-2000 | Вопрос 40

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

Какие из следующих утверждений верно?
(A) h (n) является O (f (n))

(B) h (n) является O (g (n))
(С) g (n) не является O (f (n))
(D) f (n) является O (g (n))

Ответ: (D)
Пояснение: Биг-о-н нотация:

Пусть f и g две функции, определенные на вещественном числе. Каждый пишет f (n) = O (g (n)), если существует положительная постоянная M, такая, что для всех достаточно больших значений n абсолютное значение f (n) не больше, чем M, умноженное на абсолютное значение g (п). То есть f (n) = O (g (n)) тогда и только тогда, когда существует положительное действительное число M и действительное число n0, такое что f (n) ≤M (g (n)), для всех n≥ n0.

В обозначениях Big-oh мы проводим сравнение только между двумя функциями, рассматривая большие значения n. Чтобы решить такой вопрос, мы можем взять большее значение n, а затем сравнить значения различных функций.

f (n) = 3 (n ^ 32) = 3 * (2 ^ 10) ^ 32 = 3 * 2 ^ 320

г (п) = 2 ^ 320

ч (п) = 1024!

Таким образом, связь между функциями может быть:

1.f (n) и g (n) имеют одинаковый порядок, поэтому f (n) равно O (g (n)), а g (n) = O (f (n)). Следовательно, вариант C неверен.
2.h (n) — это n! Который имеет более высокий порядок, чем f (n) и g (n). Так что варианты А и Б неправильны.

Смотрите http://geeksquiz.com/algorithms-analysis-of-algorithms-question-22/

Это решение предоставлено Nirmal Bharadwaj
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2000 | Вопрос 40

0.00 (0%) 0 votes