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

Концепции

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

Пример обозначения Big O: as существует (например, ) и (например, ) такие, что when .

{\ displaystyle {\ color {красный} f (x)} \ in O {\ color {blue} (g (x))}}

{\ displaystyle M> 0}

{\ displaystyle M = 1}

x_{0}

x_{0}=5

{\color {red}f(x)}\leq {\color {blue}Mg(x)}

x\geq x_{0}

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

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

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

Формальное определение [ править ]

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

f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to \infty

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

|f(x)|\leq Mg(x)\quad {\text{ for all }}x\geq x_{0}.

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

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

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

f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to a

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

|f(x)|\leq Mg(x).

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

f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to a

если

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

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

Пример [ править ]

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

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

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

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

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

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

так

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

Использование [ править ]

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

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

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

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

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

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

Бесконечная асимптотика [ править ]

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

N в

зависимости от размера входных данных

n

для каждой функции

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

T(n)=O(n^{2})

или же

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

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

Бесконечно малые асимптотики [ править ]

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

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

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

Свойства [ править ]

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

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 n)$ очень разные. Если $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 n$ и $3 n$ не одного порядка.

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

Продукт [ править ]

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

f\cdot O(g)=O(fg)

Сумма [ править ]

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

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

Умножение на константу [ править ]

Пусть

k

будет постоянным. Потом:

O(|k|g)=O(g)

если

k

ненулевое.

f=O(g)\Rightarrow kf=O(g).

Несколько переменных [ править ]

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

f({\vec {x}}){\text{ is }}O(g({\vec {x}}))\quad {\text{ as }}{\vec {x}}\to \infty

тогда и только тогда, когда ^[8]

\exists M\exists C>0~{\text{ such that for all }}~{\vec {x}}~{\text{ with }}~x_{i}\geq M~{\text{ for some }}~i,|f({\vec {x}})|\leq C|g({\vec {x}})|~.

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

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

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

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

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

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

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

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

(т.е. ) сильно отличается от $\exists C\exists M\forall n\forall m\dots$

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

(т.е. ). $\forall m\exists C\exists M\forall n\dots$

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

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

Вопросы обозначения [ править ]

Знак равенства [ править ]

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

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

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

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

g(x)=h(x)+O(f(x))

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

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 (...) может появляться в разных местах уравнения, даже несколько раз с каждой стороны. Например, для $n\to \infty$

(n+1)^{2}=n^{2}+O(n)

(n+O(n^{1/2}))(n+O(\log n))^{2}=n^{3}+O(n^{5/2})

n^{O(1)}=O(e^{n}).

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

Верстка [ править ]

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

Порядки общих функций [ править ]

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

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

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

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

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

Маленькая нотация [ править ]

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

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

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

|f(x)|\leq \varepsilon g(x)\quad {\text{ for all }}x\geq N.

^[17]

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

2x=o(x^{2})

и

1/x=o(1).

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

Поскольку g ( x ) отличен от нуля или, по крайней мере, становится отличным от нуля после определенной точки, отношение эквивалентно $f(x)=o(g(x))$

\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0

(и именно так Ландау ^[17] первоначально определил обозначение small-o).

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

если

c

- ненулевая константа и тогда , и

f=o(g)

c\cdot f=o(g)

если и тогда

f=o(F)

g=o(G)

f\cdot g=o(F\cdot G).

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

если и тогда

f=o(g)

g=o(h)

f=o(h).

Обозначение Большой Омеги [ править ]

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

f(x)=\Omega (g(x))

как ,

x\rightarrow a,

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

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

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

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

f(x)=\Omega (g(x))

как будто

x\rightarrow \infty

\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.

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

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

f(x)=\Omega _{R}(g(x))

как будто ;

x\rightarrow \infty

\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0

f(x)=\Omega _{L}(g(x))

как будто

x\rightarrow \infty

\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.

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

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

Простые примеры [ править ]

У нас есть

\sin x=\Omega (1)

в качестве

x\rightarrow \infty ,

а точнее

\sin x=\Omega _{\pm }(1)

в качестве

x\rightarrow \infty .

У нас есть

\sin x+1=\Omega (1)

в качестве

x\rightarrow \infty ,

а точнее

\sin x+1=\Omega _{+}(1)

в качестве

x\rightarrow \infty ;

тем не мение

\sin x+1\not =\Omega _{-}(1)

в качестве

x\rightarrow \infty .

Определение Кнута [ править ]

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

f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))

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

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

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

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

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

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

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

Т ( п ) = О ( п ¹⁰⁰ )
Т ( п ) = О ( п ³ )
Т ( п ) = Θ ( п ³ )

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

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

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

Другие обозначения [ править ]

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

f(n)=O(g(n))\quad (n\rightarrow \infty )~.

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

O(g)=\{f:

существуют положительные константы c и такие, что для всех . ^[30]

n_{0}

0\leq f(n)\leq cg(n)

n\geq n_{0}\}

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

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

Расширения обозначений Бахмана – Ландау [ править ]

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

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

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

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

Обобщения и связанные с ними обычаи [ править ]

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

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-х годах для асимптотического анализа. ^[33] Символ (в смысле «не является о ») был введен в 1914 году Харди и Литтлвудом. ^[19] Харди и Литтлвуд также ввели в 1918 г. символы («право») и $\Omega$ $\Omega _{R}$ $\Omega _{L}$ («слева»), ^[20] предшественники современных символов («не меньше маленького о») и («не больше маленького о»). Таким образом, символы Омеги (с их первоначальным значением) иногда также называют «символами Ландау». Это обозначение стало широко использоваться в теории чисел, по крайней мере, с 1950-х годов. ^[34] В 1970-х годах большой O был популяризирован в компьютерных науках Дональдом Кнутом , который ввел соответствующую нотацию Theta и предложил другое определение нотации Omega. ^[24] $\Omega _{+}$ $\Omega _{-}$ $\Omega$

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

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

f\preccurlyeq g\iff f\in O(g)

и

f\prec g\iff f\in o(g);

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

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

f\ll g\iff f\in O(g),

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

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

См. Также [ править ]

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

Ссылки и примечания [ править ]

^ a b Бахманн, Пауль (1894). Analytische Zahlentheorie [ Аналитическая теория чисел ] (на немецком языке). 2 . Лейпциг: Тойбнер.
^ a b Ландау, Эдмунд (1909). Handbuch der Lehre von der Verteilung der Primzahlen [ Справочник по теории распределения простых чисел ] (на немецком языке). Лейпциг: BG Teubner. п. 883.
^ Мор, Остин. «Квантовые вычисления в теории сложности и теории вычислений» (PDF) . п. 2 . Проверено 7 июня 2014 .
^ Ландау, Эдмунд (1909). Handbuch der Lehre von der Verteilung der Primzahlen [ Справочник по теории распределения простых чисел ] (на немецком языке). Лейпциг: BG Teubner. п. 31.
^ Майкл Сипсер (1997). Введение в теорию вычислений . Бостон / Массачусетс: PWS Publishing Co. Здесь: Def.7.2, стр.227
^ Например,не определено в. $\log(n)$ $n=0$
^ а б Кормен, Томас Х .; Leiserson, Charles E .; Ривест, Рональд Л. (2009). Введение в алгоритмы (3-е изд.). Кембридж / Массачусетс: MIT Press. п. 45 . ISBN 978-0-262-53305-8. Поскольку θ ( g ( n )) - это множество, мы могли бы написать « f ( n ) ∈ θ ( g ( n ))», чтобы указать, что f ( n ) является членом θ ( g ( n )). Вместо этого мы обычно будем писать f ( n ) = θ ( g ( n )), чтобы выразить то же понятие. Вы можете быть сбиты с толку, потому что мы таким образом злоупотребляем равенством, но позже в этом разделе мы увидим, что это имеет свои преимущества.
^ Кормен, Томас; Лейзерсон, Чарльз; Ривест, Рональд; Стейн, Клиффорд (2009). Введение в алгоритмы (третье изд.). Массачусетский технологический институт. п. 53 .
^ Хауэлл, Родни. «Об асимптотической записи с несколькими переменными» (PDF) . Проверено 23 апреля 2015 .
^ Н. де Брейна (1958). Асимптотические методы анализа . Амстердам: Северная Голландия. С. 5–7. ISBN 978-0-486-64221-5.
^ a b Грэм, Рональд ; Кнут, Дональд ; Паташник, Орен (1994). Конкретная математика (2-е изд.). Ридинг, Массачусетс: Аддисон – Уэсли. п. 446. ISBN. 978-0-201-55802-9.
↑ Дональд Кнут (июнь – июль 1998 г.). «Научите математическому анализу с большой буквы O» (PDF) . Уведомления Американского математического общества . 45 (6): 687. ( Полная версия )
^ Дональд Э. Кнут, Искусство компьютерного программирования. Vol. 1. Фундаментальные алгоритмы, третье издание, Addison Wesley Longman, 1997. Раздел 1.2.11.1.
^ Рональд Л. Грэм, Дональд Э. Кнут и Орен Паташник, Конкретная математика: Фонд компьютерных наук (2-е изд.) , Аддисон-Уэсли, 1994. Раздел 9.2, с. 443.
^ Сиварам Амбикасаран и Эрик Дарв,Быстрый прямой решатель для частично иерархически полуразделяемых матриц, J. Scientific Computing 57 (2013), нет. 3, 477–501. ${\mathcal {O}}(N\log N)$
^ Сакет Саураб и Мейрав Зехави,-Max-Cut:алгоритм времени и полиномиальное ядро, Algorithmica 80 (2018), нет. 12, 3844–3860. $(k,n-k)$ ${\mathcal {O}}^{*}(2^{p})$
^ a b Ландау, Эдмунд (1909). Handbuch der Lehre von der Verteilung der Primzahlen [ Справочник по теории распределения простых чисел ] (на немецком языке). Лейпциг: BG Teubner. п. 61.
^ Томас Х. Кормен и др., 2001, Введение в алгоритмы, второе издание ^{[ необходима страница ]}
^ а б в Харди, GH; Литтлвуд, Дж. Э. (1914). «Некоторые проблемы диофантова приближения. Часть II. Тригонометрические ряды, связанные с эллиптическими ϑ-функциями» . Acta Mathematica . 37 : 225. DOI : 10.1007 / BF02401834 .
^ a b Г. Х. Харди и Дж. Литтлвуд, «Вклад в теорию дзета-функции Римана и теорию распределения простых чисел», Acta Mathematica , vol. 41, 1916 г.
^ Э. Ландау, "Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV." Nachr. Геселл. Wiss. Gött. Math-Phys. Kl. 1924, 137–150.
^ a b Александр Ивич. Дзета-функция Римана, глава 9. John Wiley & Sons 1985.
^ Джеральд Тененбаум, Введение в аналитическую и вероятностную теорию чисел, Глава I.5. Американское математическое общество, Провиденс, Род-Айленд, 2015.
^ a b c d e Кнут, Дональд (апрель – июнь 1976 г.). «Большой Омикрон, и большая Омега, и большая Тета» (PDF) . Новости SIGACT : 18–24.
^ Balcazar, José L .; Габарро, Хоаким. «Неоднородные классы сложности, заданные нижними и верхними границами» (PDF) . RAIRO - Теоретическая информатика и приложения - Теория информатики и приложения . 23 (2): 180. ISSN 0988-3754 . Проверено 14 марта 2017 года .
^ Cucker, Фелипе; Бюргиссер, Питер (2013). «A.1 Big Oh, Little Oh и другие сравнения». Условие: геометрия численных алгоритмов . Берлин, Гейдельберг: Springer. С. 467–468. DOI : 10.1007 / 978-3-642-38896-5 . ISBN 978-3-642-38896-5.
^ a b Витаньи, Пол ; Меертенс, Ламберт (апрель 1985 г.). «Большая Омега против диких функций» (PDF) . Новости ACM SIGACT . 16 (4): 56–59. CiteSeerX 10.1.1.694.3072 . DOI : 10.1145 / 382242.382835 .
^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990]. Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 41–50. ISBN 0-262-03293-7.
^ например, он опущен в: Hildebrand, AJ "Asymptotic Notations" (PDF) . Кафедра математики. Асимптотические методы анализа . Math 595, осень 2009 г. Урбана, Иллинойс: Университет Иллинойса . Проверено 14 марта 2017 года .
^ Кормен, Томас Х .; Leiserson, Charles E .; Ривест, Рональд Л. (2009). Введение в алгоритмы (3-е изд.). Кембридж / Массачусетс: MIT Press. п. 47. ISBN 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 ) для всехп ≥ п ₀ }
^ Кормен, Томас Х .; Leiserson, Charles E .; Ривест, Рональд Л. (2009). Введение в алгоритмы (3-е изд.). Кембридж / Массачусетс: MIT Press. п. 49 . ISBN 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 ). Использование асимптотических обозначений таким образом может помочь устранить несущественные детали и беспорядок в уравнении.
^ Введение в алгоритмы . Кормен, Томас Х. (Третье изд.). Кембридж, Массачусетс: MIT Press. 2009. с. 63 . ISBN 978-0-262-27083-0. OCLC 676697295 .CS1 maint: others (link)
^ Эрдели, А. (1956). Асимптотические разложения . ISBN 978-0-486-60318-6.
^ EC Titchmarsh Теория дзета-функции (Oxford, Clarendon Press, 1951)
^ См., Например, «Новая оценка G ( n ) в проблеме Варинга» (рус.). Доклады АН СССР 5, № 5-6 (1934), 249–253. Переведено на английский язык: Избранные произведения / Иван Матвеевич Виноградов; подготовлен Математическим институтом им. В. А. Стеклова АН СССР к 90-летию со дня рождения. Спрингер-Верлаг, 1985.

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

В структуре данных Викибука есть страница по теме: Нотация большого О

Викиверситет решил проблему MyOpenMath, используя нотацию Big-O

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

[Bachmann-1] Бахманн, Пауль (1894). Analytische Zahlentheorie [ Аналитическая теория чисел ] (на немецком языке). 2 . Лейпциг: Тойбнер.

[Landau-2] Ландау, Эдмунд (1909). Handbuch der Lehre von der Verteilung der Primzahlen [ Справочник по теории распределения простых чисел ] (на немецком языке). Лейпциг: BG Teubner. п. 883.

[quantumcomplexity-3] Мор, Остин. «Квантовые вычисления в теории сложности и теории вычислений» (PDF) . п. 2 . Проверено 7 июня 2014 .

[LandauO-4] Ландау, Эдмунд (1909). Handbuch der Lehre von der Verteilung der Primzahlen [ Справочник по теории распределения простых чисел ] (на немецком языке). Лейпциг: BG Teubner. п. 31.

[5] Майкл Сипсер (1997). Введение в теорию вычислений . Бостон / Массачусетс: PWS Publishing Co. Здесь: Def.7.2, стр.227

[6] Например,не определено в. $\log(n)$ $n=0$

[clrs3-7] а б Кормен, Томас Х .; Leiserson, Charles E .; Ривест, Рональд Л. (2009). Введение в алгоритмы (3-е изд.). Кембридж / Массачусетс: MIT Press. п. 45 . ISBN 978-0-262-53305-8. Поскольку θ ( g ( n )) - это множество, мы могли бы написать « f ( n ) ∈ θ ( g ( n ))», чтобы указать, что f ( n ) является членом θ ( g ( n )). Вместо этого мы обычно будем писать f ( n ) = θ ( g ( n )), чтобы выразить то же понятие. Вы можете быть сбиты с толку, потому что мы таким образом злоупотребляем равенством, но позже в этом разделе мы увидим, что это имеет свои преимущества.

[8] Кормен, Томас; Лейзерсон, Чарльз; Ривест, Рональд; Стейн, Клиффорд (2009). Введение в алгоритмы (третье изд.). Массачусетский технологический институт. п. 53 .

[9] Хауэлл, Родни. «Об асимптотической записи с несколькими переменными» (PDF) . Проверено 23 апреля 2015 .

[10] Н. де Брейна (1958). Асимптотические методы анализа . Амстердам: Северная Голландия. С. 5–7. ISBN 978-0-486-64221-5.

[Concrete_Mathematics-11] Грэм, Рональд ; Кнут, Дональд ; Паташник, Орен (1994). Конкретная математика (2-е изд.). Ридинг, Массачусетс: Аддисон – Уэсли. п. 446. ISBN. 978-0-201-55802-9.

[12] Дональд Кнут (июнь – июль 1998 г.). «Научите математическому анализу с большой буквы O» (PDF) . Уведомления Американского математического общества . 45 (6): 687. ( Полная версия )

[KnuthArt-13] Дональд Э. Кнут, Искусство компьютерного программирования. Vol. 1. Фундаментальные алгоритмы, третье издание, Addison Wesley Longman, 1997. Раздел 1.2.11.1.

[ConcreteMath-14] Рональд Л. Грэм, Дональд Э. Кнут и Орен Паташник, Конкретная математика: Фонд компьютерных наук (2-е изд.) , Аддисон-Уэсли, 1994. Раздел 9.2, с. 443.

[15] Сиварам Амбикасаран и Эрик Дарв,Быстрый прямой решатель для частично иерархически полуразделяемых матриц, J. Scientific Computing 57 (2013), нет. 3, 477–501. ${\mathcal {O}}(N\log N)$

[16] Сакет Саураб и Мейрав Зехави,-Max-Cut:алгоритм времени и полиномиальное ядро, Algorithmica 80 (2018), нет. 12, 3844–3860. $(k,n-k)$ ${\mathcal {O}}^{*}(2^{p})$

[Landausmallo-17] Ландау, Эдмунд (1909). Handbuch der Lehre von der Verteilung der Primzahlen [ Справочник по теории распределения простых чисел ] (на немецком языке). Лейпциг: BG Teubner. п. 61.

[Introduction_to_Algorithms-18] Томас Х. Кормен и др., 2001, Введение в алгоритмы, второе издание ^{[ необходима страница ]}

[HL-19] а б в Харди, GH; Литтлвуд, Дж. Э. (1914). «Некоторые проблемы диофантова приближения. Часть II. Тригонометрические ряды, связанные с эллиптическими ϑ-функциями» . Acta Mathematica . 37 : 225. DOI : 10.1007 / BF02401834 .

[HL2-20] Г. Х. Харди и Дж. Литтлвуд, «Вклад в теорию дзета-функции Римана и теорию распределения простых чисел», Acta Mathematica , vol. 41, 1916 г.

[landau-21] Э. Ландау, "Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV." Nachr. Геселл. Wiss. Gött. Math-Phys. Kl. 1924, 137–150.

[Ivic-22] Александр Ивич. Дзета-функция Римана, глава 9. John Wiley & Sons 1985.

[23] Джеральд Тененбаум, Введение в аналитическую и вероятностную теорию чисел, Глава I.5. Американское математическое общество, Провиденс, Род-Айленд, 2015.

[knuth-24] Кнут, Дональд (апрель – июнь 1976 г.). «Большой Омикрон, и большая Омега, и большая Тета» (PDF) . Новости SIGACT : 18–24.

[Balcázar-25] Balcazar, José L .; Габарро, Хоаким. «Неоднородные классы сложности, заданные нижними и верхними границами» (PDF) . RAIRO - Теоретическая информатика и приложения - Теория информатики и приложения . 23 (2): 180. ISSN 0988-3754 . Проверено 14 марта 2017 года .

[Cucker-26] Cucker, Фелипе; Бюргиссер, Питер (2013). «A.1 Big Oh, Little Oh и другие сравнения». Условие: геометрия численных алгоритмов . Берлин, Гейдельберг: Springer. С. 467–468. DOI : 10.1007 / 978-3-642-38896-5 . ISBN 978-3-642-38896-5.

[Wild-27] Витаньи, Пол ; Меертенс, Ламберт (апрель 1985 г.). «Большая Омега против диких функций» (PDF) . Новости ACM SIGACT . 16 (4): 56–59. CiteSeerX 10.1.1.694.3072 . DOI : 10.1145 / 382242.382835 .

[28] Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990]. Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 41–50. ISBN 0-262-03293-7.

[29] например, он опущен в: Hildebrand, AJ "Asymptotic Notations" (PDF) . Кафедра математики. Асимптотические методы анализа . Math 595, осень 2009 г. Урбана, Иллинойс: Университет Иллинойса . Проверено 14 марта 2017 года .

[30] Кормен, Томас Х .; Leiserson, Charles E .; Ривест, Рональд Л. (2009). Введение в алгоритмы (3-е изд.). Кембридж / Массачусетс: MIT Press. п. 47. ISBN 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 ) для всехп ≥ п ₀ }

[31] Кормен, Томас Х .; Leiserson, Charles E .; Ривест, Рональд Л. (2009). Введение в алгоритмы (3-е изд.). Кембридж / Массачусетс: MIT Press. п. 49 . ISBN 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 ). Использование асимптотических обозначений таким образом может помочь устранить несущественные детали и беспорядок в уравнении.

[32] Введение в алгоритмы . Кормен, Томас Х. (Третье изд.). Кембридж, Массачусетс: MIT Press. 2009. с. 63 . ISBN 978-0-262-27083-0. OCLC 676697295 .CS1 maint: others (link)

[33] Эрдели, А. (1956). Асимптотические разложения . ISBN 978-0-486-60318-6.

[titchmarsh-34] EC Titchmarsh Теория дзета-функции (Oxford, Clarendon Press, 1951)

[35] См., Например, «Новая оценка G ( n ) в проблеме Варинга» (рус.). Доклады АН СССР 5, № 5-6 (1934), 249–253. Переведено на английский язык: Избранные произведения / Иван Матвеевич Виноградов; подготовлен Математическим институтом им. В. А. Стеклова АН СССР к 90-летию со дня рождения. Спрингер-Верлаг, 1985.

[1]