Big O и Big Omega такие же, но наоборот?

Question

Это правда?

f(n) = O(g(n)) === g(n) = Omega(f(n)) 

В основном они взаимозаменяемы, поскольку они являются противоположностями?

Итак, если F находится в Big O of G, то G является большой омегой F?

Answer 1

I Я никогда не особо интересовался обозначением. Самый простой способ подумать о том, что обозначение Big-O является «наихудшим случаем», а «Большая Омега» - «лучший случай».

Есть, конечно, другие вещи, которые могут вас заинтересовать. Например, вы, , могли заявить, что следующий (довольно немой) алгоритм линейного поиска - O (n), но было бы более точным заявить, что это будет всегда быть точно пропорциональна п:

public bool Contains(List<int> list, int number) 
{ 
    bool contains = false; 
    foreach (int num in list) 
    { 
     // Note that we always loop through the entire list, even if we find it 
     if (num == number) 
     contains = true; 
    } 

    return contains; 
} 

Мы могли бы, в качестве альтернативы, утверждают, что это как O (п) и Омега (п). Для этого случая введем обозначения Тета (п).

Есть и другие случаи, такие как средний случай. Средний случай часто будет таким же, как и лучший или худший случай. Например, наилучшим примером хорошо реализованного линейного поиска является O (1) (если элемент, который вы ищете, является первым элементом в списке), но в худшем случае O (n) (поскольку вы можете иметь для поиска по всему списку, чтобы обнаружить, что этого элемента нет). Если в списке содержится элемент, в среднем для его поиска потребуется n/2 шага (потому что мы, в среднем, должны просмотреть половину списка, чтобы найти элемент). Обычно мы отбрасываем часть «/ 2» и просто говорим, что средний случай равен O (n).

Они не строго имеют, чтобы быть тем же. Я видел некоторый аргумент о том, следует ли считать «лучший» случай для поиска двоичного дерева поиска O (1) (поскольку элемент, который вы ищете, может быть первым элементом на дереве), или если его следует рассматривать O (log n) (потому что «оптимальный» случай для двоичного поиска - это если дерево отлично сбалансировано). (См. here для обсуждения вставки BST). Средний случай, безусловно, равен O (log n). В худшем случае O (n) (если дерево двоичного поиска полностью un сбалансировано). Если взять наилучший случай O (1), то средний случай будет равен O (log n), а наихудший случай - O (n), тогда средний, худший и лучший случай, очевидно, будут разными.

Answer 2

Это помогает взглянуть на определении:

f(n) is in O(g(n)) if and only if: 
There are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. 


g(n) is in Omega(f(n)) if and only if: 
There are positive constants c and k, such that g(n) ≥ cf(n) ≥ 0 for all n ≥ k. 

Если вы можете найти значение с и к, которые делают F (N) в O (г (п)), то одни и те же значения будут также показывать g (n) - Омега (f (n)) (просто разделим обе части неравенства на c). Вот почему они взаимозаменяемы.

F (п) не Theta (г (п)), если оно не является и в O (г (п) и Омега (г (п)).

Надежда, что помогает!