Означает ли g(n) ∈ O(f(n)) f(n) ∈ Ω(g(n))?

Question

Я просто пытаюсь понять, как работают Big O и Big Omega. Я знаю, что Big O означает не лучше чем, а Big Omega означает не хуже времени бега. Итак, если у меня есть функция g(n) такая, что g(n) = O(f(n)), то могу ли я сказать, что f(n) = Ω (g(n))?

Answer 1

Для обозначения лучше написать g(n) ∈ O(f(n)), потому что "O(f(n))" можно рассматривать как множество всех функций, которые растут не быстрее, чем кратное f(н).

Давайте повторим два соответствующих формальных определения, используемых в теории сложности:

• g(n) ∈ O(f(n)) ∃ ∃k> 0 ∃N≥0 ∀n≥N [|г(н) | ≤ k· |f(n) |]
• f(n) ∈ Ω(g(n)) ∃ ∃k> 0 ∃N≥0 ∀n≥N [f(n) ≥ k·g(n)]

Если мы можем предположить, что f и g являются неотрицательными функциями (что почти всегда имеет место для функций, используемых в информатике), то мы можем отбросить знаки абсолютных значений. Таким образом:

• g(n) ∈ O(f(n)) ∃ ∃k> 0 ∃N≥0 ∀n≥N [g(n) ≤ k·f(n)]
• f(n) ∈ Ω(g(n)) ∃ ∃k> 0 ∃N≥0 ∀n≥N [f(n) ≥ k·g(n)]

Затем переверните неравенство по второму логическому утверждению:

• g(n) ∈ O(f(n)) ∃ ∃k> 0 ∃N≥0 ∀n≥N [g(n) ≤ k·f(n)]
• f(n) ∈ Ω(g(n)) ∃ ∃k> 0 ∃N≥0 ∀n≥N [k·g(n) ≤ f(n)]

Теперь давайте докажем, что правая часть первого утверждения подразумевает правую часть второго утверждения:

1. Предположим, что ∃k> 0 ∃N≥0 ∀n≥N [g(n) ≤ k·f(n)] верно.
2. Установить k> 0, удовлетворяющее условию ∃N≥0 ∀n≥N [g(n) ≤ k·f(n)].
3. Пусть kʹ = 1 /k, что является законным, потому что k ≠ 0.
4. Определить N≥0, удовлетворяющее ∀n≥N [g(n) ≤ k·f(n)].
5. Пусть n произвольное число такое, что n≥N.
6. Тогда имеем g(n) ≤ k·f(n).
7. Далее мы имеем g(n) /k ≤ f(n).
8. Подстановкой мы имеем kʹ ·g(n) ≤ f(n).
9. Поскольку n произвольно, мы получаем, что ∀n≥N [kʹ ·g(n) ≤ f(n)].
10. Мы получаем, что ∃N≥0, удовлетворяющее ∀n≥N [kʹ ·g(n) ≤ f(n)].
11. Получаем, что ∃kʹ> 0 ∃N≥0 ∀n≥N [kʹ ·g(n) ≤ f(n)].
12. Переименуем kʹ в k, так что ∃k> 0 ∃N≥0 ∀nN [k·g(n) ≤ f(n)].
13. Таким образом, [∃k> 0 ∃N≥0 ∀n≥N [g(n) ≤ k·f(n)]] подразумевает [[k> 0 ∃N≥0 ∀n≥N [k·g(n) ≤ f(n)]].
14. Следовательно, g(n) ∈ O(f(n)) влечет f(n) ∈ Ω(g(n)), как и хотелось.