«O» большое и «o» малое | это... Что такое «O» большое и «o» малое? (original) (raw)
У этого термина существуют и другие значения, см. O (значения).
«O» большое и «o» малое ( и
) — математические обозначения для сравнения асимптотического поведения функций. Используются в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также в информатике и теории алгоритмов.
, «о малое от
» обозначает «бесконечно малое относительно
»[1], пренебрежимо малую величину при рассмотрении
. Смысл термина «О большое» зависит от его области применения, но всегда
растёт не быстрее, чем
, «O большое от
» (точные определения приведены ниже).
В частности:
Содержание
- 1 Определения
- 2 Обозначение
- 3 Другие подобные обозначения
- 4 Основные свойства
- 5 Асимптотические обозначения в уравнениях
- 6 Примеры использования
- 7 История
- 8 См. также
- 9 Примечания
- 10 Литература
Определения
Пусть и
— две функции, определенные в некоторой проколотой окрестности точки
, причем в этой окрестности
не обращается в ноль. Говорят, что:
Иначе говоря, в первом случае отношение в окрестности точки
ограничено сверху, а во втором оно стремится к нулю при
.
Обозначение
Обычно выражение «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_²)
или
вместо, соответственно,
_x_² + _x_³ = O(_x_²)
и
Однако на практике такая запись встречается крайне редко, в основном, в простейших случаях.
При использовании данных обозначений должно быть явно оговорено (или очевидно из контекста), о каких окрестностях (одно- или двусторонних; содержащих целые, вещественные или комплексные числа и т. п.) и о каких допустимых множествах функций идет речь (поскольку такие же обозначения употребляются и применительно к функциям многих переменных, к функциям комплексной переменной, к матрицам и др.).
Другие подобные обозначения
Для функций f(n) и g(n) при _n → n_0 используются следующие обозначения:
Обозначение | Интуитивное объяснение | Определение | |
---|---|---|---|
![]() |
![]() ![]() |
![\exists (C>0), U : \forall (n \in U) ; |f(n) | \leq C |
![]() |
![]() ![]() |
![\exists (C>0), U : \forall (n \in U) ; C|g(n) | \leq |
![]() |
![]() ![]() |
![\exists (C>0), (C'>0), U : \forall (n \in U) ; C|g(n) | \leq |
![]() |
![]() ![]() |
![\forall (C>0) ,\exists U : \forall(n \in U) ; |f(n) | < C |
![]() |
![]() ![]() |
![\forall (C>0) ,\exists U : \forall(n \in U) ; C|g(n) | < |
![]() |
![]() ![]() |
![]() |
где U — проколотая окрестность точки _n_0.
Основные свойства
Транзитивность
Рефлексивность
Симметричность
Перестановочная симметрия
Другие
- 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 формула
обозначает, что
, где
— функция, о которой известно только то, что она принадлежит множеству
. Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например,
— содержит только одну функцию из класса
.
- Если асимптотические обозначения встречаются в левой части уравнения, используют следующее правило:
какие бы мы функции не выбрали (в соответствии с предыдущим правилом) взамен асимптотических обозначений в левой части уравнения, можно выбрать функции вместо асимптотических обозначений (в соответствии с предыдущим правилом) в правой части так, что уравнение будет правильным.
Например, записьобозначает, что для любой функции
, существует некоторая функция
такая, что выражение
— верно для всех
.
- Несколько таких уравнений могут быть объединены в цепочки. Каждое из уравнений в таком случае следует интерпретировать в соответствии с предыдущим правилом.
Например:. Отметим, что такая интерпретация подразумевает выполнение соотношения
.
Приведенная интерпретация подразумевает выполнение соотношения:
, где A, B, C — выражения, которые могут содержать асимптотические обозначения.
Примеры использования
- ex = 1 + x + _x_²/2 + O(_x_³) при x → 0.
- n! = O((n/e)n+1/2) при n → ∞.
при n → ∞.
Доказательство:
Если положить и
, то для _n_≥1 будет выполняться неравенство
. Отметим, что нельзя положить
, так как
и, следовательно, это значение при любой константе
больше
.
- Функция
при n → ∞ имеет степень роста
. Чтобы это показать, надо положить
и
. Можно, конечно, сказать, что
имеет порядок
, но это более слабое утверждение, чем то, что
имеет порядок роста
.
- Докажем, что функция
при n → ∞ не может иметь порядок
. Предположим, что существуют константы
и
такие, что для всех n ≥ n_0 выполняется неравенство 3_n ≤ _c_2n. Тогда c ≥ (3/2)n для всех n ≥ _n_0. Но (3/2)n принимает любое, как угодно большое, значение при достаточно большом
, поэтому не существует такой константы
, которая могла бы мажорировать (3/2)n для всех n больших некоторого _n_0.
есть
при n → ∞. Для проверки достаточно положить
. Тогда
для
.
История
Обозначение «„O“ большое» введено немецким математиком Паулем Бахманом (англ.) во втором томе его книги «Analytische Zahlentheorie» (Аналитическая теория чисел), вышедшем в 1894 году. Обозначение «„о“ малое» впервые использовано другим немецким математиком, Эдмундом Ландау в 1909 году; с работами последнего связана и популяризация обоих обозначений, в связи с чем их также называют символами Ландау. Обозначение пошло от немецкого слова «Ordnung» (порядок).
См. также
Примечания
- ↑ И. А. Шведов. Компактный курс математического анализа. Часть 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.