«O» большое и «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 года.