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

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

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

В частности:

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

ОпределенияПравить

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

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

  $|f(x)|⩽<!--\; ⩽\; -->C|g(x)|$$|f(x)| \leqslant C |g(x)|$ ;

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

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

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

ОбозначениеПравить

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

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

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

$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)$  (или $o(g(x))=f(x)$$o(g(x)) = f(x)$ )

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

Другой пример: при $x\to <!--\; \to \; -->0$$x \rightarrow 0$  верно, что

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

но

$o(x)\ne <!--\; \ne \; -->O(x^2)$$o(x)\neq O(x^{2})$ .

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

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

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

$O(x)\ne <!--\; \ne \; -->o(x).$$O(x)\neq o(x).$ 

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

$x^3+x^2\in <!--\; \in \; -->O(x^3)$$x^{3}+x^{2}\in O(x^{3})$ 

или

$O<!--\; \; -->(x^2)\subset <!--\; \subset \; -->o(x)$$\mathop O(x^2)\subset o(x)$ 

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

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

и

$O<!--\; \; -->(x^2)=o(x)$$\mathop O(x^2) = o(x)$ 

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

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

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

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

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

где $U$$U$  — проколотая окрестность точки $n_0$$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)=\mathrm{\Theta <!--\; \Theta \; -->}(f(n))$$f(n)=\Theta(f(n))$ ; $f(n)=O(f(n))$$f(n)=O(f(n))$ ; $f(n)=\mathrm{\Omega <!--\; \Omega \; -->}(f(n))$$f(n)=\Omega(f(n))$ 

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

$f(n)=\mathrm{\Theta <!--\; \Theta \; -->}(g(n))\iff <!--\; \iff \; -->g(n)=\mathrm{\Theta <!--\; \Theta \; -->}(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 <!--\; \cdot \; -->o(f)=o(f)$$C \cdot o(f) = o(f)$ 

$C\cdot <!--\; \cdot \; -->O(f)=O(f)$$C \cdot O(f) = O(f)$ 

• $o(C\cdot <!--\; \cdot \; -->f)=o(f)$$o(C \cdot f) = o(f)$ 

$O(C\cdot <!--\; \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) = 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 <!--\; \cdot \; -->O(g)=O(fg)$$O(f) \cdot O(g) = O(fg)$ 

$o(f)\cdot <!--\; \cdot \; -->O(g)=o(f)\cdot <!--\; \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(f)$ 

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

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

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

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

$\begin{array}{c}A=B\\ B=C\end{array}\}\Rightarrow <!--\; \Rightarrow \; -->A=C$$\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!}+\dots <!--\; \dots \; -->+\frac{x^n}{n!}+\dots <!--\; \dots \; -->=1+x+\frac{x^2}{2}+O(x^3)$$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\to <!--\; \to \; -->0$$x \rightarrow 0$ .

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

• $T(n)=(n+1{)}^2=O(n^2)$$T(n)=(n+1)^2=O(n^2)$  при $n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}$$n \rightarrow \infty$ .

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

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

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

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

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

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

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

• $T(n)=n^3+2n^2=\mathrm{\Omega <!--\; \Omega \; -->}(n^3),n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}$$T(n)=n^3+2n^2 = \Omega(n^3), n \rightarrow \infty$ .

Для проверки достаточно положить $c=1$$c=1$ . Тогда $T(n)\ge <!--\; \ge \; -->c{n}^3$$T(n) \geq cn^3$  для $n=0,1,...$$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 года.