«О большое» (нотация)

«${\displaystyle O}$ большо́е», обозначение для функции, ограниченной относительно другой функции в окрестности некоторой точки. Пусть функции ${\displaystyle f(x)}$ и ${\displaystyle g(x)}$ заданы на множестве ${\displaystyle X\subset \mathbb {R} }$, а ${\displaystyle x_{0}}$ – предельная точка этого множества, которая может как принадлежать, так и не принадлежать множеству ${\displaystyle X}$, не исключая и случая бесконечно удалённой точки (если ${\displaystyle X}$ – неограниченное множество). Если существуют окрестность ${\displaystyle U}$ точки ${\displaystyle x_{0}}$ и постоянная ${\displaystyle c>0}$, такие, что для всех ${\displaystyle x\in X\cap U}$ выполняется неравенство ${\displaystyle \mid f(x)\mid \leq c\mid g(x)\mid }$, то пишут ${\displaystyle f(x)=O(g(x))}$ при ${\displaystyle x\to x_{0}}$ (Кудрявцев. 2005^[1]). Приведённое определение непосредственно обобщается на случай подмножеств в пространствах ${\displaystyle \mathbb {R} ^{n}}$ и ${\displaystyle \mathbb {C} ^{n}}$, как и в произвольных топологических пространствах. Обозначение «${\displaystyle O}$ большое» введено Паулем Бахманом (Bachmann. 1984^[2]) и Э. Ландау (Landau. 1909^[3]) и получило широкое распространение в математике и смежных науках.

В частности, в программировании обозначение «${\displaystyle O}$ большое» широко используется для оценки времени выполнения (временно́й сложности, асимптотики, асимптотической сложности) алгоритма. При оценке сложности учитываются только наиболее быстро растущие с увеличением ${\displaystyle n}$ – длины обрабатываемых исходных данных – слагаемые, которые дают вклад в увеличение времени выполнения (например, в связи с увеличением количества арифметических операций, которые выполняет программа или её часть, реализующие данный алгоритм). В рамках данного определения обозначения «${\displaystyle O}$ большое» такой подход соответствует пониманию сложности алгоритма как функции от ${\displaystyle n}$.

Например, если время выполнения пропорционально ${\displaystyle 5n^{3}+2n}$ (где ${\displaystyle n}$ – длина обрабатываемых исходных данных), то говорят, что сложность (асимптотика) алгоритма равна ${\displaystyle O(n^{3})}$. ${\displaystyle O(n)}$ обозначает время, прямо пропорциональное длине обрабатываемых исходных данных, а ${\displaystyle O(1)}$ – время, независимое от длины исходных данных.

Следует отметить, что обозначение «${\displaystyle O}$ большое» предоставляет для сложности алгоритма только верхнюю оценку: если время его выполнения пропорционально ${\displaystyle n^{2}}$, не будет математической ошибкой сообщить, что сложность алгоритма (как функция аргумента ${\displaystyle n}$) есть и ${\displaystyle O(n^{2})}$, и ${\displaystyle O(n^{3})}$ при ${\displaystyle n\to \infty }$.