Обозначение большого O

Нотация Big O — это математическая нотация, описывающая предельное поведение функции, когда аргумент стремится к определенному значению или бесконечности. Большой O является членом семейства обозначений , изобретенных Полом Бахманом , ^[1] Эдмундом Ландау , ^[2] и другими, которые в совокупности называются обозначениями Бахмана-Ландау или асимптотическими обозначениями .

В информатике большая нотация O используется для классификации алгоритмов в зависимости от того, как растут их требования к времени выполнения или пространству по мере увеличения размера входных данных. ^[3] В аналитической теории чисел нотация большого O часто используется для выражения границы разницы между арифметической функцией и более понятной аппроксимацией; известный пример такой разницы — остаточный член в теореме о простых числах . Обозначение Big O также используется во многих других областях для получения аналогичных оценок.

Нотация Big O характеризует функции в соответствии с темпами их роста: разные функции с одинаковой скоростью роста могут быть представлены с использованием одной и той же нотации O. Буква O используется потому, что скорость роста функции также называется порядком функции . Описание функции в терминах нотации большого O обычно дает только верхнюю границу скорости роста функции.

С обозначением большого O связано несколько родственных обозначений, использующих символы o , Ω, ω и Θ для описания других видов границ асимптотических скоростей роста.

Пусть f — действительная или комплекснозначная функция, а g — вещественнозначная функция. Пусть обе функции определены на некотором неограниченном подмножестве положительных действительных чисел и строго положительны для всех достаточно больших значений x . ^[4] Один пишет${\ Displaystyle г (х)}$

если абсолютное значение не больше положительного постоянного кратного для всех достаточно больших значений x . То есть, если существуют положительное действительное число M и действительное число x ₀ такие, что${\ Displaystyle е (х)}$${\ Displaystyle г (х)}$${\ Displaystyle е (х) = О {\ bigl (} г (х) {\ bigr)}}$

Пример нотации Big O: существуют (например, ) и (например, ) такие, что всякий раз , когда .${\ displaystyle {\ color {red} f (x)} \ in O {\ color {blue} (g (x))}}$${\ Displaystyle М> 0}$${\ Displaystyle М = 1}$${\ Displaystyle х_ {0}}$${\ Displaystyle х_ {0} = 5}$${\ displaystyle {\ color {red} f (x)} \ leq {\ color {blue} Mg (x)}}$${\ Displaystyle х \ geq х_ {0}}$

Графики функций, обычно используемые при анализе алгоритмов, показывающие количество операций N в зависимости от размера входных данных n для каждой функции .