«O» большое
и
«o» малое
(
и
) — математические обозначения для сравнения асимптотического поведения (асимптотики)
функций
. Используются в различных разделах математики, но активнее всего — в
математическом анализе
,
теории чисел
и
комбинаторике
, а также в
информатике
и
теории алгоритмов
. Под
асимптотикой
понимается характер изменения функции при стремлении её аргумента к определённой точке.
, «
о
малое от
» обозначает «бесконечно малое относительно
»
, пренебрежимо малую величину при рассмотрении
. Смысл термина «О большое» зависит от его области применения, но всегда
растёт не быстрее, чем
(точные определения приведены ниже).
В частности:
фраза «
сложность алгоритма
есть
» означает, что с увеличением параметра
, характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем
, умноженная на некоторую константу;
фраза «функция
является „о“ малым от функции
в окрестности точки
» означает, что с приближением
к
уменьшается быстрее, чем
(отношение
стремится к нулю).
Содержание
Определения
Пусть
и
— две функции, определённые в некоторой
проколотой окрестности
точки
, причём в этой окрестности
не обращается в ноль. Говорят, что:
является «O» большим от
при
, если существует такая константа
, что для всех
из некоторой окрестности точки
имеет место неравенство
;
является «о» малым от
при
, если для любого
найдется такая проколотая окрестность
точки
, что для всех
имеет место неравенство
Иначе говоря, в первом случае отношение
в окрестности точки
(то есть ограничено сверху), а во втором оно стремится к нулю при
.
Обозначение
Обычно выражение «
является
большим (
малым) от
» записывается с помощью равенства
(соответственно,
).
Это обозначение очень удобно, но требует некоторой осторожности при использовании (а потому в наиболее элементарных учебниках его могут избегать). Дело в том, что это не равенство в обычном смысле, а несимметричное
отношение
.
В частности, можно писать
(или
),
но выражения
(или
)
бессмысленны.
Другой пример: при
верно, что
но
.
При любом x верно
,
то есть бесконечно малая величина является ограниченной, но
Вместо знака равенства методологически правильнее было бы употреблять знаки принадлежности и включения, понимая
и
как обозначения для множеств функций, то есть, используя запись в форме
или
вместо, соответственно,
и
Однако на практике такая запись встречается крайне редко, в основном, в простейших случаях.
При использовании данных обозначений должно быть явно оговорено (или очевидно из контекста), о каких окрестностях (одно- или двусторонних; содержащих целые, вещественные, комплексные или другие числа) и о каких допустимых множествах функций идет речь (поскольку такие же обозначения употребляются и применительно к функциям многих переменных, к функциям комплексной переменной, к матрицам и др.).
Другие подобные обозначения
Для функций
и
при
используются следующие обозначения:
Обозначение
Интуитивное объяснение
Определение
ограничена сверху функцией
(с точностью до постоянного множителя) асимптотически
ограничена снизу функцией
(с точностью до постоянного множителя) асимптотически
Если в правой части уравнения находится только асимптотическое обозначение (например
), то знак равенства обозначает принадлежность множеству (
).
Если в уравнении асимптотические обозначения встречаются в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при
x
→ 0 формула
обозначает, что
, где
— функция, о которой известно только то, что она принадлежит множеству
. Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например,
— содержит только одну функцию из класса
.
Если асимптотические обозначения встречаются в левой части уравнения, используют следующее правило:
какие бы мы функции ни выбрали (в соответствии с предыдущим правилом) взамен асимптотических обозначений в левой части уравнения, можно выбрать функции вместо асимптотических обозначений (в соответствии с предыдущим правилом) в правой части так, что уравнение будет правильным
.
Например, запись
обозначает, что для любой функции
, существует некоторая функция
такая, что выражение
— верно для всех
.
Несколько таких уравнений могут быть объединены в цепочки. Каждое из уравнений в таком случае следует интерпретировать в соответствии с предыдущим правилом.
Например:
. Отметим, что такая интерпретация подразумевает выполнение соотношения
.
Приведенная интерпретация подразумевает выполнение соотношения:
, где
A
,
B
,
C
— выражения, которые могут содержать асимптотические обозначения.
Отметим, что нельзя положить
, так как
и, следовательно, это значение при любой константе
больше
.
Функция
при
имеет степень роста
.
Чтобы это показать, надо положить
и
. Можно, конечно, сказать, что
имеет порядок
, но это более слабое утверждение, чем то, что
.
Докажем, что функция
при
не может иметь порядок
.
Предположим, что существуют константы
и
такие, что для всех
выполняется неравенство
.
Тогда
для всех
. Но
принимает любое, как угодно большое, значение при достаточно большом
, поэтому не существует такой константы
, которая могла бы мажорировать
для всех
больших некоторого
.
.
Для проверки достаточно положить
. Тогда
для
.
История
Обозначение «„O“ большое» введено немецким математиком
Паулем Бахманом
во втором томе его книги «Analytische Zahlentheorie» (Аналитическая теория чисел), вышедшем в 1894 году. Обозначение «„о“ малое» впервые использовано другим немецким математиком,
Эдмундом Ландау
в 1909 году; с работами последнего связана и популяризация обоих обозначений, в связи с чем их также называют
символами Ландау
. Обозначение пошло от немецкого слова «Ordnung» (порядок)
.