Обозначение «Большое О»

Описывает предельное поведение функции

Пример нотации «большое О»: поскольку существует (например, ) и (например, ) такие, что всякий раз, когда . ${\displaystyle {\color {red}f(x)}=O{\color {blue}(g(x))}}$ ${\displaystyle x\to \infty }$ ${\displaystyle M>0}$ ${\displaystyle M=1}$ ${\displaystyle x_{0}}$ ${\displaystyle x_{0}=5}$ ${\displaystyle 0\leq {\color {red}f(x)}\leq M{\color {blue}g(x)}}$ ${\displaystyle x\geq x_{0}}$

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

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

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

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

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

Пусть оцениваемая функция будет действительной или комплексной функцией, а функция сравнения будет действительной функцией. Пусть обе функции определены на некотором неограниченном подмножестве положительных действительных чисел и не равны нулю (часто, но не обязательно, строго положительны) для всех достаточно больших значений ^[4] Пишут и читают « является большим O от » или чаще « имеет порядок », если абсолютное значение не более чем положительная константа, кратная абсолютному значению для всех достаточно больших значений То есть, если существует положительное действительное число и действительное число такое, что Во многих контекстах предположение о том, что нас интересует скорость роста при стремлении переменной к бесконечности или к нулю, остается невысказанным, и пишут проще, что Обозначение также можно использовать для описания поведения вблизи некоторого действительного числа (часто, ): мы говорим , что существуют положительные числа и такие, что для всех определенных с As не равно нулю для достаточно больших (или малых) значений оба эти определения можно объединить с помощью превосходного предела : если И в обоих этих определениях предельная точка (независимо от того , является ли она точкой кластера областей из и т. е. в каждой окрестности должно быть бесконечно много общих точек. Более того, как указано в статье о нижнем и верхнем пределе , (по крайней мере на расширенной числовой прямой ) всегда существует. ${\displaystyle f,}$ ${\displaystyle \ g\ ,}$ ${\displaystyle g(x)}$ ${\displaystyle x.}$ $${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to \infty }$$ ${\displaystyle \ f(x)\ }$ ${\displaystyle g(x)}$ ${\displaystyle f(x)}$ ${\displaystyle g(x)}$ ${\displaystyle f(x)}$ ${\displaystyle g(x)}$ ${\displaystyle x.}$ ${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}}$ ${\displaystyle M}$ ${\displaystyle x_{0}}$ $${\displaystyle |f(x)|\leq M\ |g(x)|\quad {\text{ for all }}x\geq x_{0}~.}$$ ${\displaystyle \ x\ }$ $${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}.}$$ ${\displaystyle f}$ ${\displaystyle a}$ ${\displaystyle a=0}$ $${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}\ x\to a}$$ ${\displaystyle \delta }$ ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle 0<|x-a|<\delta ,}$ $${\displaystyle |f(x)|\leq M|g(x)|.}$$ ${\displaystyle g(x)}$ ${\displaystyle x,}$ $${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}\ x\to a}$$ $${\displaystyle \limsup _{x\to a}{\frac {\left|f(x)\right|}{\left|g(x)\right|}}<\infty .}$$ ${\displaystyle a}$ ${\displaystyle \infty }$ ${\displaystyle f}$ ${\displaystyle g,}$ ${\displaystyle a}$ ${\displaystyle \textstyle \limsup _{x\to a}}$

В информатике распространено несколько более ограничительное определение: и оба должны быть функциями из некоторого неограниченного подмножества положительных целых чисел в неотрицательные действительные числа; тогда если существуют положительные целые числа и такие, что для всех ^[5] ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}}$ ${\displaystyle M}$ ${\displaystyle n_{0}}$ ${\displaystyle |f(n)|\leq M|g(n)|}$ ${\displaystyle n\geq n_{0}.}$

Пример

В типичном использовании обозначение 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 ⁴ ) эквивалентно его расширению, для некоторого подходящего выбора действительного числа x ₀ и положительного действительного числа M и для всех x > x ₀ . Чтобы доказать это, пусть x ₀ = 1 и M = 13 . Тогда для всех x > x ₀ : так что $${\displaystyle |f(x)|\leq Mx^{4}}$$ $${\displaystyle {\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}}$$ $${\displaystyle |6x^{4}-2x^{3}+5|\leq 13x^{4}.}$$

Использовать

Обозначение «О большое» имеет две основные области применения:

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

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

Существуют два формально близких, но заметно отличающихся варианта использования этой записи: ^{[ необходима ссылка ]}

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

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

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

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

Обозначение Big O полезно при анализе эффективности алгоритмов . Например, время (или количество шагов), необходимое для завершения задачи размера n, может быть найдено равным T ( n ) = 4 n ² − 2 n + 2 . По мере того, как n становится большим, член n ² начинает доминировать, так что всеми другими членами можно пренебречь — например, когда n = 500 , член 4 n ² в 1000 раз больше члена 2 n . Игнорирование последнего имело бы пренебрежимо малое влияние на значение выражения для большинства целей. Кроме того, коэффициенты становятся несущественными, если мы сравниваем с любым другим порядком выражения, например, с выражением, содержащим член 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(n)=O(n^{2})}$

или

${\displaystyle T(n)\in O(n^{2})}$

и говорят, что алгоритм имеет порядок сложности n ² . Знак " = " не предназначен для выражения "равно" в его обычном математическом смысле, а скорее для более разговорного "есть", поэтому второе выражение иногда считается более точным (см. обсуждение "Знака равенства" ниже), в то время как первое рассматривается некоторыми как злоупотребление обозначениями . ^[6]

Асимптотика бесконечно малых величин

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

${\displaystyle {\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all finite }}x\\[4pt]&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\[4pt]&=1+x+O(x^{2})&{\text{as }}x\to 0\end{aligned}}}$

Среднее выражение (с O ( x ³ )) означает, что абсолютное значение ошибки e ^x − (1 + x + x ² /2) составляет максимум некоторую константу, умноженную на | x ³ |, когда 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 ,} называется субэкспоненциальной . Алгоритм может потребовать времени, которое является как суперполиномиальным, так и субэкспоненциальным; примерами этого являются самые быстрые известные алгоритмы для целочисленной факторизации и функция 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 ( n ) при измерении в терминах количества n цифр входного числа x , то его время выполнения равно O (log x ) при измерении как функции самого входного числа x , потому что 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 f\cdot O(g)=O(fg)}$

Сумма

Если и тогда . Отсюда следует, что если и тогда . Другими словами, это второе утверждение говорит, что является выпуклым конусом . ${\displaystyle f_{1}=O(g_{1})}$ ${\displaystyle f_{2}=O(g_{2})}$ ${\displaystyle f_{1}+f_{2}=O(\max(g_{1},g_{2}))}$ ${\displaystyle f_{1}=O(g)}$ ${\displaystyle f_{2}=O(g)}$ ${\displaystyle f_{1}+f_{2}\in O(g)}$ ${\displaystyle O(g)}$

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

Пусть k — ненулевая константа. Тогда . Другими словами, если , то ${\displaystyle O(|k|\cdot g)=O(g)}$ ${\displaystyle f=O(g)}$ ${\displaystyle k\cdot f=O(g).}$

Множественные переменные

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

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

тогда и только тогда, когда существуют константы и такие, что для всех с для некоторых ^[7] Эквивалентно, условие, что для некоторых можно записать , где обозначает норму Чебышёва . Например, утверждение ${\displaystyle M}$ ${\displaystyle C>0}$ ${\displaystyle |f(\mathbf {x} )|\leq C|g(\mathbf {x} )|}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle x_{i}\geq M}$ ${\displaystyle i.}$ ${\displaystyle x_{i}\geq M}$ ${\displaystyle i}$ ${\displaystyle \|\mathbf {x} \|_{\infty }\geq M}$ ${\displaystyle \|\mathbf {x} \|_{\infty }}$

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

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

${\displaystyle |f(n,m)-(n^{2}+m^{3})|\leq C|n+m|}$

всякий раз, когда выполняется или . Это определение позволяет всем координатам увеличиваться до бесконечности. В частности, утверждение ${\displaystyle m\geq M}$ ${\displaystyle n\geq M}$ ${\displaystyle \mathbf {x} }$

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

(т.е. ) весьма отличается от ${\displaystyle \exists C\,\exists M\,\forall n\,\forall m\,\cdots }$

${\displaystyle \forall m\colon ~f(n,m)=O(n^{m})\quad {\text{ as }}n\to \infty }$

(т.е. ). ${\displaystyle \forall m\,\exists C\,\exists M\,\forall n\,\cdots }$

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

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

Вопросы нотации

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

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

«знак равенства не симметричен относительно таких обозначений», [как в этой нотации] «математики обычно используют знак '=' так же, как они используют слово 'is' в английском языке: Аристотель — человек, но человек не обязательно Аристотель». ^[11]

По этим причинам было бы точнее использовать обозначение множеств и записывать f ( x ) ∈ O [ g ( x ) ]   (читается как: « f ( x )   является элементом O [ g ( x ) ]   » или « f ( x )   находится во множестве O [ g ( x ) ]»), думая об O [ g ( x ) ]   как о классе всех функций h ( x )   таких, что | h ( x ) | ≤ C | g ( x ) |   для некоторого положительного действительного числа C . ^[10] Однако использование знака равенства является общепринятым. ^{[9] [10]}               

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

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

${\displaystyle g(x)=h(x)+O(f(x))}$

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

${\displaystyle g(x)-h(x)=O(f(x)).}$

Пример

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

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

В более сложном использовании O (·) может появляться в разных местах уравнения, даже несколько раз с каждой стороны. Например, для верны следующие утверждения : Значение таких утверждений следующее: для любых функций, которые удовлетворяют каждому 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)} . ${\displaystyle n\to \infty }$ $${\displaystyle {\begin{aligned}(n+1)^{2}&=n^{2}+O(n),\\(n+O(n^{1/2}))\cdot (n+O(\log n))^{2}&=n^{3}+O(n^{5/2}),\\n^{O(1)}&=O(e^{n}).\end{aligned}}}$$

Набор текста

Большая O набирается как курсивная заглавная «O», как в следующем примере: . ^{[12] [13]} В TeX она получается простым набором O в математическом режиме. В отличие от греческих обозначений Бахмана–Ландау, ей не нужен специальный символ. Однако некоторые авторы используют вместо этого каллиграфический вариант . ^{[14] [15]} ${\displaystyle O(n^{2})}$ ${\displaystyle {\mathcal {O}}}$

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

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

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

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

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

Обозначение «маленькое о»

Интуитивно утверждение " f ( x ) is o ( g ( x )) " (читается как " f ( x ) is little-o of g ( x ) " или " f ( x ) is of lower order to g ( x ) ") означает, что g ( x ) растет гораздо быстрее, чем f ( x ) , или, что эквивалентно, f ( x ) растет гораздо медленнее, чем g ( x ) . Как и прежде, пусть f будет действительной или комплексной функцией, а g — действительной функцией, обе определенные на некотором неограниченном подмножестве положительных действительных чисел , так что g ( x ) строго положительна для всех достаточно больших значений x . Пишется

${\displaystyle f(x)=o(g(x))\quad {\text{ as }}x\to \infty }$

если для каждой положительной константы ε существует константа такая, что ${\displaystyle x_{0}}$

${\displaystyle |f(x)|\leq \varepsilon g(x)\quad {\text{ for all }}x\geq x_{0}.}$^[16]

Например, у одного есть

${\displaystyle 2x=o(x^{2})}$и     оба как ${\displaystyle 1/x=o(1),}$ ${\displaystyle x\to \infty .}$

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

Если g ( x ) не равен нулю или, по крайней мере, становится ненулевым после определенной точки, то соотношение эквивалентно следующему: ${\displaystyle f(x)=o(g(x))}$

${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0}$(и именно так Ландау ^[16] первоначально определил обозначение маленькой буквы «о»).

Little-o уважает ряд арифметических операций. Например,

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

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

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

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

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

Другая асимптотическая нотация — , читается как «большая омега». ^[18] Существуют два распространенных и несовместимых определения утверждения ${\displaystyle \Omega }$

${\displaystyle f(x)=\Omega (g(x))}$как , ${\displaystyle x\to a}$

где a — некоторое действительное число , или , где f и g — действительные функции, определенные в окрестности a , и где g положительно в этой окрестности. ${\displaystyle \infty }$ ${\displaystyle -\infty }$

Определение Харди–Литтлвуда используется в основном в аналитической теории чисел , а определение Кнута — в основном в теории сложности вычислений ; определения не эквивалентны.

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

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

${\displaystyle f(x)=\Omega {\bigl (}\ g(x)\ {\bigr )}\quad }$как будто ${\displaystyle \quad x\to \infty \quad }$ ${\displaystyle \quad \limsup _{x\to \infty }\ \left|{\frac {\ f(x)\ }{g(x)}}\right|>0~.}$

Таким образом, отрицание ${\displaystyle ~f(x)=\Omega {\bigl (}\ g(x)\ {\bigr )}~}$ ${\displaystyle ~f(x)=o{\bigl (}\ g(x)\ {\bigr )}~.}$

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

${\displaystyle f(x)=\Omega _{R}{\bigl (}\ g(x)\ {\bigr )}\quad }$как будто ${\displaystyle \quad x\to \infty \quad }$ ${\displaystyle \quad \limsup _{x\to \infty }\ {\frac {\ f(x)\ }{g(x)}}>0\ ;}$

${\displaystyle f(x)=\Omega _{L}{\bigl (}\ g(x)\ {\bigr )}\quad }$как будто ${\displaystyle \quad x\to \infty \quad }$ ${\displaystyle \quad ~\liminf _{x\to \infty }\ {\frac {\ f(x)\ }{g(x)}}<0~.}$

Эти символы использовались Э. Ландау с теми же значениями в 1924 году. ^[21] Однако авторы, последовавшие за Ландау, использовали другую нотацию для тех же определений: ^{[ необходима ссылка ]} Символ был заменен текущей нотацией с тем же определением и стал ${\displaystyle \ \Omega _{R}\ }$ ${\displaystyle \ \Omega _{+}\ }$ ${\displaystyle \ \Omega _{L}\ }$ ${\displaystyle \ \Omega _{-}~.}$

Эти три символа , а также (что означает, что и оба удовлетворяются), в настоящее время используются в аналитической теории чисел . ^{[22] [23]} ${\displaystyle \ \Omega \ ,\Omega _{+}\ ,\Omega _{-}\ ,}$ ${\displaystyle \ f(x)=\Omega _{\pm }{\bigl (}\ g(x)\ {\bigr )}\ }$ ${\displaystyle \ f(x)=\Omega _{+}{\bigl (}\ g(x)\ {\bigr )}\ }$ ${\displaystyle \ f(x)=\Omega _{-}{\bigl (}\ g(x)\ {\bigr )}\ }$

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

У нас есть

${\displaystyle \sin x=\Omega (1)\quad }$как ${\displaystyle \quad x\to \infty \ ,}$

и точнее

${\displaystyle \sin x=\Omega _{\pm }(1)\quad }$как ${\displaystyle \quad x\to \infty ~.}$

У нас есть

${\displaystyle 1+\sin x=\Omega (1)\quad }$как ${\displaystyle \quad x\to \infty \ ,}$

и точнее

${\displaystyle 1+\sin x=\Omega _{+}(1)\quad }$как ${\displaystyle \quad x\to \infty \ ;}$

однако

${\displaystyle 1+\sin x\neq \Omega _{-}(1)\quad }$как ${\displaystyle \quad x\to \infty ~.}$

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

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

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

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

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

Определения пределов предполагают для достаточно больших . Таблица (частично) отсортирована от наименьшего к наибольшему, в том смысле, что (версия Кнута) на функциях соответствует на действительной прямой ^[27] (версия Харди–Литтлвуда , однако, не соответствует ни одному такому описанию). ${\displaystyle g(n)>0}$ ${\displaystyle n}$ ${\displaystyle o,O,\Theta ,\sim ,}$ ${\displaystyle \Omega ,\omega }$ ${\displaystyle <,\leq ,\approx ,=,}$ ${\displaystyle \geq ,>}$ ${\displaystyle \Omega }$

В компьютерной науке используются обозначения big , big Theta , little , little omega и big Omega Кнута . ^[28] Аналитическая теория чисел часто использует обозначения big , small , Hardy , ^[29] Hardy–Littlewood's big Omega (с индексами +, − или ± или без них) и . ^[22] Обозначение small omega не так часто используется в анализе. ^[30] ${\displaystyle O}$ ${\displaystyle \Theta }$ ${\displaystyle o}$ ${\displaystyle \omega }$ ${\displaystyle \Omega }$ ${\displaystyle O}$ ${\displaystyle o}$ ${\displaystyle \asymp }$ ${\displaystyle \Omega }$ ${\displaystyle \sim }$ ${\displaystyle \omega }$

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

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

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

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

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

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

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

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

${\displaystyle f(n)=O(g(n))\quad (n\to \infty )~.}$

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

$${\displaystyle O(g)=\{f:{\text{there exist positive constants}}~c~{\text{and}}~n_{0}~{\text{such that}}~0\leq f(n)\leq cg(n){\text{ for all }}n\geq n_{0}\}.}$$^[32]

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

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

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

Другая нотация, иногда используемая в информатике, — это Õ (читается как soft-O ), которая скрывает полилогарифмические множители. Используются два определения: некоторые авторы используют f ( n ) =  Õ ( g ( n )) как сокращение для f ( n ) = O ( g ( n ) log ^k n ) для некоторых k , в то время как другие используют его как сокращение для f ( n ) = O ( g ( n ) log ^k g ( n )) . ^[34] Когда g ( n ) является полиномом по n , разницы нет; однако последнее определение позволяет сказать, например, что в то время как первое определение допускает для любой константы k . Некоторые авторы пишут O ^* для той же цели, что и последнее определение. ^[35] По сути, это большая нотация O , игнорирующая логарифмические факторы , поскольку эффекты скорости роста некоторой другой суперлогарифмической функции указывают на взрыв скорости роста для входных параметров большого размера, что более важно для прогнозирования плохой производительности во время выполнения, чем более тонкие эффекты, вносимые логарифмическим фактором(ами) роста. Эта нотация часто используется, чтобы избежать «придирок» в пределах скоростей роста, которые заявлены как слишком жестко ограниченные для рассматриваемых вопросов (поскольку log ^k n всегда равен o ( n ^ε ) для любой константы k и любого ε > 0 ). ${\displaystyle n2^{n}={\tilde {O}}(2^{n})}$ ${\displaystyle \log ^{k}n={\tilde {O}}(1)}$ 

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

${\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }},}$

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

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

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

${\displaystyle f\sim g\iff (f-g)\in o(g)}$

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

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

Символ O был впервые введен теоретиком чисел Паулем Бахманом в 1894 году во втором томе его книги Analytische Zahlentheorie (« Аналитическая теория чисел »). ^[1] Теоретик чисел Эдмунд Ландау принял его и, таким образом, был вдохновлен введением в 1909 году обозначения o; ^[2] поэтому оба теперь называются символами Ландау. Эти обозначения использовались в прикладной математике в 1950-х годах для асимптотического анализа. ^[36] Символ (в смысле «не является o в ») был введен в 1914 году Харди и Литтлвудом. ^[19] Харди и Литтлвуд также ввели в 1916 году символы («правый») и («левый»), ^[20] предшественники современных символов («не меньше, чем малая o в») и («не больше, чем малая o в»). Таким образом, символы Омега (с их первоначальными значениями) иногда также называют «символами Ландау». Эта нотация стала широко использоваться в теории чисел, по крайней мере, с 1950-х годов. ^[37] ${\displaystyle \Omega }$ ${\displaystyle \Omega _{R}}$ ${\displaystyle \Omega _{L}}$ ${\displaystyle \Omega _{+}}$ ${\displaystyle \Omega _{-}}$ ${\displaystyle \Omega }$

Символ , хотя он использовался и раньше с разными значениями, ^[27] получил свое современное определение от Ландау в 1909 году ^[38] и Харди в 1910 году. ^[39] Чуть выше на той же странице своего трактата Харди определил символ , где означает, что выполняются оба и . Эта нотация до сих пор используется в аналитической теории чисел. ^{[40] [29]} В своем трактате Харди также предложил символ , где означает, что для некоторой константы . ${\displaystyle \sim }$ ${\displaystyle \asymp }$ ${\displaystyle f(x)\asymp g(x)}$ ${\displaystyle f(x)=O(g(x))}$ ${\displaystyle g(x)=O(f(x))}$ ${\displaystyle \,\asymp \!\!\!\!\!\!-}$ ${\displaystyle f\asymp \!\!\!\!\!\!-g}$ ${\displaystyle f\sim Kg}$ ${\displaystyle K\not =0}$

В 1970-х годах большая буква O была популяризирована в компьютерной науке Дональдом Кнутом , который предложил другую нотацию для Харди и предложил другое определение для нотации Харди и Литтлвуда Omega. ^[24] ${\displaystyle f(x)=\Theta (g(x))}$ ${\displaystyle f(x)\asymp g(x)}$

Два других символа, придуманных Харди, были (в терминах современной нотации O )

${\displaystyle f\preccurlyeq g\iff f=O(g)}$   и   ${\displaystyle f\prec g\iff f=o(g);}$

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

Символы Харди и (а также ) больше не используются. С другой стороны, в 1930-х годах ^[41] русский теоретик чисел Иван Матвеевич Виноградов ввел свою нотацию , которая все чаще используется в теории чисел вместо нотации. Мы имеем ${\displaystyle \preccurlyeq }$ ${\displaystyle \prec }$ ${\displaystyle \,\asymp \!\!\!\!\!\!-}$ ${\displaystyle \ll }$ ${\displaystyle O}$

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

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

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

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

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

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

1. Бахманн, Пол (1894). Analytische Zahlentheorie [ Аналитическая теория чисел ] (на немецком языке). Том. 2. Лейпциг: Тойбнер.
2. Ландау, Эдмунд (1909). Handbuch der Lehre von der Verteilung der Primzahlen [Справочник по теории распределения простых чисел ] (на немецком языке). Лейпциг: Б. Г. Тойбнер. п. 883.
3. Мор, Остин. «Квантовые вычисления в теории сложности и теории вычислений» (PDF) . стр. 2. Архивировано (PDF) из оригинала 8 марта 2014 г. Получено 7 июня 2014 г.
4. Ландау, Эдмунд (1909). Handbuch der Lehre von der Verteilung der Primzahlen [Справочник по теории распределения простых чисел ] (на немецком языке). Лейпциг: Б. Г. Тойбнер. п. 31.
5. Сипсер, Майкл (1997). Введение в теорию вычислений . Бостон, Массачусетс: PWS Publishing. стр. 227, определение 7.2.
6. Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л. (2009). Введение в алгоритмы (3-е изд.). Кембридж/Массачусетс: MIT Press. п. 45. ИСБН 978-0-262-53305-8. Поскольку θ ( g ( n )) является множеством, мы могли бы написать " f ( n ) ∈ θ ( g ( n ))", чтобы указать, что f ( n ) является членом θ ( g ( n )). Вместо этого мы обычно будем писать f ( n ) = θ ( g ( n )) для выражения того же понятия. Вас может смутить, потому что мы таким образом злоупотребляем равенством, но позже в этом разделе мы увидим, что это имеет свои преимущества.
7. Кормен и др. (2009), стр. 53
8. Хауэлл, Родни. "Об асимптотической нотации с несколькими переменными" (PDF) . Архивировано (PDF) из оригинала 2015-04-24 . Получено 2015-04-23 .
9. де Брёйн, НГ (1958). Асимптотические методы анализа. Амстердам: Северная Голландия. стр. 5–7. ISBN 978-0-486-64221-5. Архивировано из оригинала 2023-01-17 . Получено 2021-09-15 .
10. Грэм, Рональд ; Кнут, Дональд ; Паташник, Орен (1994). Конкретная математика (2-е изд.). Reading, Массачусетс: Addison–Wesley. стр. 446. ISBN 978-0-201-55802-9. Архивировано из оригинала 2023-01-17 . Получено 2016-09-23 .
11. Дональд Кнут (июнь–июль 1998 г.). «Teach Calculus with Big O» (PDF) . Notices of the American Mathematical Society . 45 (6): 687. Архивировано (PDF) из оригинала 2021-10-14 . Получено 2021-09-05 .(Несокращенная версия. Архивировано 13 мая 2008 г. на Wayback Machine )
12. Дональд Э. Кнут, Искусство программирования. Том 1. Фундаментальные алгоритмы, третье издание, Addison Wesley Longman, 1997. Раздел 1.2.11.1.
13. Рональд Л. Грэм, Дональд Э. Кнут и Орен Паташник, Конкретная математика: основа компьютерной науки (2-е изд.) , Addison-Wesley, 1994. Раздел 9.2, стр. 443.
14. Сиварам Амбикасаран и Эрик Дарве, Быстрый прямой решатель для частично иерархически полуразделимых матриц, J. Scientific Computing 57 (2013), № 3, 477–501. ${\displaystyle {\mathcal {O}}(N\log N)}$
15. Сакет Саурабх и Мейрав Зехави, -Max-Cut: алгоритм -Time и полиномиальное ядро, Algorithmica 80 (2018), № 12, 3844–3860. ${\displaystyle (k,n-k)}$ ${\displaystyle {\mathcal {O}}^{*}(2^{p})}$
16. Ландау, Эдмунд (1909). Handbuch der Lehre von der Verteilung der Primzahlen [Справочник по теории распределения простых чисел ] (на немецком языке). Лейпциг: Б. Г. Тойбнер. п. 61.
17. Томас Х. Кормен и др., 2001, Введение в алгоритмы, второе издание, гл. 3.1 Архивировано 16 января 2009 г. на Wayback Machine
18. Кормен Т.Х., Лейзерсон CE, Ривест Р.Л., Штейн С. (2009). Введение в алгоритмы (3-е изд.). Кембридж, Массачусетс: MIT Press. п. 48. ИСБН 978-0-262-27083-0. OCLC  676697295.
19. Hardy, GH ; Littlewood, JE (1914). "Некоторые проблемы диофантовых приближений: Часть II. Тригонометрические ряды, связанные с эллиптическими θ-функциями". Acta Mathematica . 37 : 225. doi : 10.1007/BF02401834 . Архивировано из оригинала 2018-12-12 . Получено 2017-03-14 .
20. Харди, GH ; Литтлвуд, JE (1916). «Вклад в теорию дзета-функции Римана и теорию распределения простых чисел». Acta Mathematica . 41 .
21. Ландау, Э. (1924). «Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV» [О количестве точек сетки в известных регионах]. Нахр. Гезелл. Висс. Гетт. Математика-физ. (на немецком языке): 137–150.
22. Ivić, A. (1985). Дзета-функция Римана . John Wiley & Sons. глава 9.
23. Тененбаум, Г. (2015). Введение в аналитическую и вероятностную теорию чисел . Провиденс, Род-Айленд: Американское математическое общество. § I.5.
24. Кнут, Дональд (апрель–июнь 1976). «Большой Омикрон и большая Омега и большая Тета». SIGACT News . 8 (2): 18–24. doi : 10.1145/1008328.1008329 . S2CID 5230246 . 
25. Балькасар, Хосе Л.; Габарро, Хоаким. «Классы неоднородной сложности, определяемые нижними и верхними границами» (PDF) . RAIRO – Теоретическая информатика и приложения – Informatique Théorique et Applications . 23 (2): 180. ISSN  0988-3754. Архивировано (PDF) из оригинала 14 марта 2017 г. Проверено 14 марта 2017 г. - через Numdam.
26. Cucker, Felipe; Bürgisser, Peter (2013). "A.1 Big Oh, Little Oh, and Other Comparisons". Условие: Геометрия численных алгоритмов . Берлин, Гейдельберг: Springer. стр. 467–468. doi :10.1007/978-3-642-38896-5. ISBN 978-3-642-38896-5.
27. Витаньи, Пол ; Меертенс, Ламберт (апрель 1985 г.). «Большая Омега против диких функций» (PDF) . Новости ACM SIGACT . 16 (4): 56–59. CiteSeerX 10.1.1.694.3072 . дои : 10.1145/382242.382835 . S2CID 11700420 . Архивировано (PDF) из оригинала 10 марта 2016 г. Проверено 14 марта 2017 г.  
28. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стайн, Клиффорд (2001) [1990]. Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 41–50. ISBN 0-262-03293-7.
29. Джеральд Тененбаум, Введение в аналитическую и вероятностную теорию чисел, « Обозначения », стр. xxiii. Американское математическое общество, Провиденс, Род-Айленд, 2015.
30. например, он опущен в: Hildebrand, AJ "Asymptotic Notations" (PDF) . Department of Mathematics. Asymptotic Methods in Analysis . Math 595, осень 2009. Urbana, IL: University of Illinois. Архивировано (PDF) из оригинала 14 марта 2017 г. . Получено 14 марта 2017 г. .
31. Кормен и др. (2009), стр. 64: «Многие продолжают использовать O -обозначение, тогда как Θ-обозначение технически более точно».
32. Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л. (2009). Введение в алгоритмы (3-е изд.). Кембридж/Массачусетс: MIT Press. п. 47. ИСБН 978-0-262-53305-8. Когда у нас есть только асимптотическая верхняя граница, мы используем O-нотацию. Для заданной функции g ( n ) мы обозначаем через O ( g ( n )) (произносится как «биг-оу g от n » или иногда просто «оу g от n » ) множество функций O ( g ( n )) = { f ( n ) : существуют положительные константы c и n ₀ такие, что 0 ≤ f ( n ) ≤ cg ( n ) для всех n ≥ n ₀ }
33. Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л. (2009). Введение в алгоритмы (3-е изд.). Кембридж/Массачусетс: MIT Press. п. 49. ИСБН 978-0-262-53305-8. Когда асимптотическая запись стоит отдельно (то есть не внутри более крупной формулы) в правой части уравнения (или неравенства), как в n = O(n ² ), мы уже определили знак равенства для обозначения принадлежности к множеству: n ∈ O(n ² ). Однако, в общем случае, когда асимптотическая запись появляется в формуле, мы интерпретируем ее как обозначение некоторой анонимной функции, которую мы не хотим называть. Например, формула 2 n ² + 3 n + 1 = 2 n ² + θ ( n ) означает, что 2 n ² + 3 n + 1 = 2 n ² + f ( n ), где f ( n ) — некоторая функция из множества θ ( n ). В этом случае мы даем f ( n ) = 3 n + 1, что действительно входит в θ ( n ). Использование асимптотической записи таким образом может помочь устранить несущественные детали и беспорядок в уравнении.
34. Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Стайн, Клиффорд (2022). Введение в алгоритмы (4-е изд.). Кембридж, Массачусетс: The MIT Press. стр. 74–75. ISBN 9780262046305.
35. Андреас Бьёрклунд и Торе Хусфельдт и Микко Койвисто (2009). «Разбиение множеств с помощью включения-исключения» (PDF) . SIAM Journal on Computing . 39 (2): 546–563. doi :10.1137/070683933. Архивировано (PDF) из оригинала 2022-02-03 . Получено 2022-02-03 .См. раздел 2.3, стр. 551.
36. Эрдели, А. (1956). Асимптотические разложения . Courier Corporation. ISBN 978-0-486-60318-6.
37. EC Titchmarsh, Теория дзета-функции Римана (Оксфорд; Clarendon Press, 1951)
38. Ландау, Эдмунд (1909). Handbuch der Lehre von der Verteilung der Primzahlen [Справочник по теории распределения простых чисел ] (на немецком языке). Лейпциг: Б. Г. Тойбнер. п. 62.
39. Харди, Г. Х. (1910). Порядки бесконечности: «Бесконечное исчисление» Поля дю Буа-Реймона. Cambridge University Press . стр. 2.
40. Харди, GH; Райт, EM (2008) [1-е изд. 1938]. "1.6. Некоторые обозначения". Введение в теорию чисел . Переработано DR Heath-Brown и JH Silverman , с предисловием Andrew Wiles (6-е изд.). Oxford: Oxford University Press. ISBN 978-0-19-921985-8.
41. См., например, «Новая оценка для G ( n ) в проблеме Варинга» (на русском языке). Доклады Академии наук СССР 5, № 5-6 (1934), 249–253. Перевод на английский язык: Избранные труды / Иван Матвеевич Виноградов; подготовлено Математическим институтом им. В.А. Стеклова Академии наук СССР к его 90-летию. Springer-Verlag, 1985.

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

• Харди, Г. Х. (1910). Порядки бесконечности: «Бесконечное исчисление» Поля дю Буа-Реймона. Cambridge University Press .
• Кнут, Дональд (1997). "1.2.11: Асимптотические представления". Фундаментальные алгоритмы . Искусство программирования. Том 1 (3-е изд.). Эддисон-Уэсли. ISBN 978-0-201-89683-1.
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (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 г.). Блэк, Пол Э. (ред.). "нотация little-o". Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Получено 16 декабря 2006 г.
• Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). "Ω". Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Получено 16 декабря 2006 г.
• Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). "ω". Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Получено 16 декабря 2006 г.
• Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). "Θ". Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Получено 16 декабря 2006 г.

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

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