Big-O обозначение 1 / O (n) = Омега (n)

Question

Я получил задание доказать 1/O(n) = Ω(n)

Однако это будет означать, что n элемент O(n) => 1/n элемент Ω(n), что явно неверно.

Итак, мой вопрос: верно ли утверждение 1/O(n) = Ω(n)?

РЕДАКТИРОВАТЬ: Я отправляю письмо помощнику, который написал вопросы. И использовал пример f(n) = 1. Затем он сказал, что утверждение действительно неверно.

Answer 1

Обозначение 1 / O (n) = Ω (n) немного расплывчато. На самом деле O (n) не существует, есть только f (n) ~ O (n) , что является утверждением о значениях функции f (существует постоянная C , так что f (n) для каждого n ).

И утверждение, чтобы доказать, если я правильно понимаю, это «если функция f (n) равна O (n) , чем 1 / f (n)» is Ω (n)", формально:

f (n) ~ O (n) => 1 / f (n) ~ Ω (n)

Редактировать: За исключением того, что я не думаю, что я правильно понимаю, потому что f (n) = 1 ~ O (n) , но 1 / f (n ) = f (n) = 1 явно не Ω (n) . Разве не было присвоение f (n) ~ O (n) => 1 / f (n) ~ Ω (1 / n) вместо этого?

Редактировать: Разные люди, как правило, используют разные операторы. Наиболее распространенным является f (n) = O (n) , но это сбивает с толку, поскольку правая часть не является функцией, поэтому она не может быть нормальным равенством. Мы обычно использовали f (n) ~ O (n) в школе, что менее запутанно, но все же несовместимо с обычным использованием этого оператора для общих отношений эквивалентности. Наиболее согласованным оператором будет f (n) ∈ O (n) , потому что правая часть может быть разумно обработана как набор функций.

Answer 2

O (n) более или менее подразумевает следующее, для некоторой полиномиальной функции f (x), некоторой полиномиальной функции g (x) и O (f (x)):
По величине имеем |е (х) |<= M | g (x) |, для некоторого M. В принципе, <em>f ограничен сверху постоянным временем g .

Ω (n) означает, что для некоторого полинома h (x), некоторые полиномы k (x) и Ω (h (x)):
По величине | h (x) |> = M | k (x) |, для некоторого M. В основном h ограничено снизу постоянным временем k .

Итак, для (O (f (x)))^ -1, 1 / | f (x) |<= 1 / (M | g (x) |).Немного перестановки дает M | g (x) |<= | f (x) |- т.е. f (x) ограничен снизу постоянной величиной g, которая <em>точно такая же , что и наше определение для Ω (n) выше.

Чуть сложнее быть формальнымдоказательство, но оно должно начать вас.