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

---

ВПЕРЁД ⇒

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

⇐ НАЗАД

Асимптотические обозначения

---

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

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

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

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

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

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

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

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

$O$-обозначение ($O$-нотация) используется для определения у некоторой функции $f(x)$ её асимптотической верхней границы, представляющей собой некоторую другую функцию $h(x)$ такую, что для неё можно найти значение $x_0$, для которого будет справедливо следующее утверждение: если $x\ge x_0$, то $h(x)\ge f(x)\ge 0$.

Для заданной функции $g(n)$ запись $O(g(n))$ (которая произносится как “о-большое от $g$ от $n$”) обозначает множество функций $M=\{f_1(n),f_2(n),...,f_m(n)\}$ такое, что для всех функций из этого множества можно найти некоторые положительные константы $c$ и $n_0$ такие, что $0\le f_k(n)\le c\cdot g(n)$ для всех $n\ge n_0$ и всех $k$ из $\{1,...,m\}$.

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

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

$f(n)=O(g(n))\iff \exists n_0>0,c>0:\forall n\ge n_0\Rightarrow 0\le f(n)\le c\cdot g(n)$.

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

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

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

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

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

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

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

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

$f(n)=O(g_1(n))=O(g_2(n))$, где $g_2(n)>g_1(n)$

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

$T(n)=6n+2=O(n)=O(n^2)=...=O(n^k)$

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

Однако, для оценки времени работы алгоритмов $T(n)$, условимся под асимптотическим обозначением $O$ понимать множество функций $O(g(n))$, обладающее для $T(n)$ наименьшим из возможных порядков роста $g(n)$. То есть, если исходная функция $T(n)$, к примеру, является линейной ($T(n)=an+b$), то и для множества функций $O(g(n))$ будет указываться линейный порядок роста ($g(n)=n$).

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

1. $T(n)=a{n}^2+bn+c=O(n^2)$;
2. $T(n)=a{n}^2+bn+c=O(n^{10})$.

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

---

ВПЕРЁД ⇒

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

⇐ НАЗАД

Асимптотические обозначения

---

Источники

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

Категория

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

Теги

• Алгоритм Алгоритм
• Сложность-по-времени Сложность-по-времени
• Временная-сложность Временная-сложность
• Time-complexity Time-complexity
• Сложность-вычислений Сложность-вычислений
• Асимптотическая-оценка Асимптотическая-оценка
• Оценка-сложности-вычислений Оценка-сложности-вычислений
• Big-O Big-O