«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)$ (отношение $|f(x)|/|g(x)|$ стремится к нулю).

Определения

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

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

  $|f(x)|⩽C|g(x)|$;

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

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

Иначе говоря, в первом случае отношение $\frac{|f|}{|g|}⩽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\to 0$ верно, что

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

но

$o(x)\ne O(x^2)$.

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

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

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

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

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

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

или

$O(x^2)\subset o(x)$

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

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

и

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

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

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

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

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

Обозначение	Интуитивное объяснение	Определение
$f(n)\in O(g(n))$	$f$ ограничена сверху функцией $g$ (с точностью до постоянного множителя) асимптотически	$\mathrm{\exists }(C>0),U:\mathrm{\forall }(n\in U)|f(n)|\le C|g(n)|$
Шаблон:Якорь2	$f$ ограничена снизу функцией $g$ (с точностью до постоянного множителя) асимптотически	$\mathrm{\exists }(C>0),U:\mathrm{\forall }(n\in U)C|g(n)|\le |f(n)|$
Шаблон:Якорь2	$f$ ограничена снизу и сверху функцией $g$ асимптотически	$\mathrm{\exists }(C>0),(C^{\prime }>0),U:\mathrm{\forall }(n\in U)C|g(n)|\le |f(n)|\le C^{\prime }|g(n)|$
$f(n)\in o(g(n))$	$g$ доминирует над $f$ асимптотически	$\mathrm{\forall }(C>0),\mathrm{\exists }U:\mathrm{\forall }(n\in U)|f(n)|<C|g(n)|$
Шаблон:Якорь2	$f$ доминирует над $g$ асимптотически	$\mathrm{\forall }(C>0),\mathrm{\exists }U:\mathrm{\forall }(n\in U)C|g(n)|<|f(n)|$
$f(n)\sim g(n)$	$f$ эквивалентна $g$ асимптотически	$\underset{n\to n_0}{\lim }\frac{f(n)}{g(n)}=1$

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

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

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

$\begin{array}{ccc}f(n)=\mathrm{\Theta }(g(n))\wedge g(n)=\mathrm{\Theta }(h(n))& ⟹& f(n)=\mathrm{\Theta }(h(n))\\ f(n)=O(g(n))\wedge g(n)=O(h(n))& ⟹& f(n)=O(h(n))\\ f(n)=\mathrm{\Omega }(g(n))\wedge g(n)=\mathrm{\Omega }(h(n))& ⟹& f(n)=\mathrm{\Omega }(h(n))\\ f(n)=o(g(n))\wedge g(n)=o(h(n))& ⟹& f(n)=o(h(n))\\ f(n)=\omega (g(n))\wedge g(n)=\omega (h(n))& ⟹& f(n)=\omega (h(n))\end{array}$

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

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

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

$f(n)=\mathrm{\Theta }(g(n))\iff g(n)=\mathrm{\Theta }(f(n))$

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

$\begin{array}{ccc}f(n)=O(g(n))& \iff & g(n)=\mathrm{\Omega }(f(n))\\ f(n)=o(g(n))& \iff & g(n)=\omega (f(n))\end{array}$

Другие

• $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+\mathrm{\Theta }(n^2)=\mathrm{\Theta }(n^4)$. Отметим, что такая интерпретация подразумевает выполнение соотношения $4n^4+4n^2+1=\mathrm{\Theta }(n^4)$.

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

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

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

• $e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots +\frac{x^n}{n!}+\dots =1+x+\frac{x^2}{2}+o(x^2)$ при $x\to 0$.

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

• $T(n)=(n+1{)}^2=O(n^2)$ при $n\to \mathrm{\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\to \mathrm{\infty }$ имеет степень роста $O(n^3)$.

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

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

Предположим, что существуют константы $c$ и $n_0$ такие, что для всех $n\ge n_0$ выполняется неравенство $3^n\le c\cdot 2^n$.

Тогда $c\ge {\left(\frac{3}{2}\right)}^n$ для всех $n\ge 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=\mathrm{\Omega }(n^3),n\to \mathrm{\infty }$.

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

История

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга:CLRS
• Шаблон:Книга
• Шаблон:Cite web