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

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

14 Март 2012, 0:02

Пауль Бахман

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

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

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

Самым распространенным случаем является употребление этих обозначений при $x\to\infty$ . Мы сначала рассмотрим именно это.

Обозначение f(x)=O(g(x)) при $x\to\infty$ означает, что при достаточно больших функция f(x) удовлетворяет условию $|f(x)|\le c|g(x)|$ , где — некоторая положительная постоянная.

Точнее, f(x)=O(g(x)) при $x\to\infty$ , если существуют такие положительные постоянные и , что $|f(x)|\le c|g(x)|$ для всех , которые удовлетворяют условию x> m .

Тогда как запись через “О” большое означает ограниченность сверху, обозначение $\Omega$ означает ограниченность снизу. Опять же рассмотрим поведение функции на бесконечности. Говорят, что $f(x)=\Omega(g(x))$ при $x\to \infty$ , если существуют такие положительные постоянные и , что $|f(x)|\ge c|g(x)|$ для любого x> m .

Обозначение $f(x)=\Theta(g(x))$ означает, что одновременно f(x)=O(g(x)) и $f(x)=\Omega(g(x))$ .

Осталось еще два обозначения: (греческая буква омикрон) и $\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$ и , что $|f(x)|\le c|g(x)|$ для всех , которые удовлетворяют условию $|x-a|<\delta$ .

$f(x)=\Omega(g(x))$ при $x\to a$ , если существуют такие положительные постоянные $\delta$ и , что $|f(x)|\ge c|g(x)|$ для всех , которые удовлетворяют условию $|x-a|<\delta$ .

f(x)=o(g(x)) при $x\to a$ если f(x)/g(x) при $x\to a$ стремится к .

$f(x)=\omega(g(x))$ при $x\to a$ если f(x)/g(x) при $x\to a$ стремится к бесконечности.

Часто можно видеть такие утверждения, как f(x)=O(g(x)) без явных ограничений. В этих случаях необходимо из контекста определять, какой предел подразумевается.

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

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

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

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

Обозначение $f(x)=\omega(g(x))$ не является распространенным ни в информатике, ни в математике.

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

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

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

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

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

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

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

Разделы

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

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

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

Твиттер