«O» большое и «o» малое

«O» большое и «o» малое ($O$ и $o$) — математические обозначения для сравнения асимптотического поведения (асимптотики) функций. Используются в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также в информатике и теории алгоритмов. Под асимптотикой понимается характер изменения функции при стремлении её аргумента к определённой точке.

$o(f)$, «о малое от $f$» обозначает «бесконечно малое относительно $f$», пренебрежимо малую величину при рассмотрении $f$. Смысл термина «О большое» зависит от его области применения, но всегда $O(f)$ растёт не быстрее, чем $f$ (точные определения приведены ниже).

В частности:

• фраза «сложность алгоритма есть $O(f(n))$» означает, что с увеличением параметра $n$, характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем $f(n)$ умноженная на некоторую константу;
• фраза «функция $f(x)$ является „о“ малым от функции $g(x)$ в окрестности точки $p$» означает, что с приближением $x$ к $p$ $f(x)$ уменьшается быстрее, чем $g(x)$ (отношение $\left|f(x)\right|/\left|g(x)\right|$ стремится к нулю).

Определения

Пусть $f(x)$ и $g(x)$ — две функции, определенные в некоторой проколотой окрестности точки $x_{0}$, причем в этой окрестности $g$ не обращается в ноль. Говорят, что:

• $f$ является «O» большим от $g$ при $x\to x_{0}$, если существует такая константа $C>0$, что для всех $x$ из некоторой окрестности точки $x_{0}$ имеет место неравенство

  $|f(x)|\leqslant C|g(x)|$;

• $f$ является «о» малым от $g$ при $x\to x_{0}$, если для любого $\varepsilon >0$ найдется такая проколотая окрестность $U_{x_{0}}'$ точки $x_{0}$, что для всех $x\in U_{x_{0}}'$ имеет место неравенство

  $|f(x)|<\varepsilon |g(x)|.$

Иначе говоря, в первом случае отношение ${\frac {|f|}{|g|}}\leqslant C$ в окрестности точки $x_{0}$ (то есть ограничено сверху), а во втором оно стремится к нулю при $x\to x_{0}$.

Обозначение

Обычно выражение «$f$ является $O$ большим ($o$ малым) от $g$» записывается с помощью равенства $f(x)=O(g(x))$ (соответственно, $f(x)=o(g(x))$).

Это обозначение очень удобно, но требует некоторой осторожности при использовании (а потому в наиболее элементарных учебниках его могут избегать). Дело в том, что это не равенство в обычном смысле, а несимметричное отношение.

В частности, можно писать

$f(x)=O(g(x))$ (или $f(x)=o(g(x))$),

но выражения

$O(g(x))=f(x)$ (или $o(g(x))=f(x)$)

бессмысленны.

Другой пример: при $x\rightarrow 0$ верно, что

$O(x^{2})=o(x)$

но

$o(x)\neq O(x^{2})$.

При любом x верно

$o(x)=O(x)$,

то есть бесконечно малая величина является ограниченной, но

$O(x)\neq o(x).$

Вместо знака равенства методологически правильнее было бы употреблять знаки принадлежности и включения, понимая $O({\,})$ и $o({\,})$ как обозначения для множеств функций, то есть, используя запись в форме

$x^{3}+x^{2}\in O(x^{3})$

или

$\mathop {O} (x^{2})\subset o(x)$

вместо, соответственно,

$x^{3}+x^{2}=O(x^{3})$

и

$\mathop {O} (x^{2})=o(x)$

Однако на практике такая запись встречается крайне редко, в основном, в простейших случаях.

При использовании данных обозначений должно быть явно оговорено (или очевидно из контекста), о каких окрестностях (одно- или двусторонних; содержащих целые, вещественные, комплексные или другие числа) и о каких допустимых множествах функций идет речь (поскольку такие же обозначения употребляются и применительно к функциям многих переменных, к функциям комплексной переменной, к матрицам и др.).

Другие подобные обозначения

Для функций $f(n)$ и $g(n)$ при $n\to n_{0}$ используются следующие обозначения:

Обозначение	Интуитивное объяснение	Определение
$f(n)\in O(g(n))$	$f$ ограничена сверху функцией $g$ (с точностью до постоянного множителя) асимптотически	$\exists (C>0),U:\forall (n\in U)\;|f(n)|\leq C|g(n)|$
$f(n)\in \Omega (g(n))$	$f$ ограничена снизу функцией $g$ (с точностью до постоянного множителя) асимптотически	$\exists (C>0),U:\forall (n\in U)\;C|g(n)|\leq |f(n)|$
$f(n)\in \Theta (g(n))$	$f$ ограничена снизу и сверху функцией $g$ асимптотически	$\exists (C>0),(C'>0),U:\forall (n\in U)\;C|g(n)|\leq |f(n)|\leq C'|g(n)|$
$f(n)\in o(g(n))$	$g$ доминирует над $f$ асимптотически	$\forall (C>0),\exists U:\forall (n\in U)\;|f(n)|<C|g(n)|$
$f(n)\in \omega (g(n))$	$f$ доминирует над $g$ асимптотически	$\forall (C>0),\exists U:\forall (n\in U)\;C|g(n)|<|f(n)|$
$f(n)~\sim ~g(n)$	$f$ эквивалентна $g$ асимптотически	$\lim _{n\to n_{0}}{\frac {f(n)}{g(n)}}=1$

где $U$ — проколотая окрестность точки $n_{0}$.

Основные свойства

Транзитивность

${\begin{matrix}f(n)=\Theta (g(n))\land g(n)=\Theta (h(n))&\implies &f(n)=\Theta (h(n))\\f(n)=O(g(n))\land g(n)=O(h(n))&\implies &f(n)=O(h(n))\\f(n)=\Omega (g(n))\land g(n)=\Omega (h(n))&\implies &f(n)=\Omega (h(n))\\f(n)=o(g(n))\land g(n)=o(h(n))&\implies &f(n)=o(h(n))\\f(n)=\omega (g(n))\land g(n)=\omega (h(n))&\implies &f(n)=\omega (h(n))\end{matrix}}$

Рефлексивность

$f(n)=\Theta (f(n))$; $f(n)=O(f(n))$; $f(n)=\Omega (f(n))$

Симметричность

$f(n)=\Theta (g(n))\Leftrightarrow g(n)=\Theta (f(n))$

Перестановочная симметрия

${\begin{matrix}f(n)=O(g(n))&\Leftrightarrow &g(n)=\Omega (f(n))\\f(n)=o(g(n))&\Leftrightarrow &g(n)=\omega (f(n))\end{matrix}}$

Другие

• $C\cdot o(f)=o(f)$

$C\cdot O(f)=O(f)$

• $o(C\cdot f)=o(f)$

$O(C\cdot f)=O(f)$

и, как следствия,

$o(-f)=o(f)$

$O(-f)=O(f)$

• $o(f)+o(f)=o(f)$

$o(f)+O(f)=O(f)+O(f)=O(f)$

• $O(f)\cdot O(g)=O(fg)$

$o(f)\cdot O(g)=o(f)\cdot o(g)=o(fg)$

• $O(O(f))=O(f)$

$o(o(f))=o(O(f))=O(o(f))=o(f)$

Асимптотические обозначения в уравнениях

• Если в правой части уравнения находится только асимптотическое обозначение (например $n=O(n^{2})$), то знак равенства обозначает принадлежность множеству ($n\in O(n^{2})$).
• Если в уравнении асимптотические обозначения встречаются в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при x → 0 формула $e^{x}-1=x+o(x)$ обозначает, что $e^{x}-1=x+f(x)$, где $f(x)$ — функция, о которой известно только то, что она принадлежит множеству $o(x)$. Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например,   $\sum _{i=0}^{n}O(n_{i}^{2})$   — содержит только одну функцию из класса $O(n^{2})$.
• Если асимптотические обозначения встречаются в левой части уравнения, используют следующее правило:
  какие бы мы функции ни выбрали (в соответствии с предыдущим правилом) взамен асимптотических обозначений в левой части уравнения, можно выбрать функции вместо асимптотических обозначений (в соответствии с предыдущим правилом) в правой части так, что уравнение будет правильным.
  Например, запись $x+o(x)=O(x)$ обозначает, что для любой функции $f(x)\in o(x)$, существует некоторая функция $g(x)\in O(x)$ такая, что выражение $x+f(x)=g(x)$ — верно для всех $x$.
• Несколько таких уравнений могут быть объединены в цепочки. Каждое из уравнений в таком случае следует интерпретировать в соответствии с предыдущим правилом.
  Например: $4n^{4}+4n^{2}+1=4n^{4}+\Theta (n^{2})=\Theta (n^{4})$. Отметим, что такая интерпретация подразумевает выполнение соотношения $4n^{4}+4n^{2}+1=\Theta (n^{4})$.

Приведенная интерпретация подразумевает выполнение соотношения:

$\left.{\begin{matrix}A=B\\B=C\end{matrix}}\right\}\Rightarrow A=C$, где A, B, C — выражения, которые могут содержать асимптотические обозначения.

Примеры использования

• $e^{x}=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+\ldots +{\frac {x^{n}}{n!}}+\ldots =1+x+{\frac {x^{2}}{2}}+O(x^{3})$ при $x\rightarrow 0$.

• $n!=O\left(\left({\frac {n}{e}}\right)^{n+{\frac {1}{2}}}\right)$ при $n\rightarrow \infty$ (следует из формулы Стирлинга)

• $T(n)=(n+1)^{2}=O(n^{2})$ при $n\rightarrow \infty$.

При $n>1$ выполнено неравенство $(n+1)^{2}<4n^{2}$. Поэтому положим $n_{0}=1,c=4$.

Отметим, что нельзя положить $n_{0}=0$, так как $T(0)=1$ и, следовательно, это значение при любой константе $c$ больше $c\cdot 0^{2}=0$.

• Функция $T(n)=3n^{3}+2n^{2}$ при $n\rightarrow \infty$ имеет степень роста $O(n^{3})$.

Чтобы это показать, надо положить $n_{0}=0$ и $c=5$. Можно, конечно, сказать, что $T(n)$ имеет порядок $O(n^{4})$, но это более слабое утверждение, чем то, что $T(n)=O(n^{3})$.

• Докажем, что функция $3^{n}$ при $n\rightarrow \infty$ не может иметь порядок $O(2^{n})$.

Предположим, что существуют константы $c$ и $n_{0}$ такие, что для всех $n\geq n_{0}$ выполняется неравенство $3^{n}\leq c\cdot 2^{n}$.

Тогда $c\geq \left({\frac {3}{2}}\right)^{n}$ для всех $n\geq n_{0}$. Но $\left({\frac {3}{2}}\right)^{n}$ принимает любое, как угодно большое, значение при достаточно большом $n$, поэтому не существует такой константы $c$, которая могла бы мажорировать $\left({\frac {3}{2}}\right)^{n}$ для всех $n$ больших некоторого $n_{0}$.

• $T(n)=n^{3}+2n^{2}=\Omega (n^{3}),n\rightarrow \infty$.

Для проверки достаточно положить $c=1$. Тогда $T(n)\geq cn^{3}$ для $n=0,1,...$.

История

Обозначение «„O“ большое» введено немецким математиком Паулем Бахманом во втором томе его книги «Analytische Zahlentheorie» (Аналитическая теория чисел), вышедшем в 1894 году. Обозначение «„о“ малое» впервые использовано другим немецким математиком, Эдмундом Ландау в 1909 году; с работами последнего связана и популяризация обоих обозначений, в связи с чем их также называют символами Ландау. Обозначение пошло от немецкого слова «Ordnung» (порядок).

См. также

• Бесконечно малая величина

Литература

• Д. Грин, Д. Кнут. Математические методы анализа алгоритмов. — Пер. с англ. — М.: Мир, 1987. — 120 с.
• Дж. Макконелл. Основы современных алгоритмов. — Изд. 2 доп. — М.: Техносфера, 2004. — 368 с. — ISBN 5-94836-005-9.
• Джон Э. Сэвидж. Сложность вычислений. — М.: Факториал, 1998. — 368 с. — ISBN 5-88688-039-9.
• В. Н. Крупский. Введение в сложность вычислений. — М.: Факториал Пресс, 2006. — 128 с. — ISBN 5-88688-083-6.
• Herbert S. Wilf. Algorithms and Complexity.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 3. Рост функций // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 87—108. — ISBN 5-8459-0857-4.
• Бугров, Никольский. Высшая математика, том 2.
• Dionysis Zindros. Введение в анализ сложности алгоритмов (рус.) (2012). Дата обращения: 11 октября 2013. Архивировано 10 октября 2013 года.