Обозначение Big O - Big O notation

Подходящее приближение
Концепции
Порядок аппроксимации Масштабный анализ  · Обозначение Big O Подгонка кривой  · Ложная точность Значимые числа
Прочие основы
Аппроксимация  · Ошибка обобщения Полином Тейлора Научное моделирование
v т е

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

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

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

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

Обозначение Big O также используется во многих других областях для получения аналогичных оценок.

Формальное определение

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

${\ Displaystyle е (х) = О {\ bigl (} \, г (х) \, {\ bigr)} \ quad {\ text {as}} х \ к \ infty}$

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

${\ Displaystyle | е (х) | \ leq M \, g (x) \ quad {\ text {для всех}} x \ geq x_ {0}.}$

Во многих контекстах предположение о том, что нас интересует скорость роста, когда переменная x стремится к бесконечности, не указывается, и проще записать, что

${\ displaystyle f (x) = O {\ bigl (} \, g (x) \, {\ bigr)}.}$

Обозначения также могут использоваться для описания поведения f вблизи некоторого действительного числа a (часто a = 0 ): мы говорим

${\ Displaystyle е (х) = О {\ bigl (} \, г (х) \, {\ bigr)} \ quad {\ text {as}} х \ к а}$

если существуют положительные числа и M такие, что для всех x с , ${\ displaystyle \ delta}$${\ displaystyle 0 <| xa | <\ delta}$

${\ Displaystyle | е (х) | \; \ leq \; M \, g (x).}$

Поскольку g ( x ) выбирается ненулевым для значений x, достаточно близких к a , оба этих определения могут быть объединены с использованием верхнего предела :

${\ Displaystyle е (х) = О {\ bigl (} \, г (х) \, {\ bigr)} \ quad {\ text {as}} х \ к а}$

если

${\ displaystyle \ limsup _ {x \ to a} {\ frac {\ left | f (x) \ right |} {g (x)}} <\ infty.}$

пример

В типичном использовании обозначение O является асимптотическим, то есть относится к очень большим x . В этом случае вклад терминов, которые растут «наиболее быстро», в конечном итоге сделает другие неуместными. В результате могут применяться следующие правила упрощения:

• Если f ( x ) является суммой нескольких членов, если есть одно с наибольшей скоростью роста, его можно оставить, а все остальные опустить.
• Если f ( x ) является произведением нескольких факторов, любые константы (члены в произведении, которые не зависят от x ) могут быть опущены.

Например, пусть f ( x ) = 6 x ⁴ - 2 x ³ + 5 , и предположим, что мы хотим упростить эту функцию, используя обозначение O , чтобы описать скорость ее роста по мере приближения x к бесконечности. Эта функция представляет собой сумму трех членов: 6 x ⁴ , −2 x ³ и 5 . Из этих трех членов один с наибольшей скоростью роста имеет наибольший показатель степени как функцию от x , а именно 6 x ⁴ . Теперь можно применить второе правило: 6 x ⁴ - это произведение 6 и x ^4, в котором первый множитель не зависит от x . Отсутствие этого фактора приводит к упрощенной форме x ⁴ . Таким образом, мы говорим, что f ( x ) - это «большой O» x ⁴ . Математически мы можем записать f ( x ) = O ( x ⁴ ) . Этот расчет можно подтвердить, используя формальное определение: пусть f ( x ) = 6 x ⁴ - 2 x ³ + 5 и g ( x ) = x ⁴ . Применяя формальное определение сверху, утверждение, что f ( x ) = O ( x ⁴ ) , эквивалентно его разложению,

${\ Displaystyle | е (х) | \ leq \; Mx ^ {4}}$

для некоторого подходящего выбора x ₀ и M и для всех x > x ₀ . Чтобы доказать это, пусть x ₀ = 1 и M = 13 . Тогда для всех x > x ₀ :

${\ displaystyle {\ begin {align} | 6x ^ {4} -2x ^ {3} +5 | & \ leq 6x ^ {4} + | 2x ^ {3} | +5 \\ & \ leq 6x ^ { 4} + 2x ^ {4} + 5x ^ {4} \\ & = 13x ^ {4} \ end {align}}}$

так

${\ displaystyle | 6x ^ {4} -2x ^ {3} +5 | \ leq 13 \, x ^ {4}.}$

использование

Нотация Big O имеет две основные области применения:

• В математике он обычно используется для описания того, насколько точно конечный ряд приближается к данной функции , особенно в случае усеченного ряда Тейлора или асимптотического разложения.
• В информатике это полезно при анализе алгоритмов.

В обоих приложениях функция g ( x ), появляющаяся внутри O (...) , обычно выбирается как можно более простой, опуская постоянные множители и члены более низкого порядка.

Есть два формально близких, но заметно различных использования этой нотации:

• бесконечная асимптотика
• бесконечно малые асимптотики.

Однако это различие только в применении, а не в принципе - формальное определение «большого О» одинаково для обоих случаев, только с разными ограничениями для аргумента функции.

Бесконечная асимптотика

Обозначение Big O полезно при анализе алгоритмов на эффективность. Например, время (или количество шагов), необходимое для решения задачи размера n, может оказаться равным T ( n ) = 4 n ² - 2 n + 2 . В п растет большим, п ² термина будет доминировать, так что все остальные член можно пренебречь, например , когда п = 500 , термин 4 н ² составляет 1000 раз больше , как 2 н перспективы. Игнорирование последнего окажет незначительное влияние на значение выражения для большинства целей. Кроме того, коэффициенты становятся неактуальными при сравнении с любым другим порядком выражения, например, выражением, содержащим член n ³ или n ⁴ . Даже если T ( n ) = 1 000 000 n ² , если U ( n ) = n ³ , последнее всегда будет превышать первое, если n станет больше 1 000 000 ( T (1 000 000) = 1 000 000 ³ = U (1 000 000) ). Кроме того, количество шагов зависит от деталей модели машины, на которой работает алгоритм, но разные типы машин обычно различаются лишь на постоянный коэффициент количества шагов, необходимых для выполнения алгоритма. Таким образом, большая нотация O фиксирует то, что осталось: мы пишем либо

${\ Displaystyle \ T (п) = О (п ^ {2})}$

или

${\ Displaystyle Т (п) \ в О (п ^ {2})}$

и говорят, что алгоритм имеет временную сложность порядка n ² . Знак « = » не предназначен для выражения «равно» в его обычном математическом смысле, а скорее для более разговорного «есть», поэтому второе выражение иногда считается более точным (см. Обсуждение « Знак равенства » ниже), в то время как первый рассматривается некоторыми как злоупотребление обозначениями .

Бесконечно малые асимптотики

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

${\ displaystyle {\ begin {align} e ^ {x} & = 1 + x + {\ frac {x ^ {2}} {2!}} + {\ frac {x ^ {3}} {3!}} + {\ frac {x ^ {4}} {4!}} + \ dotsb & {\ text {для всех}} x \\ & = 1 + x + {\ frac {x ^ {2}} {2}} + O (x ^ {3}) & {\ text {as}} x \ to 0 \\ & = 1 + x + O (x ^ {2}) & {\ text {as}} x \ to 0 \ \\ конец {выровнен}}}$

Второе выражение (один с O ( х ³ )) означает абсолютное-значение ошибки е ^х - (1 + х + х ² /2) самый большие несколько раз постоянных | х ³ | когда x достаточно близко к 0.

Свойства

Если функцию f можно записать как конечную сумму других функций, то наиболее быстро растущая функция определяет порядок f ( n ) . Например,

${\ displaystyle f (n) = 9 \ log n + 5 (\ log n) ^ {4} + 3n ^ {2} + 2n ^ {3} = O (n ^ {3}) \ qquad {\ text { as}} n \ to \ infty.}$

В частности, если функция может быть ограничена полиномом от n , то по мере того, как n стремится к бесконечности , можно пренебречь членами более низкого порядка полинома. Наборы O ( n ^c ) и O ( c ⁿ ) очень разные. Если c больше единицы, то последнее растет намного быстрее. Функция, которая растет быстрее, чем n ^c для любого c , называется суперполиномиальной . Функция, которая растет медленнее, чем любая экспоненциальная функция вида c ⁿ , называется субэкспоненциальной . Для алгоритма может потребоваться время, которое является как суперполиномиальным, так и субэкспоненциальным; Примеры этого включают самые быстрые известные алгоритмы для целочисленной факторизации и функцию n ^{log n} .

Мы можем игнорировать любые степени n внутри логарифмов. Набор O (log n ) точно такой же, как O (log ( n ^c )) . Логарифмы различаются только постоянным множителем (поскольку log ( n ^c ) = c log n ), и, таким образом, большая нотация O игнорирует это. Точно так же бревна с разными постоянными основаниями эквивалентны. С другой стороны, экспоненты с разными основаниями не одного порядка. Например, 2 ⁿ и 3 ⁿ не одного порядка.

Изменение единиц измерения может или не может повлиять на порядок результирующего алгоритма. Изменение единиц эквивалентно умножению соответствующей переменной на константу, где бы она ни появлялась. Например, если алгоритм работает в порядке n ² , замена n на cn означает, что алгоритм работает в порядке c ² n ² , а нотация большого O игнорирует константу c ² . Это можно записать как c ² n ² = O ( n ² ) . Однако, если алгоритм работает в порядке 2 ⁿ , замена n на cn дает 2 ^cn = (2 ^c ) ⁿ . Это не эквивалентно 2 ⁿ в целом. Изменение переменных также может повлиять на порядок результирующего алгоритма. Например, если время выполнения алгоритма , является O ( п ) при измерении в терминах числа п из цифр входного числа х , то его время работы составляет O (журнал х ) при измерении , как функция от входного числа х сама , поскольку n = O (log x ) .

Товар

${\ displaystyle f_ {1} = O (g_ {1}) {\ text {and}} f_ {2} = O (g_ {2}) \, \ Rightarrow f_ {1} f_ {2} = O (g_ {1} g_ {2})}$

${\ Displaystyle е \ cdot O (g) = O (fg)}$

Сумма

${\ displaystyle f_ {1} = O (g_ {1}) {\ text {and}} f_ {2} = O (g_ {2}) \, \ Rightarrow f_ {1} + f_ {2} = O ( \ max (g_ {1}, g_ {2}))}$

Это подразумевает , что означает , что является выпуклым конусом . ${\ displaystyle f_ {1} = O (g) {\ text {and}} f_ {2} = O (g) \ Rightarrow f_ {1} + f_ {2} \ in O (g)}$${\ Displaystyle О (г)}$

Умножение на константу

Пусть k будет постоянным. Затем:

${\ Displaystyle \ О (| К | г) = О (г)}$если k ненулевое.

${\ Displaystyle f = O (g) \ Rightarrow kf = O (g).}$

Несколько переменных

Большой O (и маленький o, Ω и т. Д.) Также можно использовать с несколькими переменными. Чтобы формально определить большой O для нескольких переменных, предположим, что и - две функции, определенные на некотором подмножестве . Мы говорим ${\ displaystyle f}$${\ displaystyle g}$${\ Displaystyle \ mathbb {R} ^ {п}}$

${\ displaystyle f ({\ vec {x}}) {\ text {is}} O (g ({\ vec {x}})) \ quad {\ text {as}} {\ vec {x}} \ в \ infty}$

если и только если

${\ displaystyle \ exists \, M \, \ exists \, C> 0 ~ {\ text {такой, что для всех}} ~ {\ vec {x}} ~ {\ text {with}} ~ x_ {i} \ geq M ~ {\ text {для некоторых}} ~ i, | f ({\ vec {x}}) | \ leq C \, | g ({\ vec {x}}) | ~.}$

Эквивалентно условие, что для некоторых можно заменить условием , где, где обозначает чебышевскую норму . Например, утверждение ${\ displaystyle x_ {i} \ geq M}$${\ displaystyle i}$${\ Displaystyle \ | {\ vec {x}} \ | _ {\ infty} \ geq M}$${\ displaystyle \ | {\ vec {x}} \ | _ {\ infty}}$

${\ displaystyle f (n, m) = n ^ {2} + m ^ {3} + O (n + m) \ quad {\ text {as}} n, m \ to \ infty}$

утверждает, что существуют такие константы C и M , что

${\ displaystyle \ forall \, \ | (n, m) \ | _ {\ infty} \ geq M: \ quad | g (n, m) | \ leq C \, | n + m | ~}$

где g ( n , m ) определяется как

${\ Displaystyle f (n, m) = n ^ {2} + m ^ {3} + g (n, m) ~.}$

Это определение позволяет всем координатам увеличиваться до бесконечности. В частности, заявление ${\ displaystyle ~ {\ vec {x}} ~}$

${\ Displaystyle е (п, м) = О (п ^ {м}) \ квад {\ текст {как}} п, м \ к \ infty ~}$

(т.е. ) сильно отличается от ${\ Displaystyle \ существует \, С \, \ существует M \, \ forall \, n \, \ forall \, m \ dots}$

${\ Displaystyle \ forall \, м \ двоеточие ~ е (n, m) = O (n ^ {m}) \ quad {\ text {as}} n \ to \ infty}$

(т.е. ). ${\ Displaystyle \ forall м \, \ существует \, С \, \ существует \, М \, \ forall \, п \, \ точек}$

Согласно этому определению, подмножество, на котором определена функция, имеет значение при обобщении утверждений от одномерного параметра до многомерного. Например, если и , то , если мы ограничиваем и к , но если они определены на . ${\ Displaystyle ~ е (п, т) = 1 ~}$${\ Displaystyle ~ г (п, т) = п ~}$${\ Displaystyle ~ е (п, т) = О (г (п, м)) ~}$${\ displaystyle f}$${\ displaystyle g}$${\ Displaystyle ~ [1, \ infty) ^ {2} ~}$${\ displaystyle [0, \ infty) ^ {2} ~}$

Это не единственное обобщение большого O на многомерные функции, и на практике существует некоторая непоследовательность в выборе определения.

Вопросы обозначения

Знак равенства

Утверждение « f ( x ) равно O ( g ( x ))», как определено выше, обычно записывается как f ( x ) =  O ( g ( x )). Некоторые считают, что это злоупотребление обозначениями , поскольку использование знака равенства может ввести в заблуждение, так как предполагает симметрию, которой нет в этом утверждении. Как говорит де Брёйн , O ( x ) =  O ( x ² ) верно, а O ( x ² ) =  O ( x ) - нет. Кнут описывает такие утверждения как «односторонние равенства», поскольку, если бы стороны могли быть поменяны местами, «мы могли бы вывести такие нелепые вещи, как n  =  n ^2, из тождеств n  =  O ( n ² ) и n ²  =  O ( n ² ). . "

По этим причинам было бы более точно использовать обозначение множества и писать f ( x ) ∈  O ( g ( x )), рассматривая O ( g ( x )) как класс всех функций h ( x ), таких что | h ( x ) | ≤  C | g ( x ) | для некоторых постоянная C . Однако обычно используется знак равенства. Кнут указал, что «математики обычно используют знак =, как они используют слово« есть »в английском языке: Аристотель - человек, но человек не обязательно Аристотель».

Другие арифметические операторы

Обозначение Big O может также использоваться вместе с другими арифметическими операторами в более сложных уравнениях. Например, h ( x ) + O ( f ( x )) обозначает набор функций, имеющих рост h ( x ) плюс часть, рост которой ограничен ростом f ( x ). Таким образом,

${\ Displaystyle г (х) = час (х) + О (е (х))}$

выражает то же, что и

${\ Displaystyle г (х) -h (х) = О (е (х)) \ ,.}$

пример

Предположим , что разрабатывается алгоритм для работы с набором из n элементов. Его разработчики заинтересованы в поиске функции T ( n ), которая выражает, сколько времени потребуется алгоритму для выполнения (в некотором произвольном измерении времени) с точки зрения количества элементов во входном наборе. Алгоритм работает, сначала вызывая подпрограмму для сортировки элементов в наборе, а затем выполняет свои собственные операции. Сортировка имеет известную временную сложность O ( n ² ), и после запуска подпрограммы алгоритм должен сделать еще 55 n ³  + 2 n  + 10 шагов, прежде чем он завершится. Таким образом, общая временная сложность алгоритма может быть выражена как T ( n ) = 55 n ³  +  O ( n ² ). Здесь члены 2 n +10 включены в быстрорастущий O ( n ² ). Опять же, это использование игнорирует некоторые формальные значения символа «=», но позволяет использовать нотацию большой буквы O в качестве удобного заполнителя.

Многократное использование

В более сложном использовании O (...) может появляться в разных местах уравнения, даже несколько раз с каждой стороны. Например, для${\ Displaystyle п \ к \ infty}$

${\ Displaystyle (п + 1) ^ {2} = п ^ {2} + О (п)}$

${\ Displaystyle (п + О (п ^ {1/2})) (п + О (\ журнал п)) ^ {2} = п ^ {3} + О (п ^ {5/2})}$

${\ displaystyle n ^ {O (1)} = O (e ^ {n}).}$

Смысл таких утверждений заключается в следующем: для любых функций, которые удовлетворяют каждому O (...) в левой части, есть некоторые функции, удовлетворяющие каждому O (...) в правой части, такие, что замена всех этих функций в уравнение уравнивает две стороны. Например, третье уравнение выше означает: «Для любой функции f ( n ) = O (1) существует функция g ( n ) = O ( e ⁿ ) такая, что n ^{f ( n )} = g ( n ). " В терминах «обозначения множества» выше, это означает, что класс функций, представленных левой стороной, является подмножеством класса функций, представленных правой стороной. В этом случае «=» является формальным символом, который в отличие от обычного использования «=» не является симметричным отношением . Таким образом, например, n ^{O (1)} = O ( e ⁿ ) не означает ложное утверждение O ( e ⁿ ) = n ^{O (1)}

Верстка

Большой O состоит только из прописной буквы «O». В отличие от обозначений Бахмана – Ландау с греческими именами, он не требует специального символа. Тем не менее, обычно используемые каллиграфические варианты, например , доступны в LaTeX и производных системах набора текста. ${\ displaystyle {\ mathcal {O}}}$

Порядки общих функций

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

Обозначение	название	пример
${\ Displaystyle O (1)}$	постоянный	Определение четного или нечетного двоичного числа; Расчет ; Использование таблицы поиска постоянного размера${\ Displaystyle (-1) ^ {п}}$
${\ Displaystyle О (\ журнал \ журнал п)}$	двойной логарифмический	Количество сравнений, проведенных при поиске элемента с использованием поиска с интерполяцией в отсортированном массиве равномерно распределенных значений
${\ Displaystyle О (\ журнал п)}$	логарифмический	Поиск элемента в отсортированном массиве с помощью бинарного поиска или сбалансированного дерева поиска, а также все операции в биномиальной куче
${\ Displaystyle О ((\ журнал п) ^ {с})}$ ${\ displaystyle \ scriptstyle c> 1}$	полилогарифмический	Упорядочение цепочки матриц может быть решено за полилогарифмическое время на параллельной машине с произвольным доступом .
${\ Displaystyle О (п ^ {с})}$ ${\ displaystyle \ scriptstyle 0 <c <1}$	дробная мощность	Поиск в дереве kd
${\ Displaystyle О (п)}$	линейный	Нахождение элемента в несортированном списке или в несортированном массиве; сложение двух n- битных целых чисел путем переноса методом пульсации
${\ Displaystyle О (п \ журнал ^ {*} п)}$	п журнал-звезда п	Выполнение триангуляции простого многоугольника с использованием алгоритма Зейделя , или алгоритм профсоюза найти . Обратите внимание, что${\ displaystyle \ log ^ {*} (n) = {\ begin {cases} 0, & {\ text {if}} n \ leq 1 \\ 1+ \ log ^ {*} (\ log n), & {\ text {if}} n> 1 \ end {case}}}$
${\ Displaystyle О (п \ журнал п) = О (\ журнал п!)}$	linearithmic , loglinear, квазилинейный или «п войти п»	Выполнение быстрого преобразования Фурье ; Самая быстрая сортировка сравнения ; heapsort и merge sort
${\ Displaystyle О (п ^ {2})}$	квадратичный	Умножение двух n- значных чисел простым алгоритмом; простые алгоритмы сортировки, такие как пузырьковая сортировка , сортировка по выбору и сортировка по вставке ; ( в худшем случае) , связанные с некоторыми обычно быстрее алгоритмов сортировки , таких как быстрая сортировка , ShellSort и дерево рода
${\ Displaystyle О (п ^ {с})}$	полиномиальный или алгебраический	Разбор смежной грамматики ; максимальное соответствие для двудольных графов ; нахождение определителя с LU-разложением
${\ Displaystyle L_ {п} [\ альфа, с] = е ^ {(с + о (1)) (\ пер п) ^ {\ альфа} (\ пер \ пер п) ^ {1- \ альфа}} }$ ${\ Displaystyle \ scriptstyle 0 <\ альфа <1}$	L-запись или субэкспоненциальная	Факторизация числа с помощью квадратного сита или сита числового поля
${\ Displaystyle О (с ^ {п})}$ ${\ displaystyle \ scriptstyle c> 1}$	экспоненциальный	Нахождение (точного) решения задачи коммивояжера с помощью динамического программирования ; определение эквивалентности двух логических операторов с помощью перебора
${\ Displaystyle О (п!)}$	факториал	Решение задачи коммивояжера методом перебора; генерация всех неограниченных перестановок чугуна ; нахождение определителя с разложением Лапласа ; перечисление всех разделов набора

Утверждение иногда ослабляется, чтобы получить более простые формулы для асимптотической сложности. Для любого и , является подмножеством для любого , так что можно рассматривать как многочлен с некоторым большим порядком. ${\ Displaystyle е (п) = О (п!)}$${\ Displaystyle е (п) = О \ влево (п ^ {п} \ вправо)}$${\ displaystyle k> 0}$${\ displaystyle c> 0}$${\ Displaystyle О (п ^ {с} (\ журнал п) ^ {к})}$${\ Displaystyle О (п ^ {с + \ varepsilon})}$${\ displaystyle \ varepsilon> 0}$

Связанные асимптотические обозначения

Big O - наиболее часто используемая асимптотическая запись для сравнения функций. Вместе с некоторыми другими родственными обозначениями он образует семейство обозначений Бахмана – Ландау.

Маленькая нотация

Интуитивно утверждение « f ( x ) is o ( g ( x )) » (читается « f ( x ) is little-o of g ( x ) ») означает, что g ( x ) растет намного быстрее, чем f ( x ). . Пусть, как и раньше, f - вещественная или комплексная функция, а g - вещественная функция, обе определены на некотором неограниченном подмножестве положительных действительных чисел , так что g ( x ) строго положительна для всех достаточно больших значений x . Один пишет

${\ Displaystyle е (х) = о (г (х)) \ квад {\ текст {as}} х \ к \ infty}$

если для любой положительной постоянной ε существует такая постоянная N , что

${\ Displaystyle | е (х) | \ leq \ varepsilon g (x) \ quad {\ text {для всех}} x \ geq N.}$

Например, есть

${\ Displaystyle 2x = о (х ^ {2})}$ и ${\ displaystyle 1 / x = o (1).}$

Разница между предыдущим определением нотации большого O и нынешним определением little-o состоит в том, что, хотя первое должно быть истинным по крайней мере для одной константы M , последнее должно выполняться для любой положительной константы ε , какой бы малой она ни была. Таким образом, нотация small-o делает более сильное утверждение, чем соответствующая нотация big-O: каждая функция, которая является little-o для g , также является большой-O для g , но не каждая функция, которая является big-O для g , также является мало-о о г . Например, но${\ displaystyle 2x ^ {2} = O (x ^ {2})}$${\ displaystyle 2x ^ {2} \ neq o (x ^ {2}).}$

Поскольку g ( x ) отличен от нуля или, по крайней мере, становится отличным от нуля после определенной точки, это соотношение эквивалентно ${\ Displaystyle е (х) = о (г (х))}$

${\ displaystyle \ lim _ {x \ to \ infty} {\ frac {f (x)} {g (x)}} = 0}$ (и именно так Ландау первоначально определил обозначение small-o).

Мало-o соблюдает ряд арифметических операций. Например,

если c - ненулевая константа и тогда , и${\ displaystyle f = o (g)}$${\ Displaystyle с \ CDOT F = о (г)}$

если и тогда${\ Displaystyle f = о (F)}$${\ displaystyle g = o (G)}$${\ displaystyle f \ cdot g = o (F \ cdot G).}$

Он также удовлетворяет соотношению транзитивности :

если и тогда${\ displaystyle f = o (g)}$${\ Displaystyle г = о (ч)}$${\ displaystyle f = o (h).}$

Обозначение Big Omega

Еще одно асимптотическое обозначение - читай «большая Омега». К сожалению, есть два широко распространенных и несовместимых определения утверждения. ${\ displaystyle \ Omega}$

${\ Displaystyle е (х) = \ Омега (г (х)) \ (х \ rightarrow а),}$

где a - некоторое действительное число, ∞ или −∞, где f и g - действительные функции, определенные в окрестности a , и где g положительно в этой окрестности.

Первый (хронологически) используется в аналитической теории чисел , а второй - в теории сложности вычислений . Когда два субъекта встречаются, эта ситуация неизбежно вызовет замешательство.

Определение Харди – Литтлвуда

В 1914 году Годфри Гарольд Харди и Джон Эденсор Литтлвуд представили новый символ , который определяется следующим образом: ${\ displaystyle \ Omega}$

${\ Displaystyle f (x) = \ Omega (g (x)) \ (x \ rightarrow \ infty) \; \ Leftrightarrow \; \ limsup _ {x \ to \ infty} \ left | {\ frac {f (x )} {g (x)}} \ right |> 0.}$

Таким образом, отрицание . ${\ Displaystyle е (х) = \ Омега (г (х))}$${\ Displaystyle е (х) = о (г (х))}$

В 1916 году те же авторы ввели два новых символа и , определяемые как: ${\ displaystyle \ Omega _ {R}}$${\ displaystyle \ Omega _ {L}}$

${\ displaystyle f (x) = \ Omega _ {R} (g (x)) \ (x \ rightarrow \ infty) \; \ Leftrightarrow \; \ limsup _ {x \ to \ infty} {\ frac {f ( x)} {g (x)}}> 0}$;

${\ displaystyle f (x) = \ Omega _ {L} (g (x)) \ (x \ rightarrow \ infty) \; \ Leftrightarrow \; \ liminf _ {x \ to \ infty} {\ frac {f ( x)} {g (x)}} <0.}$

Эти символы использовались Эдмундом Ландау с теми же значениями в 1924 году. После Ландау обозначения больше никогда не использовались именно так; стало и стало . ${\ displaystyle \ Omega _ {R}}$${\ displaystyle \ Omega _ {+}}$${\ displaystyle \ Omega _ {L}}$${\ displaystyle \ Omega _ {-}}$

Эти три символа , а также (означающее, что и оба удовлетворены) в настоящее время используются в аналитической теории чисел . ${\ Displaystyle \ Omega, \ Omega _ {+}, \ Omega _ {-}}$${\ Displaystyle е (х) = \ Омега _ {\ pm} (г (х))}$${\ Displaystyle е (х) = \ Омега _ {+} (г (х))}$${\ Displaystyle е (х) = \ Омега _ {-} (г (х))}$

Простые примеры

У нас есть

${\ Displaystyle \ грех Икс = \ Омега (1) \ (х \ rightarrow \ infty),}$

а точнее

${\ displaystyle \ sin x = \ Omega _ {\ pm} (1) \ (x \ rightarrow \ infty).}$

У нас есть

${\ Displaystyle \ грех Икс + 1 = \ Омега (1) \ (х \ rightarrow \ infty),}$

а точнее

${\ Displaystyle \ грех Икс + 1 = \ Омега _ {+} (1) \ (х \ rightarrow \ infty);}$

тем не мение

${\ displaystyle \ sin x + 1 \ not = \ Omega _ {-} (1) \ (x \ rightarrow \ infty).}$

Определение Кнута

В 1976 году Дональд Кнут опубликовал статью, в которой обосновал использование символа -символа для описания более сильного свойства. Кнут писал: «Для всех приложений, которые я видел до сих пор в информатике, более строгие требования ... гораздо более уместны». Он определил ${\ displaystyle \ Omega}$

${\ Displaystyle f (x) = \ Omega (g (x)) \ Leftrightarrow g (x) = O (f (x))}$

с комментарием: «Хотя я изменил определение Харди и Литтлвуда , я считаю, что это оправдано, потому что их определение никоим образом не широко используется, и потому что есть другие способы сказать то, что они хотят сказать, в сравнительно редких случаях когда применимо их определение ". ${\ displaystyle \ Omega}$

Семейство обозначений Бахмана – Ландау.

Обозначение	название	Описание	Формальное определение	Определение предела
${\ Displaystyle е (п) = О (г (п))}$	Большой O; Большой Ох; Большой Омикрон	${\ displaystyle | f |}$ограничено сверху g (с точностью до постоянного множителя) асимптотически	${\ Displaystyle \ существует \ к> 0 \; \ существует \ n_ {0} \; \ forall \ n> n_ {0} \ двоеточие \ \; | f (n) | \ leq k \ cdot g (n)}$	${\ displaystyle \ limsup _ {n \ to \ infty} {\ frac {\ left | f (n) \ right |} {g (n)}} <\ infty}$
${\ Displaystyle е (п) = \ тета (г (п))}$	Большая Тета	f ограничена как сверху, так и снизу через g асимптотически	${\ displaystyle \ exists \ k_ {1}> 0 \; \ exists \ k_ {2}> 0 \; \ exists \ n_ {0} \; \ forall \ n> n_ {0} \ двоеточие}$ ${\ Displaystyle к_ {1} \ cdot g (n) \ leq f (n) \ leq k_ {2} \ cdot g (n)}$	${\ Displaystyle е (п) = О (г (п))}$и (версия Кнута) ${\ Displaystyle е (п) = \ Омега (г (п))}$
${\ Displaystyle е (п) = \ Омега (г (п))}$	Большая Омега в теории сложности (Кнут)	f ограничена снизу g асимптотически	${\ Displaystyle \ существует \ к> 0 \; \ существует \ n_ {0} \; \ forall \ n> n_ {0} \ двоеточие \ \; f (n) \ geq k \ cdot g (n)}$	${\ displaystyle \ liminf _ {n \ to \ infty} {\ frac {f (n)} {g (n)}}> 0}$
${\ Displaystyle е (п) = о (г (п))}$	Маленький O; Маленький О	f асимптотически преобладает над g	${\ Displaystyle \ forall \ k> 0 \; \ exists \ n_ {0} \; \ forall \ n> n_ {0} \ двоеточие \ \; | f (n) | <k \ cdot g (n)}$	${\ displaystyle \ lim _ {n \ to \ infty} {\ frac {\ left | f (n) \ right |} {g (n)}} = 0}$
${\ Displaystyle е (п) \ сим г (п)}$	В порядке	f асимптотически равна g	${\ Displaystyle \ forall \ \ varepsilon> 0 \; \ exists \ n_ {0} \; \ forall \ n> n_ {0} \ двоеточие \ \; \ left | {f (n) \ over g (n)} -1 \ right | <\ varepsilon}$	${\ Displaystyle \ lim _ {п \ к \ infty} {е (п) \ над г (п)} = 1}$
${\ Displaystyle е (п) = \ омега (г (п))}$	Малая Омега	f асимптотически доминирует над g	${\ Displaystyle \ forall \ k> 0 \; \ exists \ n_ {0} \; \ forall \ n> n_ {0} \ двоеточие \ \; | f (n) |> k \ cdot | g (n) | }$	${\ displaystyle \ lim _ {n \ to \ infty} \ left | {\ frac {f (n)} {g (n)}} \ right | = \ infty}$
${\ Displaystyle е (п) = \ Омега (г (п))}$	Большая Омега в теории чисел (Харди – Литтлвуд)	${\ displaystyle | f |}$не доминирует над g асимптотически	${\ Displaystyle \ существует \ к> 0 \; \ forall \ n_ {0} \; \ exists \ n> n_ {0} \ двоеточие \ \; | f (n) | \ geq k \ cdot g (n)}$	${\ displaystyle \ limsup _ {n \ to \ infty} \ left | {\ frac {f (n)} {g (n)}} \ right |> 0}$

Предельные определения предполагаются при достаточно большом n . Таблица (частично) отсортирована от наименьшего к наибольшему в том смысле, что o, O, Θ, ∼, (версия Кнута) Ω, ω на функциях соответствуют <, ≤, ≈, =, ≥,> на вещественном (версия Ω Харди-Литтлвуда, однако, не соответствует ни одному такому описанию). ${\ displaystyle g (n)> 0}$

В информатике используются нотации большого O , большого Theta Θ, маленького o , маленького omega ω и большого Omega Ω Кнута. Аналитическая теория чисел часто использует большие O , маленькие O , большие Omega Ω Харди – Литтлвуда (с индексами +, - или ± или без них) и обозначения. Маленькие обозначения омега ω не так часто используются в анализе. ${\ displaystyle \ sim}$

Использование в информатике

Неформально, особенно в информатике, нотация большого O часто может использоваться несколько иначе для описания асимптотической жесткой границы, где использование большой нотации Theta Θ может быть более актуальным в данном контексте. Например, при рассмотрении функции T ( n ) = 73 n ³ + 22 n ² + 58 все нижеследующее обычно приемлемо, но более жесткие границы (например, числа 2 и 3 ниже) обычно предпочтительнее более свободных ( например, номер 1 ниже).

1. Т ( п ) =  О ( п ¹⁰⁰ )
2. Т ( п ) =  О ( п ³ )
3. Т ( п ) = Θ ( п ³ )

Эквивалентные английские утверждения соответственно:

1. T ( n ) растет асимптотически не быстрее, чем n ¹⁰⁰
2. T ( n ) растет асимптотически не быстрее, чем n ³
3. T ( n ) растет асимптотически так же быстро, как n ³ .

Таким образом, хотя все три утверждения верны, в каждом содержится все больше информации. В некоторых полях, однако, большая нотация O (цифра 2 в списках выше) будет использоваться чаще, чем большая нотация Theta (элементы с номером 3 в списках выше). Например, если T ( n ) представляет время работы недавно разработанного алгоритма для входного размера n , изобретатели и пользователи алгоритма могут быть более склонны установить верхнюю асимптотическую границу того, сколько времени потребуется для выполнения, не делая явное утверждение о нижней асимптотической оценке.

Другие обозначения

В своей книге Введение в алгоритмы , Кормена , Лейзерсон , Ривест и Stein рассмотрим множество функций F , которые удовлетворяют условию

${\ Displaystyle е (п) = О (г (п)) \ квад (п \ стрелка вправо \ infty) ~.}$

В правильных обозначениях это множество можно, например, назвать O ( g ), где

${\ Displaystyle О (г) = \ {е:}$существуют положительные постоянные c и такие, что для всех . ${\ displaystyle n_ {0}}$${\ Displaystyle 0 \ Leq е (п) \ Leq с \, г (п)}$${\ displaystyle n \ geq n_ {0} \}}$

Авторы заявляют, что использование оператора равенства (=) для обозначения членства в множестве, а не оператора членства в множестве (∈) является злоупотреблением нотацией, но это имеет преимущества. Внутри уравнения или неравенства использование асимптотической записи означает анонимную функцию в множестве O ( g ), что исключает члены более низкого порядка и помогает уменьшить несущественный беспорядок в уравнениях, например:

${\ displaystyle 2n ^ {2} + 3n + 1 = 2n ^ {2} + O (n).}$

Расширения обозначений Бахмана – Ландау.

Другое обозначение, которое иногда используется в информатике, - это Õ (читай soft-O ): f ( n ) =  Õ ( g ( n )) - это сокращение для f ( n ) =  O ( g ( n ) log ^k  g ( n )) для некоторые k . По сути, это большая нотация O, игнорирующая логарифмические факторы, потому что эффекты скорости роста некоторых других суперлогарифмических функций указывают на взрыв скорости роста для входных параметров большого размера, которые более важны для прогнозирования плохой производительности во время выполнения, чем более точные -точечные эффекты, вносимые логарифмическими факторами роста. Это обозначение часто используется, чтобы избежать «придирок» в пределах темпов роста, которые заявлены как слишком жестко ограниченные для рассматриваемых вопросов (поскольку log ^k  n всегда o ( n ^ε ) для любой константы k и любого ε> 0).

Также обозначение L , определенное как

${\ Displaystyle L_ {п} [\ альфа, с] = е ^ {(с + о (1)) (\ пер п) ^ {\ альфа} (\ пер \ пер п) ^ {1- \ альфа}} }$

удобен для функций, которые находятся между полиномиальными и экспоненциальными в терминах . ${\ displaystyle \ ln n}$

Обобщения и связанные с ними употребления

Обобщение на функции, принимающие значения в любом нормированном векторном пространстве, является простым (заменяя абсолютные значения нормами), где f и g не должны принимать свои значения в одном и том же пространстве. Также возможно обобщение на функции g, принимающие значения в любой топологической группе . «Ограничивающий процесс» x  →  x _o также может быть обобщен путем введения произвольной базы фильтров , то есть направленных сетей f и  g . О нотации может быть использована для определения производных и дифференцируемого в довольно общих пространства, а также (асимптотическая) эквивалентность функций,

${\ Displaystyle е \ сим г \ iff (fg) \ in o (g)}$

которое является отношением эквивалентности и более ограничительным понятием, чем отношение « f is Θ ( g )» сверху. (Это сводится к lim f / g = 1, если f и g - положительные вещественные функции.) Например, 2 x - это Θ ( x ), но 2 x  -  x не является o ( x ).

История (обозначения Бахмана – Ландау, Харди и Виноградова)

Символ O был впервые введен теоретиком чисел Полем Бахманном в 1894 году во втором томе его книги Analytische Zahlentheorie (« аналитическая теория чисел »). Теоретик чисел Эдмунд Ландау принял его и, таким образом, был вдохновлен ввести в 1909 году обозначение o; поэтому оба теперь называются символами Ландау. Эти обозначения использовались в прикладной математике в 1950-х годах для асимптотического анализа. Этот символ (в смысле «не является о ») был введен в 1914 году Харди и Литтлвудом. Харди и Литтлвуд также ввели в 1918 году символы («правый») и («левый»), предшественники современных символов («не меньше маленького о») и («не больше маленького о» ). Таким образом, символы Омеги (с их первоначальным значением) иногда также называют «символами Ландау». Это обозначение стало широко использоваться в теории чисел, по крайней мере, с 1950-х годов. В 1970-х годах большой O был популяризирован в компьютерных науках Дональдом Кнутом , который ввел соответствующую нотацию Theta и предложил другое определение нотации Omega. ${\ displaystyle \ Omega}$${\ displaystyle \ Omega _ {R}}$${\ displaystyle \ Omega _ {L}}$${\ displaystyle \ Omega _ {+}}$${\ displaystyle \ Omega _ {-}}$${\ displaystyle \ Omega}$

Ландау никогда не использовал большие символы теты и малые омега.

Символы Харди были (с точки зрения современной нотации O )

${\ displaystyle f \ preccurlyeq g \ iff f \ in O (g)}$   и   ${\ Displaystyle е \ пре г \ если и только если е \ в о (г);}$

(Hardy , однако никогда не определен или использованы обозначения , ни , как это было иногда сообщается). Харди представил символы и (а также некоторые другие символы) в своем трактате 1910 года «Ордена бесконечности» и использовал их только в трех статьях (1910–1913). В своих почти 400 оставшихся статьях и книгах он постоянно использовал символы Ландау O и o. ${\ Displaystyle \ Prec \! \! \ Prec}$${\ displaystyle \ ll}$${\ displaystyle \ preccurlyeq}$${\ Displaystyle \ Prec}$

Обозначения Харди больше не используются. С другой стороны, в 1930-х годах русский теоретик чисел Иван Матвеевич Виноградов ввел свои обозначения , которые все чаще использовались в теории чисел вместо обозначений. У нас есть ${\ displaystyle \ ll}$${\ displaystyle O}$

${\ displaystyle f \ ll g \ iff f \ in O (g),}$

и часто оба обозначения используются в одной и той же статье.

Большой-O первоначально означает "порядок" ("Ordnung", Bachmann 1894) и, таким образом, является латинской буквой. Ни Бахманн, ни Ландау никогда не называли его «Омикрон». Значительно позже (1976 г.) Кнут рассматривал этот символ как заглавную омикрон , вероятно, в связи с его определением символа Омега . Цифру ноль использовать не следует.

Смотрите также

• Асимптотическое разложение : приближение функций, обобщающих формулу Тейлора
• Асимптотически оптимальный алгоритм : фраза, часто используемая для описания алгоритма, который имеет верхнюю границу асимптотически в пределах константы нижней границы для задачи.
• Большой O в вероятностной записи : O _p , o _p
• Верхний предел и нижний предел : объяснение некоторых обозначений пределов, используемых в этой статье
• Основная теорема (анализ алгоритмов) : для анализа рекурсивных алгоритмов «разделяй и властвуй» с использованием нотации Big O
• Теорема Nachbin в : Точный метод ограничивающего сложные аналитические функции , так что область сходимости интегральных преобразований можно утверждать ,
• Порядки приближения
• Вычислительная сложность математических операций

Ссылки и примечания

дальнейшее чтение

• Харди, Г. Х. (1910). Ордена бесконечности: «Infinitärcalcül» Поля дю Буа-Реймон . Издательство Кембриджского университета .
• Кнут, Дональд (1997). «1.2.11: Асимптотические представления». Фундаментальные алгоритмы . Искусство программирования. 1 (3-е изд.). Аддисон-Уэсли. ISBN 978-0-201-89683-1.
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001). «3.1: Асимптотические обозначения». Введение в алгоритмы (2-е изд.). MIT Press и McGraw – Hill. ISBN 978-0-262-03293-3.
• Сипсер, Майкл (1997). Введение в теорию вычислений . PWS Publishing. С.  226 –228. ISBN 978-0-534-94728-6.
• Авигад, Джереми; Доннелли, Кевин (2004). Формализация нотации O в Isabelle / HOL (PDF) . Международная совместная конференция по автоматизированному мышлению. DOI : 10.1007 / 978-3-540-25984-8_27 .
• Блэк, Пол Э. (11 марта 2005 г.). Блэк, Пол Э. (ред.). "нотация большого О" . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Проверено 16 декабря 2006 года .
• Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). "маленькая нотация" . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Проверено 16 декабря 2006 года .
• Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). «Ω» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Проверено 16 декабря 2006 года .
• Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). «ω» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Проверено 16 декабря 2006 года .
• Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). «Θ» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Проверено 16 декабря 2006 года .

внешние ссылки

• Рост последовательностей - OEIS (Интернет-энциклопедия целочисленных последовательностей) Wiki
• Введение в асимптотические обозначения
• Символы Ландау
• Обозначение Big-O - для чего это нужно
• Обозначение Big O на простом английском
• Пример Big O в точности центральной схемы разделенных разностей для первой производной
• Нежное введение в анализ сложности алгоритмов