“О” большое и связанные с ним обозначения

Пауль Бахман

Эдмунд Ландау

Здесь Вы найдете различные общепринятые обозначения (“О” большое и связанные с ним обозначения), введенные Паулем Бахманом и Эдмундом Ландау.

Бесконечные пределы

Самым распространенным случаем является употребление этих обозначений при

    \[x\to\infty\]

. Мы сначала рассмотрим именно это.

Обозначение

    \[f(x)=O(g(x))\]

при

    \[x\to\infty\]

означает, что при достаточно больших

    \[x\]

функция

    \[f(x)\]

удовлетворяет условию

    \[|f(x)|\le c|g(x)|\]

, где

    \[c\]

— некоторая положительная постоянная.

Точнее,

    \[f(x)=O(g(x))\]

при

    \[x\to\infty\]

, если существуют такие положительные постоянные

    \[m\]

и

    \[c\]

, что

    \[|f(x)|\le c|g(x)|\]

для всех

    \[x\]

, которые удовлетворяют условию

    \[x> m\]

.

Тогда как запись через “О” большое означает ограниченность сверху, обозначение

    \[\Omega\]

означает ограниченность снизу. Опять же рассмотрим поведение функции

    \[f\]

на бесконечности. Говорят, что

    \[f(x)=\Omega(g(x))\]

при

    \[x\to \infty\]

, если существуют такие положительные постоянные

    \[m\]

и

    \[c\]

, что

    \[|f(x)|\ge c|g(x)|\]

для любого

    \[x> m\]

.

Обозначение

    \[f(x)=\Theta(g(x))\]

означает, что одновременно

    \[f(x)=O(g(x))\]

и

    \[f(x)=\Omega(g(x))\]

.

Осталось еще два обозначения:

    \[o\]

(греческая буква омикрон) и

    \[\omega\]

(строчная греческая буква омега). Обозначение омикрон также называют “о” малым.

Говорят, что

    \[f(x)=o(g(x))\]

, если при

    \[x\to\infty\]

частное

    \[f(x)/g(x)\]

стремится к нулю.

Говорят также, что

    \[f(x)=\omega(g(x))\]

, если это частное стремится к бесконечности.

Конечные пределы

Все приведенные выше идеи остаются практически теми же для конечных пределов, хотя технические детали определения и отличаются.

    \[f(x)=O(g(x))\]

при

    \[x\to a\]

, если существуют такие положительные постоянные

    \[\delta\]

и

    \[c\]

, что

    \[|f(x)|\le c|g(x)|\]

для всех

    \[x\]

, которые удовлетворяют условию

    \[|x-a|<\delta\]

.

    \[f(x)=\Omega(g(x))\]

при

    \[x\to a\]

, если существуют такие положительные постоянные

    \[\delta\]

и

    \[c\]

, что

    \[|f(x)|\ge c|g(x)|\]

для всех

    \[x\]

, которые удовлетворяют условию

    \[|x-a|<\delta\]

.

    \[f(x)=o(g(x))\]

при

    \[x\to a\]

если

    \[f(x)/g(x)\]

при

    \[x\to a\]

стремится к

    \[0\]

.

    \[f(x)=\omega(g(x))\]

при

    \[x\to a\]

если

    \[f(x)/g(x)\]

при

    \[x\to a\]

стремится к бесконечности.

Часто можно видеть такие утверждения, как

    \[f(x)=O(g(x))\]

без явных ограничений. В этих случаях необходимо из контекста определять, какой предел подразумевается.

Использование

Обозначение “O” большое является общепринятым и в математике, и в информатике. Однако некоторые другие обозначения являются общепринятыми только в одной из этих областей.

В информатике акцент делается почти всегда на поведение алгоритма с ростом размерности задачи

    \[n\]

, поэтому неявно считается, что

    \[n\]

стремится к бесконечности. Обозначения

    \[\Omega\]

и

    \[\Theta\]

гораздо чаще используются в информатике, чем в математике. Обозначение “о” малое в информатике используется редко.

В математике обозначение “О” большое является общим для бесконечных и конечных пределов. Обозначение “о” малое следующее по популярности. Обозначения

    \[\Omega\]

и

    \[\Theta\]

являются редкими.

Обозначение

    \[f(x)=\omega(g(x))\]

не является распространенным ни в информатике, ни в математике.

Источники: http://www.johndcook.com/asymptotic_notation.html

http://ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое

Оставьте свой отзыв

Добавить изображение