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

У этого термина существуют и другие значения, см. O (значения).

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

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

В частности:

• фраза «сложность алгоритма есть O(n!)» означает, что с увеличением параметра n, характеризующего количество входной информации алгоритма, время работы алгоритма растёт не быстрее, чем пропорционально 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)|.$

Иначе говоря, в первом случае отношение $|f|/|g|$ в окрестности точки $x_0$ ограничено сверху, а во втором оно стремится к нулю при $x\to x_0$.

Обозначение

Обычно выражение «f является „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 → 0 верно, что

O(x²) = o(x),

но неверно, что

o(x) = O(x²).

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

x² + x³ ∈ O(x²)

или

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

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

x² + x³ = O(x²)

и

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

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

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

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

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

Обозначение	Интуитивное объяснение	Определение
$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₀.

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

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

• $\begin{matrix}f(n)=\Theta(g(n)) \land g(n)=\Theta(h(n)) & \Rightarrow & f(n) = \Theta (h(n)) \\ f(n)=O(g(n)) \land g(n)=O (h(n)) & \Rightarrow & f(n) = O (h(n)) \\ f(n)=\Omega(g(n)) \land g(n)=\Omega(h(n)) & \Rightarrow & f(n) = \Omega(h(n)) \\ f(n)=o(g(n)) \land g(n)= o (h(n)) & \Rightarrow & f(n) = o (h(n)) \\ f(n)=\omega(g(n)) \land g(n)=\omega(h(n)) & \Rightarrow & 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}$

Другие

• const × o(f) = o(f); const × O(f) = O(f);
• o(const × f) = o(f); O(const × f) = O(f);
• o(f) + o(f) = o(f); o(f) + O(f) = O(f); O(f) + O(f) = O(f);
• O(f) × O(g) = O(fg); o(f) × O(g) = o(fg); o(f) × o(g) = o(fg);
• O(O(f)) = O(f);
• o(o(f)), o(O(f)), O(o(f)) = o(f);
• o(-f) = o(f), O(-f) = O(f) (следствия из п. 2)

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

• Если в правой части уравнения находится только асимптотическое обозначение (например n = O(n²)), то знак равенства обозначает принадлежность множеству (n ∈ O(n²)).
• Если в уравнении асимптотические обозначения встречается в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при x → 0 формула $e^x-1 = x + o(x)$ обозначает, что $e^x-1 = x + f(x)$, где $f(x)$ — функция, о которой известно только то, что она принадлежит множеству $o(x)$. Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например,   $\sum_{i=0}^nO(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 + x²/2 + O(x³) при x → 0.
• n! = O((n/e)^n+1/2) при n → ∞.
• $T(n)=(n+1)^2=O(n^2)$ при n → ∞.

Доказательство:

Если положить $n_0=1$ и $c=4$, то для n≥1 будет выполняться неравенство $(n+1)^2<4n^2$. Отметим, что нельзя положить $n_0=0$, так как $T(0)=1$ и, следовательно, это значение при любой константе $c$ больше $c0^2=0$.

• Функция $T(n)=3n^3+2n^2$ при n → ∞ имеет степень роста $O(n^3)$. Чтобы это показать, надо положить $n_0=0$ и $c=5$. Можно, конечно, сказать, что $T(n)$ имеет порядок $O(n^4)$, но это более слабое утверждение, чем то, что $T(n)$ имеет порядок роста $O(n^3)$.
• Докажем, что функция $3^n$ при n → ∞ не может иметь порядок $O(2^n)$. Предположим, что существуют константы $c$ и $n_0$ такие, что для всех n ≥ n₀ выполняется неравенство 3ⁿ ≤ c2ⁿ. Тогда c ≥ (3/2)ⁿ для всех n ≥ n₀. Но (3/2)ⁿ принимает любое, как угодно большое, значение при достаточно большом $n$, поэтому не существует такой константы $c$, которая могла бы мажорировать (3/2)ⁿ для всех n больших некоторого n₀.
• $T(n)=n^3+2n^2$ есть $\Omega(n^3)$ при n → ∞. Для проверки достаточно положить $c=1$. Тогда $T(n)>cn^3$ для $n=0,1,...$.

История

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

См. также

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

Примечания

1. ↑ И. А. Шведов. Компактный курс математического анализа. Часть 1. Функции одной переменной. Новосибирск, 2003. С.43.

Литература

• Д. Грин, Д. Кнут Математические методы анализа алгоритмов. — Пер. с англ. — М.: Мир, 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. — С. 230—204. — ISBN 5-8459-0857-4
• Бугров, Никольский Высшая математика, том 2.