Омега = О большое?

[bot]

Встречался ли кто-нибудь, где-нибудь с обозначением $\Omega(N)$ в смысле $O(N)$ ?

[Xaositect]

Нет.
$\Omega(N)$ - это совсем наоборот.

[caxap]

$f=O(g)\iff g=\Omega (f)$

[creative]

Определения во всяком случае такие, как бы я не понимал Ваш вопрос:

$O(g(n)) = \{\ \ f(n): \exists c \wedge \exists n_0 ( \forall n \geq n_0 (\ 0 \leq f(n) \leq cg(n)\ ) \ ) \ \ \}$

$\Omega(g(n)) = \{\ \ f(n): \exists c \wedge \exists n_0 ( \forall n \geq n_0 (\ 0 \leq cg(n) \leq f(n)\ ) \ ) \ \ \}$

[mihailm]

Тоже первый раз вижу и где такое распространено?

[caxap]

mihailm в сообщении #408754 писал(а):

Тоже первый раз вижу и где такое распространено?

Это кнутовские обозначения из "Конкретной математики".

[ewert]

Оно совершенно никому не нужно. Полезны только оценки сверху.

[mihailm]

caxap в сообщении #408764 писал(а):

Это кнутовские обозначения из "Конкретной математики".

Любопытно

[caxap]

ewert в сообщении #408767 писал(а):

Полезны только оценки сверху.

Снизу тоже полезно оценивать. Например, при анализе алгоритмов.

[creative]

И у Кнута есть и в книжке "Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн Алгоритмы. Построение и анализ." (второе издание) и в этой книжке попроще, чем у Кнута написано про асимптотическую оценку (определения взял оттуда).

[bot]

caxap в сообщении #408764 писал(а):

Это кнутовские обозначения из "Конкретной математики".

Спасибо - теперь ясно откуда автор взял это обозначение, но использовал его совсем наоборот.

ewert в сообщении #408767 писал(а):

Оно совершенно никому не нужно. Полезны только оценки сверху.

В данном случае речь шла именно об оценке сверху, почему я и спросил о тождестве невиданного мной обозначения с известным.

-- Пт фев 04, 2011 15:06:29 --

Стоп - всё верно. Автор ведь и в самом деле указывал две границы нижней оценки алгоритма и вторую я принял за верхнюю, в то время как при незначительном изменении доказательства верхняя оценка совпадёт с первой нижней оценкой.