O-большое и o-малое

O-большое и o-малое — математические обозначения для сравнения асимптотического поведения функций.

Эти обозначения часто используют в математическом анализе и при оценке сложности алгоритма. Фраза «сложность алгоритма o(n!)» означает, что время вычислений (или общее количество операций) для алгоритма является o-малым от факториала числа данных, с которыми работает алгоритм.

Определения

Пусть

f(x)

g(x)

– две положительные вещественнозначные функции. Говорят что

$f$ является O-большим от $g$ при $x\to x_0$ , если отношение ${f(x)}/{g(x)}$ ограничено в некоторой окрестности $x_0$ .
$f$ является о-малым от $g$ при $x\to x_0$ , если отношение ${f(x)}/{g(x)}\to 0$ при $x\to x_0$ .

Обозначение

Часто выражение «

f

является O-большим (соответственно о-малым) от

g

при

x\to x_0

» записывается с помощью равенства

f(x)=O(g(x))

(соответственно

f(x)=o(g(x))

)

Это обозначение очень удобно, но не вполне правильно, оно является своего рода математическим слэнгом и в учебниках его стараются избегать. Дело в том что оно нарушает свойства равенства, например, можно писать

f(x)=O(g(x))

или

f(x)=o(g(x))

но выражения

O(g(x))=f(x)

o(g(x))=f(x)

не имеют никакого смысла.

Также,

O(x^2)=o(x)

при

x\to0

но

o(x)\,\not=\,O(x^2),

при

x\to0

Вместо знака равенства правильнее употреблять знаки принадлежности и включения,

x^2+x^3 \in O(x^2)

O(x^2)\subset o(x),

понимая под

O(g(x))

или

o(g(x))

множество всех функций являющимися O-большим или о-малым от $g$ при $x\to x_0$ .

Свойства

o(f ) ∈ O(f )
O(f ) + O(f ) ∈ O(f )
o(f ) + o(f ) ∈ o(f )
O(f ) O(g ) ∈ O(fg )
o(f ) o(g ) ∈ o(fg )
O(O(f )) ∈ O(f )
o(o(f )), o(O(f )), O(o(f ))∈ o(f )

Примеры использования

$e^x\in 1+x+x^2/2+O(x^3)$ при $x\to 0$
$n!\in O\left((n/e)^{n+1/2}\right)$ при $n\to \infty$

Математические обозначения | Математический анализ

Gourt Home::Gourt :: O-большое и o-малое

Определения

Обозначение

Свойства

Примеры использования