«O» большое и «o» малое ( O O и o o) — математические обозначения для сравнения асимптотического поведения (асимптотики) функций. Используются в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также в информатике и теории алгоритмов. Под асимптотикой понимается характер изменения функции при стремлении её аргумента к определённой точке.
o ( f ) o(f), «о малое от f f» обозначает «бесконечно малое относительно f f»[1], пренебрежимо малую величину при рассмотрении f f. Смысл термина «О большое» зависит от его области применения, но всегда O ( f ) O(f) растёт не быстрее, чем f f (точные определения приведены ниже).
В частности:
фраза «сложность алгоритма есть O ( f ( n ) ) O(f(n))» означает, что с увеличением параметра n n, характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем f ( n ) f(n) умноженная на некоторую константу;
фраза «функция f ( x ) f(x) является „о“ малым от функции g ( x ) g(x) в окрестности точки p p» означает, что с приближением x x к p p f ( x ) f(x) уменьшается быстрее, чем g ( x ) g(x) (отношение | f ( x ) | / | g ( x ) | \left |f(x)\right |/\left |g(x)\right | стремится к нулю).
так что «менее больших» — это словесное выражение «O» большое )))
