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

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

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

В частности:

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

Определения

[править | править код]

Пусть и  — две функции, определённые в некоторой проколотой окрестности точки , причём в этой окрестности не обращается в ноль. Говорят, что:

  • является «O» большим от при , если существует такая константа , что для всех из некоторой окрестности точки имеет место неравенство
    ;
  • является «o» малым от при , если для любого найдется такая проколотая окрестность точки , что для всех имеет место неравенство

Иначе говоря, в первом случае отношение в окрестности точки (то есть ограничено сверху), а во втором оно стремится к нулю при .

Обозначение

[править | править код]

Обычно выражение « является большим ( малым) от » записывается с помощью равенства (соответственно, ).

Это обозначение очень удобно, но требует некоторой осторожности при использовании (а потому в наиболее элементарных учебниках его могут избегать). Дело в том, что это не равенство в обычном смысле, а несимметричное отношение.

В частности, можно писать

(или ),

но выражения

(или )

бессмысленны.

Другой пример: при верно, что

но

.

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

,

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

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

или

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

и

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

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

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

[править | править код]

Для функций и при используются следующие обозначения:

Обозначение Интуитивное объяснение Определение
ограничена сверху функцией (с точностью до постоянного множителя) асимптотически
ограничена снизу функцией (с точностью до постоянного множителя) асимптотически
ограничена снизу и сверху функцией асимптотически
доминирует над асимптотически
доминирует над асимптотически
эквивалентна асимптотически

где  — проколотая окрестность точки .

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

[править | править код]

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

[править | править код]

Рефлексивность

[править | править код]

; ;

Симметричность

[править | править код]

Перестановочная симметрия

[править | править код]

и, как следствия,

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

[править | править код]
  • Если в правой части уравнения находится только асимптотическое обозначение (например ), то знак равенства обозначает принадлежность множеству ().
  • Если в уравнении асимптотические обозначения встречаются в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при x → 0 формула обозначает, что , где  — функция, о которой известно только то, что она принадлежит множеству . Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например,     — содержит только одну функцию из класса .
  • Если асимптотические обозначения встречаются в левой части уравнения, используют следующее правило:
    какие бы мы функции ни выбрали (в соответствии с предыдущим правилом) взамен асимптотических обозначений в левой части уравнения, можно выбрать функции вместо асимптотических обозначений (в соответствии с предыдущим правилом) в правой части так, что уравнение будет правильным.
    Например, запись обозначает, что для любой функции , существует некоторая функция такая, что выражение  — верно для всех .
  • Несколько таких уравнений могут быть объединены в цепочки. Каждое из уравнений в таком случае следует интерпретировать в соответствии с предыдущим правилом.
    Например: . Отметим, что такая интерпретация подразумевает выполнение соотношения .

Приведенная интерпретация подразумевает выполнение соотношения:

, где A, B, C — выражения, которые могут содержать асимптотические обозначения.

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

[править | править код]
  • при .
  • при (следует из формулы Стирлинга)
  • при .
При выполнено неравенство . Поэтому положим .
Отметим, что нельзя положить , так как и, следовательно, это значение при любой константе больше .
  • Функция при имеет степень роста .
Чтобы это показать, надо положить и . Можно, конечно, сказать, что имеет порядок , но это более слабое утверждение, чем то, что .
  • Докажем, что функция при не может иметь порядок .
Предположим, что существуют константы и такие, что для всех выполняется неравенство .
Тогда для всех . Но принимает любое, как угодно большое, значение при достаточно большом , поэтому не существует такой константы , которая могла бы мажорировать для всех больших некоторого .
  • .
Для проверки достаточно положить . Тогда для .

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

Примечания

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