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

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

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

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

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

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

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

Позволять $f$, функция, которую нужно оценить, является действительной или комплекснозначной функцией, и пусть $g$, функция сравнения, является вещественнозначной функцией. Пусть обе функции определены на некотором неограниченном подмножестве положительных действительных чисел и $g(x)$ быть строго положительным для всех достаточно больших значений $x$. Один пишет $$f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to \infty$$и это читается" $f(x)$ большой О из $g(x)$«если абсолютное значение $f(x)$ не более чем положительное постоянное кратное $g(x)$ для всех достаточно больших значений $x$. То есть, $f(x)=O{\bigl (}g(x){\bigr )}$ если существует положительное действительное число $M$ и реальное число $x_{0}$ такой, что $$|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$$если существуют положительные числа $\delta$ и $M$ такой, что для всех определенных $x$ с $0<|x-a|<\delta$, $$|f(x)|\leq Mg(x).$$Как $g(x)$ выбирается строго положительным для таких значений $x$оба этих определения можно унифицировать, используя верхний предел : $$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 .$$И в обоих этих определениях предельная точка $a$ (ли $\infty$ или нет) является точкой кластера доменов $f$ и $g$, я. е., в каждом районе $a$ должно быть бесконечно много общих точек. Более того, как указано в статье о пределе нижнего и верхнего предела , $\textstyle \limsup _{x\to a}$ (по крайней мере, на расширенной линии действительных чисел ) всегда существует.

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

Пример

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

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

Например, пусть f ( x ) = 6 x ⁴ − 2 х ³ + 5 , и предположим, что мы хотим упростить эту функцию, используя обозначение O , чтобы описать скорость ее роста, когда x приближается к бесконечности. Эта функция представляет собой сумму трёх слагаемых: 6 x ⁴ , −2 х ³ , и 5 . Из этих трех слагаемых наибольшую скорость роста имеет тот, у которого наибольший показатель степени зависит от x , а именно 6 x ⁴ . Теперь можно применить второе правило: 6 х ⁴ является произведением 6 и x ⁴ в котором первый множитель не зависит от x . Отсутствие этого фактора приводит к упрощенной форме x ⁴ . Таким образом, мы говорим, что f ( x ) является «большим O» x ⁴ . Математически мы можем записать f ( x ) = O ( x ⁴ ) . Подтвердить этот расчет можно с помощью формального определения: пусть f ( x ) = 6 x ⁴ − 2 х ³ + 5 и г ( х ) = х ⁴ . Применяя формальное определение , данное выше, утверждение о том, что f ( x ) = O ( x ⁴ ) эквивалентно его расширению, $$|f(x)|\leq Mx^{4}$$для некоторого подходящего выбора действительного числа x ₀ и положительного действительного числа M и для всех x > x ₀ . Чтобы доказать это, пусть x ₀ = 1 и M = 13 . Тогда для всех x > x ₀ : $${\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 становится большим, n ² член станет доминировать, так что всеми остальными членами можно будет пренебречь — например, когда n = 500 , член 4 n ² в 1000 раз больше 2n члена . Игнорирование последнего оказало бы незначительное влияние на значение выражения для большинства целей. Кроме того, коэффициенты становятся нерелевантными, если мы сравниваем их с любым другим порядком выражения, например с выражением, содержащим термин n ³ или н ⁴ . Даже если T ( n ) = 1 000 000 n ² , если U ( п ) = п ³ , последнее всегда будет превышать первое, как только n станет больше 1 000 000 , а именно. Т (1 000 000) = 1 000 000 ³ = U (1 000 000) . Кроме того, количество шагов зависит от деталей модели машины, на которой работает алгоритм, но разные типы машин обычно различаются только на постоянный коэффициент количества шагов, необходимых для выполнения алгоритма. Таким образом, большая запись О отражает то, что осталось: мы пишем либо

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

или

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

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

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

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

${\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 ^х − (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 ^с ) и O ( c ^н ) очень разные. Если c больше единицы, то последняя растет гораздо быстрее. Функция, которая растет быстрее, чем n ^с для любого c называется суперполиномиальным . Та, которая растет медленнее, чем любая показательная функция вида c ^н называется субэкспоненциальным . Алгоритму может потребоваться время, которое является как суперполиномиальным, так и субэкспоненциальным; примеры этого включают самые быстрые известные алгоритмы факторизации целых чисел и функцию n ^{войти в систему} .

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

Изменение единиц измерения может повлиять или не повлиять на порядок результирующего алгоритма. Изменение единиц эквивалентно умножению соответствующей переменной на константу, где бы она ни появлялась. Например, если алгоритм выполняется в порядке n ² , замена n на cn означает, что алгоритм работает в порядке c ² н ² , а большое обозначение O игнорирует константу c ² . Это можно записать как c ² н ² = О( п ² ) . Однако если алгоритм работает в порядке 2 ^н , замена n на cn дает 2 ^CN = (2 ^с ) ^н . Это не эквивалентно 2 ^н в общем. Изменение переменных также может повлиять на порядок результирующего алгоритма. Например, если время выполнения алгоритма равно O ( n ), если оно измерено в терминах числа n цифр , входного числа x то время его выполнения равно O (log x ), если оно измерено как функция входного числа x. самого , потому что 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})$ и $f_{2}=O(g_{2})$ затем $f_{1}+f_{2}=O(\max(g_{1},g_{2}))$. Отсюда следует, что если $f_{1}=O(g)$ и $f_{2}=O(g)$ затем $f_{1}+f_{2}\in O(g)$. Другими словами, это второе утверждение говорит, что $O(g)$ представляет собой выпуклый конус .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обозначение 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 ³ + О ( н ² ) . Здесь члены 2 n + 10 включены в состав быстрорастущего O ( n ² ). Опять же, такое использование игнорирует часть формального значения символа «=", но позволяет использовать большую букву О в качестве своего рода удобного заполнителя.

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

В более сложном использовании O (·) может появляться в разных местах уравнения, даже несколько раз с каждой стороны. Например, для $n\to \infty$: $${\begin{aligned}(n+1)^{2}&=n^{2}+O(n),\\(n+O(n^{1/2}))\cdot (n+O(\log n))^{2}&=n^{3}+O(n^{5/2}),\\n^{O(1)}&=O(e^{n}).\end{aligned}}$$Смысл таких утверждений следующий: для любых функций, удовлетворяющих каждому O (·) в левой части, существуют некоторые функции, удовлетворяющие каждому O (·) в правой части, такие, что подстановка всех этих функций в уравнение дает две стороны равны. Например, третье уравнение выше означает: «Для любой функции f ( n ) = O (1) существует некоторая функция g ( n ) = O ( e ^н ) такой, что n ^{ж ( п )} = g ( n ).» С точки зрения «нотации множества» выше, это означает, что класс функций, представленный левой частью, является подмножеством класса функций, представленных правой частью. При этом используйте «= " является формальным символом, который, в отличие от обычного использования "=", не является симметричным отношением . Так, например, n ^{О (1)} = О ( и ^н ) не подразумевает ложное утверждение O ( e ^н ) = п ^{О (1)} .

верстка

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

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

Дополнительная информация: Временная сложность § Таблица распространенных временных сложностей.

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

Обозначения	Имя	Пример
$O(1)$	постоянный	Нахождение медианного значения для отсортированного массива чисел; Расчет $(-1)^{n}$; постоянного размера Использование справочной таблицы
$O(\alpha (n))$	обратная функция Аккермана	Амортизированная сложность каждой операции для структуры данных Disjoint-set.
$O(\log \log n)$	двойной логарифмический	Среднее количество сравнений, потраченных на поиск элемента с использованием интерполяционного поиска в отсортированном массиве равномерно распределенных значений
$O(\log n)$	логарифмический	Поиск элемента в отсортированном массиве с помощью двоичного поиска или сбалансированного дерева поиска , а также всех операций в биномиальной куче.
$O((\log n)^{c})$ ${\textstyle c>1}$	полилогарифмический	Упорядочение цепочек матриц можно решить за полилогарифмическое время на параллельной машине с произвольным доступом .
$O(n^{c})$ ${\textstyle 0<c<1}$	дробная мощность	Поиск в дереве kd
$O(n)$	линейный	Поиск элемента в несортированном списке или в несортированном массиве; добавление двух n -битных целых чисел методом пульсирующего переноса
$O(n\log ^{*}n)$	n лог-звезда 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!)$	линейный , логлинейный, квазилинейный или « n log n »	Выполнение быстрого преобразования Фурье ; самая быстрая сортировка сравнения ; пирамидальная сортировка и сортировка слиянием
$O(n^{2})$	квадратичный	Умножение двух n -значных чисел по школьному умножению ; простые алгоритмы сортировки, такие как пузырьковая сортировка , сортировка выбором и сортировка вставкой ; (наихудший случай) привязан к некоторым обычно более быстрым алгоритмам сортировки, таким как быстрая сортировка , Шеллсорт и сортировка по дереву.
$O(n^{c})$	полиномиальный или алгебраический	Парсинг древовидной грамматики ; максимальное совпадение для двудольных графов ; нахождение определителя с помощью LU-разложения
$L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ ${\textstyle 0<\alpha <1}$	L-нотация или субэкспоненциальная	Факторизация числа с использованием квадратичного сита или сита числового поля
$O(c^{n})$ ${\textstyle 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 широко используется в информатике. Вместе с некоторыми другими родственными обозначениями он образует семейство обозначений Бахмана – Ландау.

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

«Маленький о» перенаправляется сюда. Чтобы узнать о бейсболисте, см. Омар Вискель .

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

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

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

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

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

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

Разница между определением обозначения big-O и определением small-o заключается в том, что первое должно быть верным хотя бы для одной константы M , а второе должно выполняться для каждой положительной константы ε , какой бы маленькой она ни была. Таким образом, нотация small-o делает более сильное утверждение, чем соответствующее обозначение big-O: каждая функция, которая является small-o для g , также является big-O для g , но не каждая функция, которая является big-O для 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$ (и именно так Ландау первоначально определял нотацию «little-o»).

Little-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\to a$,

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

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

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

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

$f(x)=\Omega (g(x))$ как $x\to \infty$ если $\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$

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

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

$f(x)=\Omega _{R}(g(x))$ как $x\to \infty$ если $\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$;

$f(x)=\Omega _{L}(g(x))$ как $x\to \infty$ если $\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$

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

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

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

У нас есть

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

и точнее

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

У нас есть

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

и точнее

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

однако

$\sin x+1\not =\Omega _{-}(1)$ как $x\to \infty .$

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

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

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

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

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

Обозначения	Имя	Описание	Формальное определение	Определение предела
$f(n)=o(g(n))$	Маленький О; Маленький Ой; Маленький О; Маленький Ох	f асимптотически доминирует g (для любого постоянного множителя $k$)	$\forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon |f(n)|<k\,g(n)$	$\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=0$
$f(n)=O(g(n))$	Большой О; Большой Ой; Большой Омикрон	$|f|$ асимптотически ограничена сверху величиной g (с точностью до постоянного множителя $k$)	$\exists k>0\,\exists n_{0}\,\forall n>n_{0}\colon |f(n)|\leq k\,g(n)$	$\limsup _{n\to \infty }{\frac {f(n)}{g(n)}}<\infty$
$f(n)\asymp g(n)$ (обозначение Харди) или $f(n)=\Theta (g(n))$ (обозначение Кнута)	Того же порядка, что и (Харди); Большая Тета (Кнут)	f асимптотически ограничен g как выше (с постоянным множителем $k_{2}$) и ниже (с постоянным коэффициентом $k_{1}$)	$\exists k_{1}>0\,\exists k_{2}>0\,\exists n_{0}\,\forall n>n_{0}\colon$ $k_{1}\,g(n)\leq f(n)\leq k_{2}\,g(n)$	$f(n)=O(g(n))$ и $g(n)=O(f(n))$
$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 асимптотически	$\exists k>0\,\exists n_{0}\,\forall n>n_{0}\colon f(n)\geq k\,g(n)$	$\liminf _{n\to \infty }{\frac {f(n)}{g(n)}}>0$
$f(n)=\omega (g(n))$	Малая Омега; Маленькая Омега	f доминирует над g асимптотически	$\forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon f(n)>k\,g(n)$	$\lim _{n\to \infty }{\frac {f(n)}{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\,g(n)$	$\limsup _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}>0$

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

Информатика использует большие $O$, большая Тета $\Theta$, маленький $o$, маленькая омега $\omega$ и большая Омега Кнута $\Omega$ обозначения. Аналитическая теория чисел часто использует большие $O$, маленький $o$, Харди $\asymp$, Большая Омега Харди-Литтлвуда $\Omega$ (с индексами +, - или ± или без них) и $\sim$ обозначения. Маленькая омега $\omega$ обозначения не используются так часто в анализе.

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

Дополнительная информация: Анализ алгоритмов.

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

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

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

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

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

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

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

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

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

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

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

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

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

Другое обозначение, иногда используемое в информатике, — Õ (читай soft-O ), которое скрывает полилогарифмические коэффициенты. Используются два определения: некоторые авторы используют f ( n ) = Õ ( g ( n )) как сокращение для f ( n ) = O ( g ( n ) log ^к n ) для некоторых k , в то время как другие используют его как сокращение для f ( n ) = O ( g ( n ) log ^к г ( п )) . Когда g ( n ) является полиномом по n , разницы нет; однако последнее определение позволяет сказать, например, что $n2^{n}={\tilde {O}}(2^{n})$ хотя первое определение допускает $\log ^{k}n={\tilde {O}}(1)$ для любой константы 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 не обязательно принимают свои значения в одном и том же пространстве. обобщение на функции g, принимающие значения в любой топологической группе. Также возможно .«Предельный процесс» x → xo _{, т. е} также можно обобщить, введя произвольную базу фильтров . на ориентированные сети f и g . Обозначение o можно использовать для определения производных и дифференцируемости в довольно общих пространствах, а также (асимптотической) эквивалентности функций:

$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 (« аналитическая теория чисел »). Теоретик чисел Эдмунд Ландау принял его и, таким образом, был вдохновлен ввести в 1909 году обозначение o; поэтому оба теперь называются символами Ландау. Эти обозначения использовались в прикладной математике в 1950-х годах для асимптотического анализа. Символ $\Omega$ (в смысле «не является о ») было введено в 1914 году Харди и Литтлвудом. Харди и Литтлвуд также ввели в 1916 году символы $\Omega _{R}$ («право») и $\Omega _{L}$ ("левый"), предшественники современных символов $\Omega _{+}$ («не меньше маленькой буквы») и $\Omega _{-}$ («не больше маленькой буквы»). Таким образом, символы Омеги (с их первоначальным значением) иногда также называют «символами Ландау». Это обозначение $\Omega$ стал широко использоваться в теории чисел, по крайней мере, с 1950-х годов.

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

В 1970-х годах большая буква О была популяризирована в информатике Дональдом Кнутом , который предложил другое обозначение. $f(x)=\Theta (g(x))$ для Харди $f(x)\asymp g(x)$и предложил другое определение обозначения Харди и Литтлвуда Омега.

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

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

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

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

$f\ll g\iff f=O(g),$

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

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

См. также

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

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

• Харди, 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.
• Нежное введение в анализ сложности алгоритмов