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

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

Пример обозначения Big O: поскольку существуют (например, ) и (например, ) такие, что всякий раз, когда . ${\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] и другими, которые в совокупности называются нотацией Бахмана-Ландау или асимптотической нотацией . Буква О была выбрана Бахманом для обозначения Ordnung , что означает порядок приближения .

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

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

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

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

Пусть оцениваемая функция является действительной или комплексной функцией, а функция сравнения - действительной функцией. Пусть обе функции определены на некотором неограниченном подмножестве положительных действительных чисел и строго положительны для всех достаточно больших значений . ^[4] Один пишет ${\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 x}$ ${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}}$ ${\displaystyle M}$ ${\displaystyle x_{0}}$

$${\displaystyle |f(x)|\leq Mg(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 Mg(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|}{g(x)}}<\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 Mg(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 х ⁴ — это произведение 6 и х ⁴ , в котором первый множитель не зависит от х . Отсутствие этого фактора приводит к упрощенной форме x ⁴ . Таким образом, мы говорим, что ^f ( x ) — это «большое О» x4 . Математически мы можем написать f ( x ) = O ( x ⁴ ) . Подтвердить этот расчет можно с помощью формального определения: пусть f ( x ) = 6 x ⁴ − 2 x ³ + 5 и g ( x ) = x ⁴ . Применяя формальное определение, данное выше, утверждение, что f ( x ) = O ( x ⁴ ) , эквивалентно его расширению,

$${\displaystyle |f(x)|\leq Mx^{4}}$$

x ₀Mx > x ₀x ₀ = 1M = 13x > x ₀

$${\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}.}$$

Применение

Обозначение Big O имеет две основные области применения:

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

В обоих приложениях функция 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 , а именно. Т (1 000 000) = 1 000 000 ³ = U (1 000 000) . Кроме того, количество шагов зависит от деталей модели машины, на которой работает алгоритм, но разные типы машин обычно различаются только на постоянный коэффициент количества шагов, необходимых для выполнения алгоритма. Таким образом, большая запись О отражает то, что осталось: мы пишем либо

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

или

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

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

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

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

${\displaystyle {\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}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 достаточно близок к 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 ( nc ) и O ( cn ⁾ сильно ^{различаются} . Если c больше единицы, то последняя растет гораздо быстрее. Функция, которая растет быстрее, чем ^nc для любого c , называется суперполиномиальной . Та, которая растет медленнее любой показательной функции вида cn ^, называется субэкспоненциальной . Алгоритму может потребоваться время, которое является как суперполиномиальным, так и субэкспоненциальным; примеры этого включают самые быстрые известные алгоритмы факторизации целых чисел и функцию n ^{log n} .

Мы можем игнорировать любые степени n внутри логарифмов. Набор O (log n ) точно такой же, как O ⁽ log( nc )) . Логарифмы отличаются только постоянным коэффициентом (поскольку 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 ^{n .} Изменение переменных также может повлиять на порядок результирующего алгоритма. Например, если время выполнения алгоритма равно 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 для нескольких переменных, предположим, что и — две функции, определенные на некотором подмножестве . Мы говорим ${\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 ^2, из тождеств n = O ( n ² ) и n ² = O ( п ² ) ». ^[10] В другом письме Кнут также указал, что «знак равенства не симметричен относительно таких обозначений», поскольку в этом обозначении «математики обычно используют знак =, как они используют слово «is» в английском языке: Аристотель — человек, но мужчина не обязательно Аристотель». ^[11]

По этим причинам было бы точнее использовать обозначение множества и писать f ( x ) ∈ O ( g ( x )) (читается как: « f ( x ) является элементом O ( g ( x ))», или « f ( x ) находится в множестве O ( g ( x ))»), думая об O ( g ( x )) как о классе всех функций h ( x ) таких, что | час ( Икс )| ≤  Cg ( 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 (·) может появляться в разных местах уравнения, даже несколько раз с каждой стороны. Например, для : ${\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некоторыеOfnOgnOen ⁾n ^{f ( n )}gnсимметричным отношениемⁿ O ^{( 1)} = O ( en )^{O (en} ) = n O ( ^{1 )}

верстка

Большой 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}$

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

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

Обозначение Little-o

Интуитивно, утверждение « f ( x ) is o ( g ( x )) » (читай « f ( x ) мало-о от g ( x ) ») означает, что g ( x ) растёт гораздо быстрее, чем f ( 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 и определением small-o заключается в том, что первое должно быть верным хотя бы для одной константы M , а второе должно выполняться для каждой положительной константы ε , какой бы маленькой она ни была. ^[17] Таким образом, обозначение «маленькое-о» является более сильным утверждением , чем соответствующее обозначение «большое-О»: каждая функция, которая является «маленьким-О» для g , также является «большим-О» для g , но не каждая функция, которая является «большим-О» для g , но не каждая функция, которая является «большим-О» для g. g также мало-о от 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).}$

Обозначение Большой Омеги

Другое асимптотическое обозначение — читай «большая омега». ^[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 (g(x))}$будто _ ${\displaystyle x\to \infty }$ ${\displaystyle \limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.}$

Таково отрицание . ${\displaystyle f(x)=\Omega (g(x))}$ ${\displaystyle f(x)=o(g(x))}$

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

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

${\displaystyle f(x)=\Omega _{L}(g(x))}$будто _ ${\displaystyle x\to \infty }$ ${\displaystyle \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 }(g(x))}$ ${\displaystyle f(x)=\Omega _{+}(g(x))}$ ${\displaystyle f(x)=\Omega _{-}(g(x))}$

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

У нас есть

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

и точнее

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

У нас есть

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

и точнее

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

однако

${\displaystyle \sin x+1\not =\Omega _{-}(1)}$как ${\displaystyle 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 }$

В информатике используются обозначения «большая -большая тета» , «маленькая -маленькая омега» и «большая омега» Кнута . ^[28] Аналитическая теория чисел часто использует большую , маленькую , большую Омегу Харди-Литтлвуда (с индексами +, - или ± или без них) и обозначения. ^[22] Маленькие омега- нотации используются в анализе не так часто. ^[29] ${\displaystyle O}$ ${\displaystyle \Theta }$ ${\displaystyle o}$ ${\displaystyle \omega }$ ${\displaystyle \Omega }$ ${\displaystyle O}$ ${\displaystyle o}$ ${\displaystyle \Omega }$ ${\displaystyle \sim }$ ${\displaystyle \omega }$

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

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

1. Т ( п ) знак равно О ( п ¹⁰⁰ )
2. Т ( п ) знак равно О ( п ³ )
3. Т ( п ) знак равно Θ( п ³ )

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

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

Таким образом, хотя все три утверждения верны, каждое из них содержит все больше информации. Однако в некоторых областях большая нотация О (номер 2 в списках выше) будет использоваться чаще, чем большая нотация Тета (пункты под номером 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}\}.}$$

^[31]

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

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

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

Другое обозначение, иногда используемое в информатике, — Õ (читай soft-O ), которое скрывает полилогарифмические коэффициенты. Используются два определения: некоторые авторы используют f ( n ) =  Õ ( g ( n )) как сокращение для f ( n ) = O ( g ( n ) log ^k n ) для некоторого k , в то время как другие используют его как сокращение для ж ( п ) знак равно О ( г ( п ) журнал ^k г ( п )) . ^[33] Когда g ( n ) является полиномиальным по n , разницы нет; однако последнее определение позволяет, например, сказать, что первое определение допускает любую константу k . Некоторые авторы пишут О ^* с той же целью, что и последнее определение. ^[34] По сути, это обозначение большого О , игнорирующее логарифмические коэффициенты , поскольку эффекты скорости роста некоторой другой суперлогарифмической функции указывают на взрывной темп роста для входных параметров большого размера, что более важно для прогнозирования плохой производительности во время выполнения. чем более мелкие эффекты, вносимые фактором(ами) логарифмического роста. Это обозначение часто используется, чтобы избежать «придирок» к темпам роста, которые заявлены как слишком жестко ограниченные для рассматриваемых вопросов (поскольку 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 is Θ( g )», указанное выше. (Оно сводится к lim f / g = 1, если f и g — положительные вещественнозначные функции.) Например, 2 x равно Θ( x ), но 2 x − x не равно o ( x ).

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

Символ O был впервые введен теоретиком чисел Полом Бахманом в 1894 году во втором томе его книги Analytische Zahlentheorie (« аналитическая теория чисел »). ^[1] Теоретик чисел Эдмунд Ландау принял его и, таким образом, был вдохновлен введением в 1909 году обозначения o; ^[2] поэтому оба теперь называются символами Ландау. Эти обозначения использовались в прикладной математике в 1950-х годах для асимптотического анализа. ^[35] Символ (в смысле «не является буквой о ») был введен в 1914 году Харди и Литтлвудом. ^[19] Харди и Литтлвуд также ввели в 1916 году символы («правый») и («левый»), ^[20] предшественники современных символов («не меньше маленькой буквы») и («не больше чем маленькое о»). Таким образом, символы Омеги (с их первоначальным значением) иногда также называют «символами Ландау». Это обозначение стало широко использоваться в теории чисел, по крайней мере, с 1950-х годов. ^[36] В 1970-х годах большая буква О была популяризирована в информатике Дональдом Кнутом , который ввёл родственную нотацию Тета и предложил другое определение нотации Омега. ^[24] ${\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 f\prec g\iff f\in o(g);}$

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

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

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

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

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

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

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

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

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 Co.Здесь: Def.7.2, стр.227
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) из оригинала 24 апреля 2015 г. Проверено 23 апреля 2015 г.
9. Н.Г. де Брейн (1958). Асимптотические методы анализа. Амстердам: Северная Голландия. стр. 5–7. ISBN 978-0-486-64221-5. Архивировано из оригинала 17 января 2023 г. Проверено 15 сентября 2021 г.
10. Грэм, Рональд ; Кнут, Дональд ; Паташник, Орен (1994). Конкретная математика (2-е изд.). Ридинг, Массачусетс: Аддисон-Уэсли. п. 446. ИСБН 978-0-201-55802-9. Архивировано из оригинала 17 января 2023 г. Проверено 23 сентября 2016 г.
11. Дональд Кнут (июнь – июль 1998 г.). «Учите исчислению с большой буквой О» (PDF) . Уведомления Американского математического общества . 45 (6): 687. Архивировано (PDF) из оригинала 14 октября 2021 г. Проверено 05 сентября 2021 г.(Полная версия. Архивировано 13 мая 2008 г. на Wayback Machine )
12. Дональд Э. Кнут, Искусство компьютерного программирования. Том. 1. Фундаментальные алгоритмы, третье издание, Аддисон Уэсли Лонгман, 1997. Раздел 1.2.11.1.
13. Рональд Л. Грэм, Дональд Э. Кнут и Орен Паташник, Конкретная математика: фонд компьютерных наук (2-е изд.) , Аддисон-Уэсли, 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. ОСЛК  676697295.
19. Харди, GH; Литтлвуд, Дж. Э. (1914). «Некоторые задачи диофантовой аппроксимации: Часть II. Тригонометрический ряд, связанный с эллиптическими θ-функциями». Акта Математика . 37 : 225. дои : 10.1007/BF02401834 . Архивировано из оригинала 12 декабря 2018 г. Проверено 14 марта 2017 г.
20. GH Hardy и JE Littlewood, «Вклад в теорию дзета-функции Римана и теорию распределения простых чисел», Acta Mathematica , vol. 41, 1916.
21. Э. Ландау, «Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV». Нахр. Гезелл. Висс. Гетт. Математика-физ. кл. 1924, 137–150.
22. Александр Ивич. Дзета-функция Римана, глава 9. John Wiley & Sons, 1985.
23. Джеральд Тененбаум, Введение в аналитическую и вероятностную теорию чисел, Глава I.5. Американское математическое общество, Провиденс, Род-Айленд, 2015.
24. Кнут, Дональд (апрель – июнь 1976 г.). «Большой Омикрон, большая Омега и большая Тета» (PDF) . Новости СИГАКТ . 8 (2): 18–24. дои : 10.1145/1008328.1008329. S2CID  5230246. Архивировано из оригинала 08 апреля 2022 г. Проверено 8 декабря 2022 г.{{cite journal}}: CS1 maint: bot: original URL status unknown (link)
25. Балькасар, Хосе Л.; Габарро, Хоаким. «Классы неоднородной сложности, определяемые нижними и верхними границами» (PDF) . RAIRO – Теоретическая информатика и приложения – Informatique Théorique et Applications . 23 (2): 180. ISSN  0988-3754. Архивировано (PDF) из оригинала 14 марта 2017 года . Проверено 14 марта 2017 г.
26. Кукер, Фелипе; Бюргиссер, Питер (2013). «A.1 Большое о, маленькое о и другие сравнения». Условие: Геометрия численных алгоритмов . Берлин, Гейдельберг: Springer. стр. 467–468. дои : 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. например, он опущен в: Хильдебранд, А.Дж. «Асимптотические обозначения» (PDF) . Кафедра математики. Асимптотические методы анализа . Math 595, осень 2009 г. Урбана, Иллинойс: Университет Иллинойса. Архивировано (PDF) из оригинала 14 марта 2017 года . Проверено 14 марта 2017 г.
30. Кормен и др. (2009), с. 64: «Многие люди продолжают использовать О -нотацию там, где Θ-нотация технически более точна».
31. Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л. (2009). Введение в алгоритмы (3-е изд.). Кембридж/Массачусетс: MIT Press. п. 47. ИСБН 978-0-262-53305-8. Когда у нас есть только асимптотическая верхняя граница, мы используем O-нотацию. Для данной функции g ( n ) мы обозначаем через O ( g ( n )) (произносится как «big-oh of g of n » или иногда просто «oh of g of n ») набор функций O ( g ( n) )) = { f ( n ) : существуют положительные константы c и n ₀ такие, что 0 ⩽ f ( n ) ⩽ cg ( n ) для всех n ≥ n ₀ }
32. Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л. (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 ) = 3n + 1, что действительно находится в θ ( n ). Использование асимптотических обозначений таким образом может помочь устранить несущественные детали и беспорядок в уравнении.
33. Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2022). Введение в алгоритмы (4-е изд.). Кембридж, Массачусетс: MIT Press. стр. 74–75. ISBN 9780262046305.
34. Андреас Бьорклунд, Торе Хусфельдт и Микко Койвисто (2009). «Настройка разделения посредством включения-исключения» (PDF) . SIAM Journal по вычислительной технике . 39 (2): 546–563. дои : 10.1137/070683933. Архивировано (PDF) из оригинала 3 февраля 2022 г. Проверено 3 февраля 2022 г.См. разд.2.3, стр.551.
35. Эрдели, А. (1956). Асимптотические разложения . Курьерская корпорация. ISBN 978-0-486-60318-6.
36. EC Титчмарш, Теория дзета-функции Римана (Оксфорд; Clarendon Press, 1951)
37. См., например, «Новая оценка G ( n ) в задаче Варинга» (рус.). Доклады Академии наук СССР 5, № 5–6 (1934), 249–253. Переведено на английский язык: Избранные произведения / Иван Матвеевич Виноградов; подготовлен Математическим институтом им. Стеклова АН СССР к его 90-летию. Спрингер-Верлаг, 1985.

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

• Харди, GH (1910). Ордены бесконечности: «Бесконечный расчет» Поля дю Буа-Реймона. Издательство Кембриджского университета .
• Кнут, Дональд (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). Введение в теорию вычислений . Издательство ПВС. стр. 226–228. ISBN 978-0-534-94728-6.
• Авигад, Джереми; Доннелли, Кевин (2004). Формализация нотации O в Isabelle/HOL (PDF) . Международная совместная конференция по автоматизированному рассуждению. дои : 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 – для чего это нужно
• Пример большого О в точности схемы центральной разделенной разности для первой производной. Архивировано 7 октября 2018 г. на Wayback Machine.
• Нежное введение в анализ сложности алгоритмов