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

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

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

В частности:

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

Определения

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

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

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

Обозначение

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

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

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

(или ),

но выражения

(или )

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

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

но

.

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

,

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

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

или

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

и

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

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

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

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

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

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

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

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

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

; ;

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

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

Другие

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

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

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

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

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

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

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

История

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

См. также

Примечания

  1. Шведов И. А. Компактный курс математического анализа. Часть 1. Функции одной переменной. — Новосибирск, 2003. — С. 43.
  2. D.E. Knuth. (англ.) : 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. .
  • Кормен, Т. , Лейзерсон, Ч. , Ривест, Р. , Штайн, К. Глава 3. Рост функций // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М. : Вильямс, 2005. — С. 87—108. — ISBN 5-8459-0857-4 .
  • Бугров, Никольский. Высшая математика, том 2.
  • Dionysis Zindros. (2012). Дата обращения: 11 октября 2013. 10 октября 2013 года.
Источник —

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