Может ли f (n) принадлежать как o (g (n)), так и большому омегу (g (n))?

Question

У меня есть небольшой запрос.
Can f(n) принадлежат к o(g(n))иbig omega(g(n))?
Я не могу понять это. Может кто-нибудь объяснить мне, пожалуйста?

Answer 1

Нет, это невозможно. С o(g(n)) означает сложность времени строго менее g(n) и ω(g(n))строго больше.

Answer 2

Новый ответ (для Editted вопроса):

Нет, она не может. Формальное доказательство, основанный на set theory и тот факт, что o(g(n)) и Ω(g(n)) наборы функций:

o(g(n)) = O(g(n)) \ Θ(g(n)) 
Θ(g(n)) = Ω(g(n)) ∩ O(g(n)) 

o(g(n)) ∩ Ω(g(n)) = { O(g(n)) \ Θ(g(n)) } ∩ Ω(g(n)) 
        = { O(g(n)) ∩ Ω(g(n)) } \ Θ(g(n)) [see appendix 1] 
        = Θ(g(n)) \ Θ(g(n)) = {} 

Поскольку o(g(n)) ∩ Ω(g(n)) является пустое множество, не существует функция f(n), которая принадлежит к пересечению, таким образом, ни одна функция не принадлежит для обоих наборов.

QED

Приложение 1:
Давайте удостоверимся, мы понимаем это равенство:

(1) = {O (г (п)) \ Θ (г (п)) } ∩ Ом (г (п)) = {О (г (п)) ∩ Ω (г (п))} \ Q (г (п)) = (2)

• Если х не находится в O (g (n)) - это не в (1), а также не в (2), независимо от того, что они появляются в других наборах.
• , если x находится в O (g (n)) и в Θ (g (n)), оно не находится в (1), а также не в (2), независимо от того, что оно появляется в Ω (g (n))
• , если x находится в O (g (n)), а не в Θ (g (n)) и да в Ω (g (n)), он как в (1), так и в (2)
• , если x находится в O (g (n)), а не в Θ (g (n)), а не в Ω (g (n)), он не находится в (1), а также не в (2)

Так как это завершает все возможности, и мы обнаружили, что во всех них x находится в (1) тогда и только тогда, когда оно также находится в (2), это уравнение верно.

---

Старый ответ (для первоначального вопроса, спрашивая о малом омеги):

Нет, она не может. Формальное доказательство, основанный на set theory и тот факт, что o(g(n)) и ω(g(n)) наборы функций:

o(g(n)) = O(g(n)) \ Θ(g(n)) 
omega(g(n)) = Ω(g(n)) \ Θ(g(n)) 

o(g(n)) ∩ ω(g(n)) = { O(g(n)) \ Θ(g(n)) } ∩ { Ω(g(n)) \ Θ(g(n)) } 
        = { Ω(g(n)) ∩ O(g(n)) } \ Θ(g(n)) 
        = Θ(g(n)) \ Θ(g(n)) 
        = {} 

Поскольку o(g(n)) ∩ ω(g(n)) является пустое множество, не существует функция f(n), которая принадлежит к пересечению, таким образом, ни одна функция не принадлежит для обоих наборов.

КЭД

Answer 3

Мы можем использовать определения O (N) и Омега (N): Мы предполагаем, что существует функция г со следующими свойствами: г (п) = о (е (n)) и g (n) = Omega (f (n)).

Если g (n) = o (f (n)), то для каждой положительной константы c1: 0 < = g (n) < c1 * f (n). (1)

Если g (n) = Omega (f (n)), то существует положительная постоянная c2, для которой 0 < = c2 * f (n) < = g (n).

Заявление (1) также справедливо для c1 = с2, что означает, что = г (п) < с2 * п (п) и 0 < = с2 * Р (п) < = г (п) ,

Теперь мы имеем g (n) < c2 * f (n) и g (n)> = c2 * f (n), что невозможно, поэтому наше первоначальное предположение неверно. Итак, такой функции g нет, а пересечение o (f (n)) и Omega (f (n)) является пустым множеством.