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

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

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

В частности:

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

Определения

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

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

  ${\displaystyle |f(x)|\leqslant C|g(x)|}$;

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

  ${\displaystyle |f(x)|<\varepsilon |g(x)|.}$

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

Обозначение

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

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

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

${\displaystyle f(x)=O(g(x))}$ (или ${\displaystyle f(x)=o(g(x))}$),

но выражения

${\displaystyle O(g(x))=f(x)}$ (или ${\displaystyle o(g(x))=f(x)}$)

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

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

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

но

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

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

${\displaystyle o(x)=O(x)}$,

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

${\displaystyle O(x)\neq o(x).}$

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

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

или

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

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

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

и

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

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

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

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle f(n)=\Theta (f(n))}$; ${\displaystyle f(n)=O(f(n))}$; ${\displaystyle f(n)=\Omega (f(n))}$

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

${\displaystyle f(n)=\Theta (g(n))\Leftrightarrow g(n)=\Theta (f(n))}$

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

${\displaystyle {\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}}}$

Другие

• ${\displaystyle C\cdot o(f)=o(f)}$

${\displaystyle C\cdot O(f)=O(f)}$

• ${\displaystyle o(C\cdot f)=o(f)}$

${\displaystyle O(C\cdot f)=O(f)}$

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

${\displaystyle o(-f)=o(f)}$

${\displaystyle O(-f)=O(f)}$

• ${\displaystyle o(f)+o(f)=o(f)}$

${\displaystyle o(f)+O(f)=O(f)+O(f)=O(f)}$

• ${\displaystyle O(f)\cdot O(g)=O(fg)}$

${\displaystyle o(f)\cdot O(g)=o(f)\cdot o(g)=o(fg)}$

• ${\displaystyle O(O(f))=O(f)}$

${\displaystyle o(o(f))=o(O(f))=O(o(f))=o(f)}$

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

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

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

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

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

• ${\displaystyle 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^{2})}$ при ${\displaystyle x\rightarrow 0}$.

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

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

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

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

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

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

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

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

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

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

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

История

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

См. также

• Бесконечно малая и бесконечно большая

Примечания

1. Шведов И. А. Компактный курс математического анализа. Часть 1. Функции одной переменной. — Новосибирск, 2003. — С. 43.
2. D.E. Knuth. Big Omicron and big Omega and big Theta (англ.) : Article. — ACM Sigact News, 1976. — Т. 8, № 2. — С. 18—24. Архивировано 15 августа 2016 года.

Литература

• Д. Грин, Д. Кнут. Математические методы анализа алгоритмов. — Пер. с англ. — М.: Мир, 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 года.