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

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

Обозначение Big O математическая запись, описывающая ограничивающее поведение из функция когда аргумент стремится к определенному значению или бесконечности. В соответствии с Дональд Кнут, обозначение ${\displaystyle O(f(n))}$ «обозначает количество, которое явно не известно, за исключением того, что его величина не слишком велика».^[1] Big O является членом семейство обозначений изобретен Пол Бахманн,^[2] Эдмунд Ландау,^[3] и другие, вместе называемые Обозначения Бахмана – Ландау или же асимптотическая запись.

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

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

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

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

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

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

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

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

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

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

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

если есть положительные числа ${\displaystyle \delta }$ и M такой, что для всех Икс с ${\displaystyle 0<|x-a|<\delta }$,

${\displaystyle |f(x)|\leq Mg(x).}$

В качестве грамм(Икс) выбирается ненулевым для значений Икс достаточно близко к а, оба этих определения можно объединить с помощью предел высшего:

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

если

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

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

Пример

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

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

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

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

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

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

так

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

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

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

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

В обоих приложениях функция грамм(Икс) появляясь в О(...) обычно выбирается как можно более простым, опуская постоянные множители и члены более низкого порядка.

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

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

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

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

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

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

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

или же

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

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

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

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

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

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

Характеристики

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

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

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

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

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

Товар

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

${\displaystyle f\cdot O(g)=O(fg)}$

Сумма

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

Из этого следует ${\displaystyle f_{1}=O(g){\text{ and }}f_{2}=O(g)\Rightarrow f_{1}+f_{2}\in O(g)}$, что обозначает ${\displaystyle O(g)}$ это выпуклый конус.

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

Позволять k быть постоянным. Потом:

${\displaystyle O(|k|g)=O(g)}$ если k отличен от нуля.

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

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

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

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

если и только если^[9]

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

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

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

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

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

куда грамм(п,м) определяется

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

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

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

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

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

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

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

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

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

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

Заявление "ж(Икс) является О(грамм(Икс)) ", как определено выше, обычно записывается как ж(Икс) = О(грамм(Икс)). Некоторые считают это злоупотребление обозначениями, поскольку использование знака равенства может ввести в заблуждение, так как предполагает симметрию, которой нет в этом утверждении. В качестве де Брюйн говорит, О(Икс) = О(Икс²) верно, но О(Икс²) = О(Икс) не является.^[11] Knuth описывает такие утверждения как «одностороннее равенство», поскольку, если бы стороны могли быть поменяны местами, «мы могли бы вывести такие нелепые вещи, как п = п² от личности п = О(п²) и п² = О(п²)."^[12]

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

Верстка

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

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

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

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

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

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

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

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

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

"Little o" перенаправляется сюда. Для бейсболиста см. Омар Вискель.

Интуитивно утверждение "ж(Икс) является о(грамм(Икс))" (читать "ж(Икс) мало грамм(Икс)") Значит это грамм(Икс) растет намного быстрее, чем ж(Икс). Пусть по-прежнему ж быть вещественной или комплексной функцией и грамм вещественнозначная функция, обе определены на некотором неограниченном подмножестве положительных действительные числа, так что грамм(Икс) строго положительна для всех достаточно больших значений Икс. Один пишет

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle f(x)=\Omega (g(x))}$ в качестве ${\displaystyle x\rightarrow a,}$,

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

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

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

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

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

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

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

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

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

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

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

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

У нас есть

${\displaystyle \sin x=\Omega (1)}$ в качестве ${\displaystyle x\rightarrow \infty ,}$

а точнее

${\displaystyle \sin x=\Omega _{\pm }(1)}$ в качестве ${\displaystyle x\rightarrow \infty .}$

У нас есть

${\displaystyle \sin x+1=\Omega (1)}$ в качестве ${\displaystyle x\rightarrow \infty ,}$

а точнее

${\displaystyle \sin x+1=\Omega _{+}(1)}$ в качестве ${\displaystyle x\rightarrow \infty ;}$

тем не мение

${\displaystyle \sin x+1\not =\Omega _{-}(1)}$ в качестве ${\displaystyle x\rightarrow \infty .}$

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

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

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

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

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

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

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

Информатика использует большие О, большая тета Θ, маленькая о, обозначения маленькой омеги ω и большой омеги Кнута.^[26] Аналитическая теория чисел часто использует большой О, маленький о, Большая Омега Ω Харди – Литтлвуда (с нижними индексами +, - или ± или без них) и ${\displaystyle \sim }$ обозначения.^[20] Маленькие обозначения омега ω не так часто используются в анализе.^[27]

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

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

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

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

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

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

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

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

В их книге Введение в алгоритмы, Кормен, Leiserson, Ривест и Stein рассмотреть набор функций ж которые удовлетворяют

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

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

${\displaystyle O(g)=\{f:}$ существуют положительные постоянные c и ${\displaystyle n_{0}}$ такой, что ${\displaystyle 0\leq f(n)\leq cg(n)}$ для всех ${\displaystyle n\geq n_{0}\}}$.^[28]

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

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

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

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

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

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

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

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

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

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

который является отношение эквивалентности и понятие более ограничительное, чем отношения "ж (грамм) "сверху. (сводится к lim ж / грамм = 1, если ж и грамм положительные действительные функции.) Например, 2Икс (Икс), но 2Икс − Икс не является о(Икс).

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Дональд Э. Кнут, Искусство программирования. Vol. 1. Фундаментальные алгоритмы, третье издание, Addison Wesley Longman, 1997. Раздел 1.2.11.1.
2. Бахманн, Пауль (1894). Analytische Zahlentheorie [Аналитическая теория чисел] (на немецком). 2. Лейпциг: Тойбнер.
3. Ландау, Эдмунд (1909). Handbuch der Lehre von der Verteilung der Primzahlen [Справочник по теории распределения простых чисел] (на немецком). Лейпциг: Б. Г. Тойбнер. п. 883.
4. Мор, Остин. «Квантовые вычисления в теории сложности и теории вычислений» (PDF). п. 2. Получено 7 июн 2014.
5. Ландау, Эдмунд (1909). Handbuch der Lehre von der Verteilung der Primzahlen [Справочник по теории распределения простых чисел] (на немецком). Лейпциг: B.G. Teubner. п. 31.
6. Майкл Сипсер (1997). Введение в теорию вычислений. Бостон / Массачусетс: PWS Publishing Co. Здесь: Def.7.2, стр.227
7. Например, ${\displaystyle \log(n)}$ не определено в ${\displaystyle n=0}$.
8. Cormen, Thomas H .; Leiserson, Charles E .; Ривест, Рональд Л. (2009). Введение в алгоритмы (3-е изд.). Кембридж / Массачусетс: MIT Press. п.45. ISBN  978-0-262-53305-8. Потому что θ(грамм(п)) это набор, мы могли бы написать "ж(п) ∈ θ(грамм(п)) ", чтобы указать, что ж(п) является членом θ(грамм(п)). Вместо этого мы обычно пишем ж(п) = θ(грамм(п)), чтобы выразить то же понятие. Вы можете быть сбиты с толку, потому что мы таким образом злоупотребляем равенством, но позже в этом разделе мы увидим, что это имеет свои преимущества.
9. Кормен, Томас; Лейзерсон, Чарльз; Ривест, Рональд; Стейн, Клиффорд (2009). Введение в алгоритмы (Третье изд.). Массачусетский технологический институт. п.53.
10. Хауэлл, Родни. «Об асимптотической записи с несколькими переменными» (PDF). Получено 2015-04-23.
11. Н. Г. де Брёйн (1958). Асимптотические методы анализа.. Амстердам: Северная Голландия. С. 5–7. ISBN  978-0-486-64221-5.
12. Грэм, Рональд; Кнут, Дональд; Паташник, Орен (1994). Конкретная математика (2-е изд.). Ридинг, Массачусетс: Аддисон – Уэсли. п. 446. ISBN  978-0-201-55802-9.
13. Дональд Кнут (июнь – июль 1998 г.). "Teach Calculus with Big O" (PDF). Уведомления Американского математического общества. 45 (6): 687. (Unabridged version )
14. Tom (24 June 2014). "Big O and related notations in LaTeX". texblog.
15. Ландау, Эдмунд (1909). Handbuch der Lehre von der Verteilung der Primzahlen [Handbook on the theory of the distribution of the primes] (на немецком). Лейпциг: Б. Г. Тойбнер. п. 61.
16. Thomas H. Cormen et al., 2001, Introduction to Algorithms, Second Edition^{[страница нужна ]}
17. Харди, Г. Х .; Littlewood, J. E. (1914). "Some problems of diophantine approximation: Part II. The trigonometrical series associated with the elliptic ϑ-functions". Acta Mathematica. 37: 225. Дои:10.1007/BF02401834.
18. G. H. Hardy and J. E. Littlewood, « Contribution to the theory of the Riemann zeta-function and the theory of the distribution of primes », Acta Mathematica, т. 41, 1916.
19. E. Landau, "Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV." Nachr. Гезелл. Wiss. Gött. Math-phys. Kl. 1924, 137–150.
20. Aleksandar Ivić. The Riemann zeta-function, chapter 9. John Wiley & Sons 1985.
21. Gérald Tenenbaum, Introduction to analytic and probabilistic number theory, Chapter I.5. American Mathematical Society, Providence RI, 2015.
22. Knuth, Donald (April–June 1976). "Big Omicron and big Omega and big Theta" (PDF). Новости SIGACT: 18–24.
23. Balcázar, José L.; Gabarró, Joaquim. "Nonuniform complexity classes specified by lower and upper bounds" (PDF). RAIRO – Theoretical Informatics and Applications – Informatique Théorique et Applications. 23 (2): 180. ISSN  0988-3754. Получено 14 марта 2017.
24. Cucker, Felipe; Bürgisser, Peter (2013). "A.1 Big Oh, Little Oh, and Other Comparisons". Condition: The Geometry of Numerical Algorithms. Berlin, Heidelberg: Springer. С. 467–468. Дои:10.1007/978-3-642-38896-5. ISBN  978-3-642-38896-5.
25. Vitányi, Paul; Меертенс, Ламберт (Апрель 1985 г.). "Big Omega versus the wild functions" (PDF). Новости ACM SIGACT. 16 (4): 56–59. CiteSeerX  10.1.1.694.3072. Дои:10.1145/382242.382835.
26. Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001) [1990]. Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 41–50. ISBN  0-262-03293-7.
27. for example it is omitted in: Хильдебранд, А.Дж. "Asymptotic Notations" (PDF). Кафедра математики. Asymptotic Methods in Analysis. Math 595, Fall 2009. Urbana, IL: University of Illinois. Получено 14 марта 2017.
28. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (2009). Введение в алгоритмы (3-е изд.). Кембридж / Массачусетс: MIT Press. п. 47. ISBN  978-0-262-53305-8. When we have only an asymptotic upper bound, we use O-notation. For a given function грамм(п), we denote by О(грамм(п)) (pronounced "big-oh of грамм из п" or sometimes just "oh of грамм из п") the set of functions О(грамм(п)) = { ж(п) : there exist positive constants c и п₀ such that 0 ≤ ж(п) ≤ cg(п) for all п ≥ п₀}
29. Cormen,Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (2009). Введение в алгоритмы (3-е изд.). Кембридж / Массачусетс: MIT Press. п.49. ISBN  978-0-262-53305-8. When the asymptotic notation stands alone (that is, not within a larger formula) on the right-hand side of an equation (or inequality), as in n = O(n²), we have already defined the equal sign to mean set membership: n ∈ O(n²). In general, however, when asymptotic notation appears in a formula, we interpret it as standing for some anonymous function that we do not care to name. For example, the formula 2п² + 3п + 1 = 2п² + θ(п) means that 2п² + 3п + 1 = 2п² + ж(п), куда ж(п) is some function in the set θ(п). In this case, we let ж(п) = 3п + 1, which is indeed in θ(п). Using asymptotic notation in this manner can help eliminate inessential detail and clutter in an equation.
30. Введение в алгоритмы. Кормен, Томас Х. (Третье изд.). Кембридж, Массачусетс: MIT Press. 2009. с.63. ISBN  978-0-262-27083-0. OCLC  676697295.
31. Erdelyi, A. (1956). Asymptotic Expansions. ISBN  978-0-486-60318-6.
32. E. C. Titchmarsh, The Theory of the Riemann Zeta-Function (Oxford; Clarendon Press, 1951)
33. See for instance "A new estimate for грамм(п) in Waring's problem" (Russian). Doklady Akademii Nauk SSSR 5, No 5-6 (1934), 249–253. Translated in English in: Selected works / Ivan Matveevič Vinogradov; prepared by the Steklov Mathematical Institute of the Academy of Sciences of the USSR on the occasion of his 90th birthday. Springer-Verlag, 1985.

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

• Харди, Г. Х. (1910). Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond. Издательство Кембриджского университета.
• Кнут, Дональд (1997). "1.2.11: Asymptotic Representations". Fundamental Algorithms. The Art of Computer Programming. 1 (3-е изд.). Addison–Wesley. ISBN  978-0-201-89683-1.
• Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001). "3.1: Asymptotic notation". Введение в алгоритмы (2-е изд.). MIT Press and McGraw–Hill. ISBN  978-0-262-03293-3.
• Сипсер, Майкл (1997). Введение в теорию вычислений. PWS Publishing. стр.226 –228. ISBN  978-0-534-94728-6.
• Avigad, Jeremy; Donnelly, Kevin (2004). Formalizing O notation in Isabelle/HOL (PDF). International Joint Conference on Automated Reasoning. Дои:10.1007/978-3-540-25984-8_27.
• Black, Paul E. (11 March 2005). Black, Paul E. (ed.). "big-O notation". Словарь алгоритмов и структур данных. U.S. National Institute of Standards and Technology. Получено 16 декабря, 2006.
• Black, Paul E. (17 December 2004). Black, Paul E. (ed.). "little-o notation". Словарь алгоритмов и структур данных. U.S. National Institute of Standards and Technology. Получено 16 декабря, 2006.
• Black, Paul E. (17 December 2004). Black, Paul E. (ed.). "Ω". Словарь алгоритмов и структур данных. U.S. National Institute of Standards and Technology. Получено 16 декабря, 2006.
• Black, Paul E. (17 December 2004). Black, Paul E. (ed.). "ω". Словарь алгоритмов и структур данных. U.S. National Institute of Standards and Technology. Получено 16 декабря, 2006.
• Black, Paul E. (17 December 2004). Black, Paul E. (ed.). "Θ". Словарь алгоритмов и структур данных. U.S. National Institute of Standards and Technology. Получено 16 декабря, 2006.

внешняя ссылка

• Growth of sequences — OEIS (Online Encyclopedia of Integer Sequences) Wiki
• Introduction to Asymptotic Notations^{[постоянная мертвая ссылка ]}
• Landau Symbols
• Big-O Notation – What is it good for
• Big O Notation explained in plain english
• An example of Big O in accuracy of central divided difference scheme for first derivative
• A Gentle Introduction to Algorithm Complexity Analysis