Распечатать запись Распечатать запись

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

Пауль Бахман

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

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

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

Самым распространенным случаем является употребление этих обозначений при 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»_малое

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

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