“О” большое и связанные с ним обозначения
Здесь Вы найдете различные общепринятые обозначения (“О” большое и связанные с ним обозначения), введенные Паулем Бахманом и Эдмундом Ландау.
Бесконечные пределы
Самым распространенным случаем является употребление этих обозначений при . Мы сначала рассмотрим именно это.
Обозначение при
означает, что при достаточно больших
функция
удовлетворяет условию
, где
— некоторая положительная постоянная.
Точнее, при
, если существуют такие положительные постоянные
и
, что
для всех
, которые удовлетворяют условию
.
Тогда как запись через “О” большое означает ограниченность сверху, обозначение означает ограниченность снизу. Опять же рассмотрим поведение функции
на бесконечности. Говорят, что
при
, если существуют такие положительные постоянные
и
, что
для любого
.
Обозначение означает, что одновременно
и
.
Осталось еще два обозначения: (греческая буква омикрон) и
(строчная греческая буква омега). Обозначение омикрон также называют “о” малым.
Говорят, что , если при
частное
стремится к нулю.
Говорят также, что , если это частное стремится к бесконечности.
Конечные пределы
Все приведенные выше идеи остаются практически теми же для конечных пределов, хотя технические детали определения и отличаются.
при
, если существуют такие положительные постоянные
и
, что
для всех
, которые удовлетворяют условию
.
при
, если существуют такие положительные постоянные
и
, что
для всех
, которые удовлетворяют условию
.
при
, если
при
стремится к
.
при
, если
при
стремится к бесконечности.
Часто можно видеть такие утверждения, как без явных ограничений. В этих случаях необходимо из контекста определять, какой предел подразумевается.
Использование
Обозначение “O” большое является общепринятым и в математике, и в информатике. Однако некоторые другие обозначения являются общепринятыми только в одной из этих областей.
В информатике акцент делается почти всегда на поведение алгоритма с ростом размерности задачи , поэтому неявно считается, что
стремится к бесконечности. Обозначения
и
гораздо чаще используются в информатике, чем в математике. Обозначение “о” малое в информатике используется редко.
В математике обозначение “О” большое является общим для бесконечных и конечных пределов. Обозначение “о” малое следующее по популярности. Обозначения и
являются редкими.
Обозначение не является распространенным ни в информатике, ни в математике.
Источники: http://www.johndcook.com/asymptotic_notation.html
http://ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое
Оставьте свой отзыв