Если мы имеем f = 2x ^ 2 + log (x), если большое O (f) = x ^ 2, то что означает Omega (f) =?

Question

это лог (х), так как Омега - лучший возможный случай? тогда если f = x + 1, есть ли Omega (f) = 1, тогда?

Answer 1

Нет, Omega для асимптотических нижних оценок во многом так же, как O для асимптотических верхних оценок. Итак, f = Omega(g), если для некоторой константы C в конечном итоге верно, что f >= C * g. То есть существует константа C и константа N, такая, что n >= N подразумевает f(n) >= C * g(n). Это то же самое, что и O, только с измененным направлением неравенства.

Answer 2

Ни О, ни Омега так не работают. Вы также не можете сказать O (f) = x ^ 2

Вместо этого один говорит: f = O (g), что означает, что существуют константы k и C, такие что: f

Поэтому следующие утверждения верны для вашего f:

• f = O (x ^ 2)
• f = O (x ^ 2 + log (x))
• f = O (x ^ 3)
• f = O (x ^ 145321)

Омега работает так же, но с обратным неравенством: f = Omega (g), что означает, что существуют константы k и C, такие что: f> k * g + C

Поэтому следующие утверждения верны для вашего f:

• f = Омега (бревно (х))
• f = Омега (x ^ 2 + log (x))
• f = Омега (1)
• f = Омега (х)

Надеюсь, это поможет. Для получения дополнительной информации см. Википедия

Answer 3

Многие люди думают, что O означает «худший случай», а Omega означает «лучший случай», но это не правильно. Утверждение f (x) = O (g (x)) означает, что " f (x) не растет быстрее, чем cg (x) (для некоторая константа c ), в то время как f (x) = Omega (g (x)) означает, что " f (x) не растет медленнее, чем cg (x)". Обратите внимание, что в обоих этих утверждений это самый" большой "термин (в данном случае 2x ^ 2 ), который вам следует посмотрите, так что f (x) равно O (x ^ 2) и Omega (x ^ 2) (и это также O (x ^ 3) , O (2 ^ x) , Омега (x) , Омега (1) и т. д.) Наиболее Однако важно отметить, что и O, и Omega являются утверждениями о функции f (x) . Они не заботятся о том, что описывает функция, и не имеют представления о лучшие или худшие случаи. Скорее, это обычное использование O для описания функции, когда функция представляет наихудший случай, и использование Омега , когда функция представляет лучший случай. Причина этого заключается в том, что если у нас есть O , ограниченная для функции, которая представляет наихудший случай для алгоритма, то та же самая граница O применяется ко времени выполнения алгоритма в все случаев (так как он никогда не может использовать больше времени, чем в худшем случае), и аналогично, Омега , ограниченный для лучшего случая, применяется ко времени выполнения алгоритма во всех случаях.

Answer 4

Есть еще одно очень важное обозначение с практической точки зрения. Большая тэта нотация. Идея такая же, как с большим O и большим Omega, но функция ограничена как сверху, так и снизу.