ru.wikipedia.org

«O» большое и «o» малое — Википедия

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

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

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

В частности:

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

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

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

но

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

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

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

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

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

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

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

или

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

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

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

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

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

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

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

Обозначение	Интуитивное объяснение	Определение
$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_{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)=\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}}$

$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}+\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 — выражения, которые могут содержать асимптотические обозначения.

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

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

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

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

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

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

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

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

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