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

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

Определения

Пусть $f(x)$ и $g(x)$ — две функции, определенные в некоторой проколотой окрестности точки $x\_0$, причем в этой окрестности $g$ не обращается в ноль.Говорят, что:
* $f$ является «O» большим от $g$ при $x\; o\; x\_0$, если существует константа $C>0$, что для всех $x$ из некоторой окрестности точки $x\_0$ имеет место неравенство
*: $|f(x)|\; le\; C\; |g(x)|$;
* $f$ является «о» малым от $g$ при $x\; o\; x\_0$, если для любого $epsilon>0$ найдется такая проколотая окрестность $U\_\{x\_0\}\text{'}$ точки $x\_0$, что для всех $xin\; U\_\{x\_0\}\text{'}$ имеет место неравенство
*: $|f(x)|\; le\; epsilon\; |g(x)|.$

Иначе говоря, в первом случае отношение $|f|/|g|$ в окрестности точки $x\_0$ ограничено сверху, а во втором оно стремится к нулю при $x\; o\; 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)$Однако на практике такая запись встречается крайне редко, в основном в простейших случаях.

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

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

* "o "( "f ") = 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 "( "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 ").

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

* "e^x " = 1 + "x " + "x "²/2 + "O "( "x "³) при "x " → 0;
* "n "! = "O "(( "n "/ "e ") ^{"n "+1/2}) при $n\; o\; infty$.

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

Реже используются обозначения:
* "f " = Ω( "g ") при "x " → "x "₀, если отношение | "f "( "x ")/ "g "( "x ")| ограничено снизу положительной константой в некоторой окрестности точки "x "₀;
* "f " = Θ( "g ") при "x " → "x "₀, если отношение | "f "( "x ")/ "g "( "x ")| ограничено положительными константами и сверху, и снизу, то есть если одновременно "f " = "O "( "g ") и "g " = "O "( "f ").

История

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

См. также

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

Литература

* Дж. Макконелл, Основы современных алгоритмов, Изд. 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, http://www.math.upenn.edu/~wilf/AlgComp3.html