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

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

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

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

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

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

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

если абсолютная величина из не более чем положительное постоянное кратное для всех достаточно больших значений Икс. То есть, если существует положительное действительное число M и реальное число Икс0 такой, что

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

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

если есть положительные числа и M такой, что для всех Икс с ,

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

если

В информатике распространено несколько более ограничительное определение: и оба должны быть функциями от положительное число к неотрицательным действительным числам; если существуют положительные целые числа M и п0 такой, что [6]При необходимости конечные диапазоны (неявно) исключаются из 'песок домена, выбрав п0 достаточно большой.[7]

Пример

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

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

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

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

так

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

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

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

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

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

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

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

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

или же

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

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

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

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

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

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

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

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

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

Товар

Сумма

Из этого следует , что обозначает это выпуклый конус.

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

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

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

Большой О (и маленькие o, Ω и т. д.) также можно использовать с несколькими переменными. О формально для нескольких переменных предположим и две функции, определенные на некотором подмножестве . Мы говорим

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

Эквивалентно условие, что для некоторых можно заменить условием, что , куда обозначает Чебышевская норма. Например, утверждение

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

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

Это определение допускает все координаты увеличивать до бесконечности. В частности, заявление

(т.е. ) сильно отличается от

(т.е. ).

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

Верстка

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

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

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

ОбозначениеИмяПример
постоянныйОпределение четного или нечетного двоичного числа; Расчет ; Использование постоянного размера Справочная таблица
двойной логарифмическийКоличество сравнений, проведенных при поиске элемента с использованием поиск с интерполяцией в отсортированном массиве равномерно распределенных значений
логарифмическийПоиск элемента в отсортированном массиве с бинарный поиск или сбалансированный поиск дерево а также все операции в Биномиальная куча

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

дробная мощностьПоиск в k-d дерево
линейныйНахождение элемента в несортированном списке или в несортированном массиве; добавление двух п-битовые целые числа рябь нести
п бревенчатая звезда пВыполнение триангуляция простого многоугольника с помощью Алгоритм Зейделя, или алгоритм объединения – поиска. Обратите внимание, что
линейный, логлинейный, квазилинейный или "n log n"Выполнение быстрое преобразование Фурье; Максимально быстро сортировка сравнения; heapsort и Сортировка слиянием
квадратичныйУмножение двух п-разрядные числа по простому алгоритму; простые алгоритмы сортировки, такие как пузырьковая сортировка, сортировка выбора и вставка сортировки; (худший случай) связаны с некоторыми обычно более быстрыми алгоритмами сортировки, такими как быстрая сортировка, Shellsort, и сортировка по дереву
многочлен или алгебраическийГрамматика, примыкающая к дереву парсинг; максимум соответствие за двудольные графы; найти детерминант с LU разложение

L-обозначение или же субэкспоненциальныйФакторинг числа с использованием квадратное сито или же числовое поле сито

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

Заявление иногда ослабляется до для вывода более простых формул асимптотической сложности. и , это подмножество для любого , поэтому его можно рассматривать как полином большего порядка.

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

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

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

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

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

[15]

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

и

Разница между более ранними определение для обозначения большого О и нынешнего определения маленького О таково, что в то время как первое должно быть верным для хотя бы один постоянный M, последнее должно выполняться каждый положительная константа εхоть и маленький.[16] Таким образом, небольшие обозначения делают более сильное заявление чем соответствующая нотация большого O: каждая функция, которая является маленькой из грамм также большой O из грамм, но не каждая функция, которая является большим-O из грамм также мало грамм. Например, но

В качестве грамм(Икс) отлична от нуля или, по крайней мере, становится ненулевой после определенной точки, соотношение эквивалентно

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

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

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

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

если и тогда

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

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

в качестве ,

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

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

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

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

в качестве если

Таким образом это отрицание .

В 1916 году те же авторы ввели два новых символа. и , определяется как:[18]

в качестве если ;
в качестве если

Эти символы использовались Эдмунд Ландау, с тем же смыслом, в 1924 году.[19] После Ландау обозначения больше никогда не использовались именно так; стал и стал .[нужна цитата ]

Эти три символа , а также (означающий, что и оба удовлетворены), в настоящее время используются в аналитическая теория чисел.[20][21]

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

У нас есть

в качестве

а точнее

в качестве

У нас есть

в качестве

а точнее

в качестве

тем не мение

в качестве

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

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

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

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

ОбозначениеИмя[22]ОписаниеФормальное определениеОпределение предела[23][24][25][22][17]
Большой O; Big Oh; Большой Омикрон ограничен сверху грамм (с точностью до постоянного множителя) асимптотически
Большая Тетаж ограничена как сверху, так и снизу грамм асимптотически и (Версия Кнута)
Большая Омега в теории сложности (Кнут)ж ограничено снизу грамм асимптотически
Маленький O; Маленький Ож преобладают грамм асимптотически
В порядкеж равно грамм асимптотически
Малая Омегаж доминирует грамм асимптотически
Большая Омега в теории чисел (Харди – Литтлвуд) не преобладает грамм асимптотически

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

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

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

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

  1. Т(п) = О(п100)
  2. Т(п) = О(п3)
  3. Т(п) = Θ (п3)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

и

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

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

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

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

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

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

  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. ^ Например, не определено в .
  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. ^ а б c Харди, Г. Х .; 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. ^ а б c d е 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 и п0 such that 0 ≤ ж(п) ≤ cg(п) for all пп0}
  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п2 + 3п + 1 = 2п2 + θ(п) means that 2п2 + 3п + 1 = 2п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.CS1 maint: другие (связь)
  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.

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

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