Алгоритм вопроса

Question

Если f (x) = O (g (x)) как x -> бесконечность, то

A. g - верхняя граница f

B. f - верхняя граница г.

C. g - нижняя граница f.

D. f - нижняя граница g.

Может кто-нибудь сказать мне, когда они думают, что это так и почему?

Answer 1

Реальный ответ заключается в том, что ни один из них не является правильным.

Определение обозначения big-O таково:

|f(x)| <= k|g(x)|

для всех x > x0, для некоторых x0 и k.

В определенных случаях |k| может быть меньше или равно 1, и в этом случае было бы правильно сказать, что «| g | является верхнимоценка | f | ".Но в целом это не так.

Answer 2

Ответ

g - верхняя граница f

Когда x стремится к бесконечности, наихудший сценарий - O(g(x)).Это означает, что фактическое время выполнения может быть ниже, чем g(x), но никогда не хуже, чем g(x).

РЕДАКТИРОВАТЬ:

Как отметил Оли Чарльзуорт,верно с произвольной константой k <= 1 и не в целом.<a href="/5924250/algoritm-voprosa"> Пожалуйста, посмотрите на его ответ для общего случая.

Answer 3

Вопрос проверяет ваше понимание основ асимптотической алгебры, или big-oh обозначений.В

f(x) = O(g(x)) при приближении x к бесконечности

вопрос говорит о том, что при подаче функции f значение x, значение которого f вычисляет из x, затем в порядке того, что возвращено из другой функции, g(x).В качестве примера, предположим, что

f(x) = 2x
g(x) = x

, тогда значение g(x) возвращается при подаче x того же порядка, что и f(x) для x.В частности, две функции возвращают значение в порядке x;обе функции линейные .Неважно, является ли f(x) 2x или ½x;для любого постоянного фактора вообще f(x) вернет значение, которое имеет порядок x.Это потому, что нотация big-oh означает игнорирование постоянных факторов.Постоянные факторы не растут по мере роста x, поэтому мы предполагаем, что они не так важны, как x.

Мы ограничиваем g(x) определенным набором функций.g(x) может быть x, или ln(x), или log(x) и и т. Д. и и т. Д. .Это может выглядеть так, как если бы

f(x) = 2x
g(x) = x

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