ВПЕРЁД ⇒

Асимптотическое обозначение тета-большое

⇐ НАЗАД

Асимптотическое обозначение о-большое

Асимптотическое обозначение омега-большое

Сначала объясним понятие асимптотического обозначения $Ω$ (омега-большое) на простом конкретном примере, а затем дадим формальное определение этому асимптотическому обозначению.

Простое объяснение для омега-большое

Для алгоритма поиска минимального элемента в массиве размерностью $n$ мы получили следующую зависимость для наихудшего и наилучшего случаев входных данных:

$T (n) = 6 n + 3$ , где $n$ - линейный порядок роста сложности вычислений алгоритма. То есть функция $T (n)$ ведёт себя линейным образом.

Зная порядок роста сложности вычислений алгоритма, мы можем не указывать точное выражение для сложности вычислений $T (n)$ , достаточно просто подчеркнуть тот факт, что нам известно, каким порядком роста обладает искомая зависимость:

$T (n) = 6 n + 3 = Ω (n)$ , где $Ω (n)$ - асимптотическая оценка для времени работы $T (n)$ в наилучшем случае входных данных. Оценка $Ω (n)$ говорит о том, что в некотором множестве $M$ существует некоторая неизвестная нам точная оценка для $T (n)$ такая, что порядок роста этой точной оценки (то есть порядок роста искомой функции $T$ ) в наилучшем случае линеен, то есть равен $n$ . Обозначение $Ω (...)$ , применяющееся в математическом анализе для оценки любой произвольной функции, носит название $Ω$ -нотации/обозначения (нотации омега-большое; big-omega notation). В случае анализа алгоритмов, данная нотация говорит нам о том, что, с ростом размера входных данных, время работы алгоритма увеличивается не медленней, чем порядок роста, указанный во входном параметре оценки (в данном примере, не медленней, чем $n$ ). Иными словами, рассматриваемый алгоритм работает (в контексте скорости исполнения) не лучше указанного порядка роста ( $n$ ).

Математическое определение для омега-большое

Для функции $f (n)$ можно рассматривать асимптотическую оценку $Ω (g (n))$ снизу, то есть рассматривать существование функции $g (n)$ такой, что с увеличением параметра $n$ будет выполняться условие $f (n) \geq c \cdot g (n) \geq 0$ .

Подобно тому, как в $O$ -нотации для некоторой функции $f (x)$ даётся её асимптотическая верхняя граница, в $Ω$ -нотации для этой функции даётся её асимптотическая нижняя граница, представляющая собой некоторую другую функцию $h (x)$ такую, что для неё можно найти значение $x_{0}$ , для которого будет справедливо следующее утверждение: если $x \geq x_{0}$ , то $0 \leq h (x) \leq f (x)$ .

Для заданной функции $g (n)$ запись $Ω (g (n))$ (которая произносится как “омега-большое от $g$ от $n$ ”) обозначает множество функций $M = {f_{1} (n), f_{2} (n), ..., f_{m} (n)}$ такое, что для всех функций из этого множества можно найти некоторые положительные константы $c$ и $n_{0}$ такие, что $0 \leq c \cdot g (n) \leq f_{k} (n)$ для всех $n \geq n_{0}$ и всех $k$ из ${1, ..., m}$ .

Ниже представлено определение для $Ω$ -нотации в математической символьной форме (расшифровка математической записи идёт сразу следом за самой математической записью):

Определение $Ω$ -нотации

$f (n) = Ω (g (n)) \Leftrightarrow \exists n_{0} > 0, c > 0 : \forall n \geq n_{0} \Rightarrow 0 \leq c \cdot g (n) \leq f (n)$ .

Расшифровка математической записи:

Утверджение $f (n) = Ω (g (n))$ эквивалентно (равносильно) утверждению, что существуют положительные константы $n_{0}$ и $с$ такие, что для любых значений $n$ , больших или равных $n_{0}$ , выполняется условие $0 \leq c \cdot g (n) \leq f (n)$ , то есть из выполнения условия $n \geq n_{0}$ следует выполнение условия $0 \leq c \cdot g (n) \leq f (n)$ .

Исходя из данного выше определения, обозначение $Ω (g (n))$ носит название асимптотической оценки функции $f (n)$ снизу и означает, что с увеличением параметра $n$ функция $f (n)$ будет ограничена снизу значениями (не будет лежать ниже значений) некоторой функции $c \cdot g (n)$ .

Обратите внимание: $Ω (g (n))$ на самом деле представляет собой множество, содержащее в себе функцию $f (n)$ , то есть можно сделать запись " $f (n) \in Ω (g (n))$ ", чтобы указать на тот факт, что $f (n)$ является членом $Ω (g (n))$ .

Однако, вместо использования математически правильной записи " $f (n) \in Ω (g (n))$ ", для удобства обычно используют менее точную (с математической точки зрения) запись " $f (n) = Ω (g (n))$ ". Эта запись и соответствующий ей выше рисунок интуитивно воспринимаются читателем как: “Для всех значений $n$ , лежащих справа от $n_{0}$ , значения функции $f (n)$ больше или равны значениям функции $c \cdot g (n)$ “.

Возвращаясь к алгоритму поиска минимального элемента в массиве размерностью $n$ и его времени работы $T (n) = 6 n + 3$ , можем сделать очевидный вывод о существовании констант $c$ и $n_{0}$ таких, что будет выполняться условие $6 n + 3 \geq c \cdot n \geq 0$ для $n \geq n_{0}$ . Например, для $c = 6$ и $n_{0} = 0$ получаем, что $6 n + 3 \geq 6 n \geq 0$ для $n \geq 0$ . Это и означает, что $T (n) = Ω (n)$ .

Итак, когда мы встречаем в тексте запись " $f (n) = Ω (g (n))$ ", то это означает, что нами рассматривается условие $0 \leq c \cdot g (n) \leq f (n)$ . Если $c_{0}$ - максимальное из возможных значений константы $c$ , при котором всё ещё соблюдается указанное условие, то из этого очевидным образом следует, что данное условие будет соблюдаться для любого значения $c_{1}$ такого, что $c_{1} < c_{0}$ . То есть мы можем вплоть до нуля уменьшать значение $c_{1}$ (начиная со значения $c_{0}$ ), и получаемая по мере уменьшения этого параметра функция $c_{1} g (n)$ будет всё сильней и сильней отдаляться от оцениваемой функции $f (n)$ , что в свою очередь будет означать, что мы просто расширяем область, охватываемую множеством $Ω (g (n))$ , а сама функция $f (n)$ всё также будет оставаться в этом множестве. Из этого можно сделать ещё один вывод: множество $Ω (g (n))$ может быть каким угодно большим, главное, чтобы в это множество попадала исходная функция $f (n)$ .

Очевидно, что если множество функций $Ω (g_{1} (n))$ , имееющее порядок роста $g_{1} (n)$ , содержит в себе исходную оцениваемую функцию $f (n)$ , то это означает, что и множество функций $Ω (g_{2} (n))$ , имеющее порядок роста $g_{2} (n)$ меньший, чем $g_{1} (n)$ , также будет содержать в себе целевую функцию $f (n)$ :

$f (n) = Ω (g_{1} (n)) = Ω (g_{2} (n))$ , где $g_{2} (n) < g_{1} (n)$

Исходя из сказанного, оценку ранее упомянутого алгоритма поиска минимального элемента в массиве можно переписать в следующем виде:

$T (n) = 6 n + 2 = Ω (n) = Ω (n^{0}) = Ω (n^{- 1}) = ... = Ω (n^{- k})$ ;

Иными словами, с математической точки зрения, при определении асимптотической нижней границы, не очень то и важно, насколько близко функция $f (n)$ находится к этой нижней границе, главное, чтобы эта нижняя граница росла не быстрей, чем растёт функция $f (n)$ . В этом и кроется весь математический смысл асимптотического обозначения $Ω$ .

Однако, для оценки времени работы алгоритмов $T (n)$ , условимся под асимптотическим обозначением $Ω$ понимать множество функций $Ω (g (n))$ , обладающее для $T (n)$ наибольшим из возможных порядков роста $g (n)$ . То есть, если исходная функция $T (n)$ , к примеру, является кубической ( $T (n) = a n^{3} + b n^{2} + c n + d$ ), то и для множества функций $Ω (g (n))$ будет указываться кубический порядок роста ( $g (n) = n^{3}$ ).

Для примера, рассмотрим некоторую кубическую функцию $T (n)$ и сравним для неё следующие асимптотические обозначения:

$T (n) = a n^{3} + b n^{2} + c n + d = Ω (n^{3})$ ;
$T (n) = a n^{3} + b n^{2} + c n + d = Ω (n)$ .

Обе указанные записи являются корректными (с математической точки зрения), но только первый вариант даёт истинное понимание того, каким образом изменяется/растёт время работы алгоритма $T (n)$ . В данном случае мы можем сказать, что время работы алгоритма $T (n)$ с увеличением размера входных данных $n$ растёт не медленней, чем кубическая зависимость $n^{3}$ .

ВПЕРЁД ⇒

Асимптотическое обозначение тета-большое

⇐ НАЗАД

Асимптотическое обозначение о-большое

Источники

Павел Маврин “АиСД, Семестр 1, Лекция 1. Оценка времени. Сортировка слиянием”

Big O нотация (Wiki)

Томас Кормен “Алгоритмы. Построение и анализ”. Глава 3 “Рост функций”, параграф 3.1 “Асимптотические обозначения” (стр. 68-78).

Категория

Алгоритмы-и-структуры-данных Алгоритмы-и-структуры-данных

Теги

Алгоритм Алгоритм

Сложность-по-времени Сложность-по-времени

Временная-сложность Временная-сложность

Time-complexity Time-complexity

Сложность-вычислений Сложность-вычислений

Асимптотическая-оценка Асимптотическая-оценка

Оценка-сложности-вычислений Оценка-сложности-вычислений

Big-Omega Big-Omega

🖥️ Математика, Информатика и Инженерия ПО

Проводник

09. Асимптотическое обозначение омега-большое

Асимптотическое обозначение омега-большое

Простое объяснение для омега-большое

Математическое определение для омега-большое

Вид графа

Оглавление

Обратные ссылки