Обозначение Big O - Википедия - Big O notation

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

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

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

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

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

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

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

${ Displaystyle е (х) = О { bigl (} г (х) { bigr)} quad { text {as}} х к infty}$

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

${ displaystyle | f (x) | leq Mg (x) quad { text {для всех}} x geq x_ {0}.}$

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

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

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

${ Displaystyle е (х) = О { bigl (} г (х) { bigr)} quad { text {as}} х к а}$

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

${ Displaystyle | е (х) | leq Mg (x).}$

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

${ Displaystyle е (х) = О { bigl (} г (х) { bigr)} quad { text {as}} х к а}$

если

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

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

Пример

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

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

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

${ Displaystyle | е (х) | leq Mx ^ {4}}$

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

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

так

${ 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 Т (п) = О (п ^ {2})}$

или же

${ Displaystyle Т (п) в О (п ^ {2})}$

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

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

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

${ displaystyle { begin {align} e ^ {x} & = 1 + x + { frac {x ^ {2}} {2!}} + { frac {x ^ {3}} {3!}} + { frac {x ^ {4}} {4!}} + dotsb & { text {для всех}} 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 конец {выровнено}}}$

Второе выражение (с О(Икс³)) означает абсолютное значение ошибки е^Икс − (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 е 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 О (г)}$ это выпуклый конус.

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

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

${ Displaystyle О (| К | г) = О (г)}$ если k отличен от нуля.

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

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

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

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

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

${ displaystyle exists M exists C> 0 ~ { text {такой, что для всех}} ~ { vec {x}} ~ { text {with}} ~ x_ {i} geq M ~ { text {для некоторых}} ~ 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 е (п, м) = О (п ^ {м}) квад { текст {как}} п, м к infty ~}$

(т.е. ${ Displaystyle существует C существует M forall n forall m dots}$) сильно отличается от

${ Displaystyle forall м двоеточие ~ е (п, м) = О (п ^ {м}) quad { text {as}} п к infty}$

(т.е. ${ Displaystyle forall м существует C существует M forall п точек}$).

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

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

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

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

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

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

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

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

${ Displaystyle г (х) = час (х) + О (е (х))}$

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

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

Пример

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

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

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

${ Displaystyle (п + 1) ^ {2} = п ^ {2} + О (п)}$

${ Displaystyle (п + О (п ^ {1/2})) (п + О ( журнал п)) ^ {2} = п ^ {3} + О (п ^ {5/2})}$

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

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

Верстка

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

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

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

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

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

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

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

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

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

${ Displaystyle е (х) = о (г (х)) квад { текст {as}} х к infty}$

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

${ Displaystyle | е (х) | leq varepsilon g (x) quad { text {для всех}} x geq N.}$^[15]

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

${ Displaystyle 2x = о (х ^ {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 е (х) = о (г (х))}$ эквивалентно

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

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

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

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

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

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

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

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

${ Displaystyle е (х) = Омега (г (х))}$ в качестве ${ displaystyle x rightarrow a,}$,

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

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

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

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

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

Таким образом ${ Displaystyle е (х) = Омега (г (х))}$ это отрицание ${ Displaystyle е (х) = о (г (х))}$.

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

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

${ Displaystyle е (х) = Омега _ {L} (г (х))}$ в качестве ${ Displaystyle х 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 е (х) = Омега _ { pm} (г (х))}$ (означающий, что ${ Displaystyle е (х) = Омега _ {+} (г (х))}$ и ${ Displaystyle е (х) = Омега _ {-} (г (х))}$ оба удовлетворены), в настоящее время используются в аналитическая теория чисел.^[20][21]

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

У нас есть

${ Displaystyle грех х = Омега (1)}$ в качестве ${ Displaystyle х rightarrow infty,}$

а точнее

${ Displaystyle грех х = Омега _ { pm} (1)}$ в качестве ${ displaystyle x rightarrow infty.}$

У нас есть

${ Displaystyle грех х + 1 = Омега (1)}$ в качестве ${ Displaystyle х rightarrow infty,}$

а точнее

${ Displaystyle грех х + 1 = Омега _ {+} (1)}$ в качестве ${ Displaystyle х rightarrow infty;}$

тем не мение

${ Displaystyle грех х + 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 е (п) = О (г (п))}$	Большой O; Big Oh; Большой Омикрон	${ displaystyle | f |}$ ограничен сверху грамм (с точностью до постоянного множителя) асимптотически	${ Displaystyle существует к> 0 существует n_ {0} forall n> n_ {0} двоеточие | f (n) | Leq k cdot g (n)}$	${ Displaystyle limsup _ {п к infty} { frac { left | f (n) right |} {g (n)}} < infty}$
${ Displaystyle е (п) = тета (г (п))}$	Большая Тета	ж ограничена как сверху, так и снизу грамм асимптотически	${ displaystyle exists k_ {1}> 0 exists k_ {2}> 0 exists n_ {0} forall n> n_ {0} двоеточие}$ ${ Displaystyle к_ {1} cdot g (n) leq f (n) leq k_ {2} cdot g (n)}$	${ Displaystyle е (п) = О (г (п))}$ и ${ Displaystyle е (п) = Омега (г (п))}$ (Версия Кнута)
${ Displaystyle е (п) = Омега (г (п))}$	Большая Омега в теории сложности (Кнут)	ж ограничено снизу грамм асимптотически	${ Displaystyle существует к> 0 существует n_ {0} forall n> n_ {0} двоеточие f (n) geq k cdot g (n)}$	${ displaystyle liminf _ {n to infty} { frac {f (n)} {g (n)}}> 0}$
${ Displaystyle е (п) = о (г (п))}$	Маленький O; Маленький О	ж преобладают грамм асимптотически	${ Displaystyle forall k> 0 существует n_ {0} forall n> n_ {0} двоеточие | f (n) |$	${ displaystyle lim _ {n to infty} { frac { left | f (n) right |} {g (n)}} = 0}$
${ Displaystyle е (п) сим г (п)}$	В порядке	ж равно грамм асимптотически	${ Displaystyle forall varepsilon> 0 существует n_ {0} forall n> n_ {0} двоеточие left | {f (n) over g (n)} - 1 right | < varepsilon}$	${ Displaystyle lim _ {п к infty} {е (п) над г (п)} = 1}$
${ Displaystyle е (п) = омега (г (п))}$	Малая Омега	ж доминирует грамм асимптотически	${ Displaystyle forall k> 0 существует n_ {0} forall n> n_ {0} двоеточие | f (n) |> k cdot | g (n) |}$	${ displaystyle lim _ {n to infty} left | { frac {f (n)} {g (n)}} right | = infty}$
${ Displaystyle е (п) = Омега (г (п))}$	Большая Омега в теории чисел (Харди – Литтлвуд)	${ displaystyle | f |}$ не преобладает грамм асимптотически	${ displaystyle exists k> 0 forall n_ {0} exists n> n_ {0} двоеточие | 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 е (п) = О (г (п)) квад (п стрелка вправо infty) ~.}$

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

${ Displaystyle О (г) = {е:}$ существуют положительные постоянные c и ${ displaystyle n_ {0}}$ такой, что ${ Displaystyle 0 Leq е (п) Leq cg (п)}$ для всех ${ 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_ {п} [ альфа, с] = е ^ {(с + о (1)) ( пер п) ^ { альфа} ( пер пер п) ^ {1- альфа}} }$

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

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

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

${ Displaystyle е сим г iff (е-г) ин о (г)}$

который является отношение эквивалентности и понятие более ограничительное, чем отношения "ж (грамм) "сверху. (сводится к 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 е пре г если и только если е в о (г);}$

(Однако Харди никогда не определял и не использовал обозначение ${ 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
• Теорема Нахбина: Точный метод ограничения комплексный аналитический функций так, чтобы область сходимости интегральные преобразования можно сказать
• Порядки приближения
• Вычислительная сложность математических операций

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

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

• Харди, Г. Х. (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