О-большое и связанные с ним обозначения | Математика, которая мне нравится

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

14 Март 2012, 0:02

Пауль Бахман

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

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

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

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

$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»_малое

Теги: мат. анализ, обозначения
Рубрика: Статьи по математике | Отзывы (RSS) | Трекбек

Математика, которая мне нравится

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

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

Навигация по сайту

Разделы

Новые комментарии

Хороший книжный магазин

Подписка на обновления сайта

Твиттер