«O» большое и «o» малое: различия между версиями
[отпатрулированная версия] | [отпатрулированная версия] |
Lesless (обсуждение | вклад) м откат правок 46.138.79.51 (обс.) к версии Tosha Метка: откат |
Niklem (обсуждение | вклад) м оформление |
||
Строка 5: | Строка 5: | ||
В частности: |
В частности: |
||
* фраза «[[Вычислительная сложность|сложность алгоритма]] есть <math>O(f(n))</math>» означает, что с увеличением параметра <math>n</math>, характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем <math>f(n)</math> умноженная на некоторую константу; |
* фраза «[[Вычислительная сложность|сложность алгоритма]] есть <math>O(f(n))</math>» означает, что с увеличением параметра <math>n</math>, характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем <math>f(n)</math>, умноженная на некоторую константу; |
||
* фраза «функция <math>f(x)</math> является „о“ малым от функции <math>g(x)</math> в окрестности точки <math>p</math>» означает, что с приближением <math>x</math> к <math>p</math> <math>f(x)</math> уменьшается быстрее, чем <math>g(x)</math> (отношение <math>\left |f(x)\right |/\left |g(x)\right |</math> стремится к нулю). |
* фраза «функция <math>f(x)</math> является „о“ малым от функции <math>g(x)</math> в окрестности точки <math>p</math>» означает, что с приближением <math>x</math> к <math>p</math> <math>f(x)</math> уменьшается быстрее, чем <math>g(x)</math> (отношение <math>\left |f(x)\right |/\left |g(x)\right |</math> стремится к нулю). |
||
== Определения == |
== Определения == |
||
Пусть <math>f(x)</math> и <math>g(x)</math> — две функции, |
Пусть <math>f(x)</math> и <math>g(x)</math> — две функции, определённые в некоторой [[Окрестность#Проколотая окрестность|проколотой окрестности]] точки <math>x_0</math>, причём в этой окрестности <math>g</math> не обращается в ноль. Говорят, что: |
||
Говорят, что: |
|||
* <math>f</math> является «O» большим от <math>g</math> при <math>x\to x_0</math>, если существует такая константа <math>C>0</math>, что для всех <math>x</math> из некоторой окрестности точки <math>x_0</math> имеет место неравенство |
* <math>f</math> является «O» большим от <math>g</math> при <math>x\to x_0</math>, если существует такая константа <math>C>0</math>, что для всех <math>x</math> из некоторой окрестности точки <math>x_0</math> имеет место неравенство |
||
*: <math>|f(x)| \leqslant C |g(x)|</math>; |
*: <math>|f(x)| \leqslant C |g(x)|</math>; |
||
Строка 19: | Строка 18: | ||
== Обозначение == |
== Обозначение == |
||
Обычно выражение «<math>f</math> является <math>O</math> большим (<math>o</math> малым) от <math>g</math>» |
Обычно выражение «<math>f</math> является <math>O</math> большим (<math>o</math> малым) от <math>g</math>» записывается с помощью равенства <math>f(x) = O(g(x))</math> (соответственно, <math>f(x) = o(g(x))</math>). |
||
записывается с помощью равенства <math>f(x) = O(g(x))</math> (соответственно, <math>f(x) = o(g(x))</math>). |
|||
Это обозначение очень удобно, но требует некоторой осторожности при использовании (а потому в наиболее элементарных учебниках его могут избегать). Дело в том, что это не равенство в обычном смысле, а несимметричное [[Бинарное отношение|отношение]]. |
Это обозначение очень удобно, но требует некоторой осторожности при использовании (а потому в наиболее элементарных учебниках его могут избегать). Дело в том, что это не равенство в обычном смысле, а несимметричное [[Бинарное отношение|отношение]]. |
||
Строка 160: | Строка 158: | ||
== История == |
== История == |
||
Обозначение «„O“ большое» введено немецким математиком [[Бахман, Пауль|Паулем Бахманом]] во втором томе его книги «Analytische Zahlentheorie» (Аналитическая теория чисел), вышедшем в |
Обозначение «„O“ большое» введено немецким математиком [[Бахман, Пауль|Паулем Бахманом]] во втором томе его книги «Analytische Zahlentheorie» (Аналитическая теория чисел), вышедшем в 1894 году. Обозначение «„о“ малое» впервые использовано другим немецким математиком, [[Ландау, Эдмунд Георг Герман|Эдмундом Ландау]] в 1909 году; с работами последнего связана и популяризация обоих обозначений, в связи с чем их также называют '''символами Ландау'''. Обозначение пошло от немецкого слова «Ordnung» (порядок)<ref>{{Статья|автор = D.E. Knuth|заглавие = Big Omicron and big Omega and big Theta|тип = Article|год = 1976|номер = 2|том = 8|страницы = 18—24|издательство = ACM Sigact News|ссылка = http://www.phil.uu.nl/datastructuren/09-10/knuth_big_omicron.pdf|язык = English|место = |издание = |archivedate = 2016-08-15|archiveurl = https://web.archive.org/web/20160815141848/http://www.phil.uu.nl/datastructuren/09-10/knuth_big_omicron.pdf}}</ref>. |
||
== См. также == |
== См. также == |
||
* [[Бесконечно малая |
* [[Бесконечно малая и бесконечно большая]] |
||
== Примечания == |
== Примечания == |
Версия от 18:28, 10 февраля 2023
«O» большое и «o» малое ( и ) — математические обозначения для сравнения асимптотического поведения (асимптотики) функций. Используются в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также в информатике и теории алгоритмов. Под асимптотикой понимается характер изменения функции при стремлении её аргумента к определённой точке.
, «о малое от » обозначает «бесконечно малое относительно »[1], пренебрежимо малую величину при рассмотрении . Смысл термина «О большое» зависит от его области применения, но всегда растёт не быстрее, чем (точные определения приведены ниже).
В частности:
- фраза «сложность алгоритма есть » означает, что с увеличением параметра , характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем , умноженная на некоторую константу;
- фраза «функция является „о“ малым от функции в окрестности точки » означает, что с приближением к уменьшается быстрее, чем (отношение стремится к нулю).
Определения
Пусть и — две функции, определённые в некоторой проколотой окрестности точки , причём в этой окрестности не обращается в ноль. Говорят, что:
- является «O» большим от при , если существует такая константа , что для всех из некоторой окрестности точки имеет место неравенство
- ;
- является «о» малым от при , если для любого найдется такая проколотая окрестность точки , что для всех имеет место неравенство
Иначе говоря, в первом случае отношение в окрестности точки (то есть ограничено сверху), а во втором оно стремится к нулю при .
Обозначение
Обычно выражение « является большим ( малым) от » записывается с помощью равенства (соответственно, ).
Это обозначение очень удобно, но требует некоторой осторожности при использовании (а потому в наиболее элементарных учебниках его могут избегать). Дело в том, что это не равенство в обычном смысле, а несимметричное отношение.
В частности, можно писать
- (или ),
но выражения
- (или )
бессмысленны.
Другой пример: при верно, что
но
- .
При любом x верно
- ,
то есть бесконечно малая величина является ограниченной, но
Вместо знака равенства методологически правильнее было бы употреблять знаки принадлежности и включения, понимая и как обозначения для множеств функций, то есть, используя запись в форме
или
вместо, соответственно,
и
Однако на практике такая запись встречается крайне редко, в основном, в простейших случаях.
При использовании данных обозначений должно быть явно оговорено (или очевидно из контекста), о каких окрестностях (одно- или двусторонних; содержащих целые, вещественные, комплексные или другие числа) и о каких допустимых множествах функций идет речь (поскольку такие же обозначения употребляются и применительно к функциям многих переменных, к функциям комплексной переменной, к матрицам и др.).
Другие подобные обозначения
Для функций и при используются следующие обозначения:
Обозначение | Интуитивное объяснение | Определение |
---|---|---|
ограничена сверху функцией (с точностью до постоянного множителя) асимптотически | ||
ограничена снизу функцией (с точностью до постоянного множителя) асимптотически | ||
ограничена снизу и сверху функцией асимптотически | ||
доминирует над асимптотически | ||
доминирует над асимптотически | ||
эквивалентна асимптотически |
где — проколотая окрестность точки .
Основные свойства
Транзитивность
Рефлексивность
; ;
Симметричность
Перестановочная симметрия
Другие
- и, как следствия,
Асимптотические обозначения в уравнениях
- Если в правой части уравнения находится только асимптотическое обозначение (например ), то знак равенства обозначает принадлежность множеству ().
- Если в уравнении асимптотические обозначения встречаются в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при x → 0 формула обозначает, что , где — функция, о которой известно только то, что она принадлежит множеству . Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например, — содержит только одну функцию из класса .
- Если асимптотические обозначения встречаются в левой части уравнения, используют следующее правило:
какие бы мы функции ни выбрали (в соответствии с предыдущим правилом) взамен асимптотических обозначений в левой части уравнения, можно выбрать функции вместо асимптотических обозначений (в соответствии с предыдущим правилом) в правой части так, что уравнение будет правильным.
Например, запись обозначает, что для любой функции , существует некоторая функция такая, что выражение — верно для всех . - Несколько таких уравнений могут быть объединены в цепочки. Каждое из уравнений в таком случае следует интерпретировать в соответствии с предыдущим правилом.
Например: . Отметим, что такая интерпретация подразумевает выполнение соотношения .
Приведенная интерпретация подразумевает выполнение соотношения:
- , где A, B, C — выражения, которые могут содержать асимптотические обозначения.
Примеры использования
- при .
- при (следует из формулы Стирлинга)
- при .
- При выполнено неравенство . Поэтому положим .
- Отметим, что нельзя положить , так как и, следовательно, это значение при любой константе больше .
- Функция при имеет степень роста .
- Чтобы это показать, надо положить и . Можно, конечно, сказать, что имеет порядок , но это более слабое утверждение, чем то, что .
- Докажем, что функция при не может иметь порядок .
- Предположим, что существуют константы и такие, что для всех выполняется неравенство .
- Тогда для всех . Но принимает любое, как угодно большое, значение при достаточно большом , поэтому не существует такой константы , которая могла бы мажорировать для всех больших некоторого .
- .
- Для проверки достаточно положить . Тогда для .
История
Обозначение «„O“ большое» введено немецким математиком Паулем Бахманом во втором томе его книги «Analytische Zahlentheorie» (Аналитическая теория чисел), вышедшем в 1894 году. Обозначение «„о“ малое» впервые использовано другим немецким математиком, Эдмундом Ландау в 1909 году; с работами последнего связана и популяризация обоих обозначений, в связи с чем их также называют символами Ландау. Обозначение пошло от немецкого слова «Ordnung» (порядок)[2].
См. также
Примечания
- ↑ Шведов И. А. Компактный курс математического анализа. Часть 1. Функции одной переменной. — Новосибирск, 2003. — С. 43.
- ↑ 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 года.