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

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

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) | Трекбек

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

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

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

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

Разделы

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

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

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

Твиттер