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

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

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

В частности:

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

Определения

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

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

  [math]\displaystyle{ |f(x)| \leqslant C |g(x)| }[/math];

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

  [math]\displaystyle{ |f(x)| \lt \varepsilon |g(x)|. }[/math]

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

Обозначение

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

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

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

[math]\displaystyle{ f(x) = O(g(x)) }[/math] (или [math]\displaystyle{ f(x) = o(g(x)) }[/math]),

но выражения

[math]\displaystyle{ O(g(x)) = f(x) }[/math] (или [math]\displaystyle{ o(g(x)) = f(x) }[/math])

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

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

[math]\displaystyle{ O(x^2) = o(x) }[/math]

но

[math]\displaystyle{ o(x) \ne O(x^2) }[/math].

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

[math]\displaystyle{ o(x) = O(x) }[/math],

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

[math]\displaystyle{ O(x) \ne o(x) . }[/math]

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

[math]\displaystyle{ x^3 + x^2 \in O(x^3) }[/math]

или

[math]\displaystyle{ \mathop O(x^2)\subset o(x) }[/math]

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

[math]\displaystyle{ x^3 + x^2 = O(x^3) }[/math]

и

[math]\displaystyle{ \mathop O(x^2) = o(x) }[/math]

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

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

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

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

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

где [math]\displaystyle{ U }[/math] — проколотая окрестность точки [math]\displaystyle{ n_0 }[/math].

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

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

[math]\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} }[/math]

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

[math]\displaystyle{ f(n)=\Theta(f(n)) }[/math]; [math]\displaystyle{ f(n)=O(f(n)) }[/math]; [math]\displaystyle{ f(n)=\Omega(f(n)) }[/math]

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

[math]\displaystyle{ f(n)=\Theta(g(n)) \Leftrightarrow g(n)=\Theta(f(n)) }[/math]

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

[math]\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} }[/math]

Другие

• [math]\displaystyle{ C \cdot o(f) = o(f) }[/math]

[math]\displaystyle{ C \cdot O(f) = O(f) }[/math]

• [math]\displaystyle{ o(C \cdot f) = o(f) }[/math]

[math]\displaystyle{ O(C \cdot f) = O(f) }[/math]

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

[math]\displaystyle{ o(-f) = o(f) }[/math]

[math]\displaystyle{ O(-f) = O(f) }[/math]

• [math]\displaystyle{ o(f) + o(f) = o(f) }[/math]

[math]\displaystyle{ o(f) + O(f) = O(f) + O(f) = O(f) }[/math]

• [math]\displaystyle{ O(f) \cdot O(g) = O(fg) }[/math]

[math]\displaystyle{ o(f) \cdot O(g) = o(f) \cdot o(g) = o(fg) }[/math]

• [math]\displaystyle{ O(O(f)) = O(f) }[/math]

[math]\displaystyle{ o(o(f)) = o(O(f)) = O(o(f)) = o(f) }[/math]

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

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

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

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

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

• [math]\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^3) }[/math] при [math]\displaystyle{ x \rightarrow 0 }[/math], где [math]\displaystyle{ O(x^3) }[/math] - остаточный член.

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

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

При [math]\displaystyle{ n \gt 1 }[/math] выполнено неравенство [math]\displaystyle{ (n+1)^2\lt 4n^2 }[/math]. Поэтому положим [math]\displaystyle{ n_0=1, c=4 }[/math].

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

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

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

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

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

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

• [math]\displaystyle{ T(n)=n^3+2n^2 = \Omega(n^3), n \rightarrow \infty }[/math].

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

История

Обозначение «„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 года.