Большой О обозначений является математическим выражением , которое описывает предельное поведение в виде функции , когда аргумент стремится к определенному значению или бесконечности. Big O является член семейства нотации , изобретенного Paul Bachmann , [1] Эдмунд Ландау , [2] и другие, в совокупности называется Bachmann-Ландау обозначение или асимптотическим обозначение .
В информатике нотация большого O используется для классификации алгоритмов в соответствии с тем, как их время выполнения или требования к пространству растут по мере увеличения размера входных данных. [3] В аналитической теории чисел нотация большого O часто используется для обозначения разницы между арифметической функцией и более понятным приближением; известный пример такой разницы - остаточный член в теореме о простых числах . Обозначение Big O также используется во многих других областях для получения аналогичных оценок.
Обозначение Big O характеризует функции в соответствии с их скоростью роста: разные функции с одинаковой скоростью роста могут быть представлены с использованием одной и той же записи O. Буква O используется, потому что скорость роста функции также называется порядком функции . Описание функции в терминах нотации большого O обычно дает только верхнюю границу скорости роста функции.
С обозначением большого O связано несколько связанных обозначений, в которых используются символы o , Ω, ω и Θ для описания других видов оценок асимптотических темпов роста.
Формальное определение
Пусть f - вещественная или комплексная функция, а g - вещественная функция. Пусть обе функции определены на некотором неограниченном подмножестве положительных действительных чисел ибыть строго положительным для всех достаточно больших значений x . [4] Один пишет
если абсолютное значение из не более чем положительное постоянное кратное для всех достаточно больших значений x . Это,если существуют положительное действительное число M и действительное число x 0 такие, что
Во многих контекстах предположение о том, что нас интересует скорость роста, когда переменная x стремится к бесконечности, не указывается, и проще записать, что
Обозначения также могут использоваться для описания поведения f вблизи некоторого действительного числа a (часто a = 0 ): мы говорим
если есть положительные числа и M такие, что для всех x с,
Поскольку g ( x ) выбирается ненулевым для значений x, достаточно близких к a , оба этих определения могут быть объединены с использованием верхнего предела :
если
В информатике распространено несколько более ограничительное определение: а также оба должны быть функциями от положительных целых чисел до неотрицательных действительных чисел;если существуют натуральные числа M и n 0 такие, что для всех . [5] При необходимости конечные диапазоны (неявно) исключаются из'песок области, выбрав n 0 достаточно большим. (Например, не определено в .)
Пример
В типичном использовании обозначение O является асимптотическим, то есть относится к очень большим x . В этом случае вклад терминов, которые растут «наиболее быстро», в конечном итоге сделает другие неуместными. В результате могут применяться следующие правила упрощения:
- Если f ( x ) является суммой нескольких членов, если есть одно с наибольшей скоростью роста, его можно оставить, а все остальные опустить.
- Если f ( x ) является произведением нескольких факторов, любые константы (члены в произведении, которые не зависят от x ) могут быть опущены.
Например, пусть f ( x ) = 6 x 4 - 2 x 3 + 5 , и предположим, что мы хотим упростить эту функцию, используя обозначение O , чтобы описать скорость ее роста по мере приближения x к бесконечности. Эта функция представляет собой сумму трех членов: 6 x 4 , −2 x 3 и 5 . Из этих трех членов один с наибольшей скоростью роста имеет наибольший показатель как функцию от x , а именно 6 x 4 . Теперь можно применить второе правило: 6 x 4 - это произведение 6 и x 4, в котором первый множитель не зависит от x . Отсутствие этого фактора приводит к упрощенной форме x 4 . Таким образом, мы говорим, что f ( x ) - это «большой O» x 4 . Математически мы можем написать f ( x ) = O ( x 4 ) . Этот расчет можно подтвердить, используя формальное определение: пусть f ( x ) = 6 x 4 - 2 x 3 + 5 и g ( x ) = x 4 . Применяя формальное определение сверху, утверждение, что f ( x ) = O ( x 4 ) , эквивалентно его разложению,
для некоторого подходящего выбора x 0 и M и для всех x > x 0 . Чтобы доказать это, пусть x 0 = 1 и M = 13 . Тогда для всех x > x 0 :
так
Применение
Нотация Big O имеет две основные области применения:
- В математике он обычно используется для описания того, насколько близко конечный ряд приближается к заданной функции , особенно в случае усеченного ряда Тейлора или асимптотического разложения.
- В информатике это полезно при анализе алгоритмов.
В обоих приложениях функция g ( x ), появляющаяся внутри O (...) , обычно выбирается как можно более простой, опуская постоянные множители и члены более низкого порядка.
Есть два формально близких, но заметно разных использования этой нотации: [ необходима цитата ]
- бесконечная асимптотика
- бесконечно малые асимптотики.
Однако это различие только в применении, а не в принципе - формальное определение «большого О» одинаково для обоих случаев, только с разными ограничениями для аргумента функции. [ оригинальное исследование? ]
Бесконечная асимптотика
Обозначение Big O полезно при анализе алгоритмов на эффективность. Например, время (или количество шагов), необходимое для выполнения задачи размера n, может оказаться равным T ( n ) = 4 n 2 - 2 n + 2 . В п растет большим, п 2 термина будет доминировать, так что все остальные член можно пренебречь, например , когда п = 500 , термин 4 н 2 составляет 1000 раз больше , как 2 н перспективы. Игнорирование последнего окажет незначительное влияние на значение выражения для большинства целей. Кроме того, коэффициенты становятся неактуальными, если мы сравниваем их с любым другим порядком выражения, например с выражением, содержащим член n 3 или n 4 . Даже если T ( n ) = 1000000 n 2 , если U ( n ) = n 3 , последнее всегда будет превышать первое, как только n станет больше 1000000 ( T (1000000) = 1000000 3 = U (1000000) ). Кроме того, количество шагов зависит от деталей модели машины, на которой работает алгоритм, но разные типы машин обычно различаются только постоянным фактором количества шагов, необходимых для выполнения алгоритма. Таким образом, большая нотация O фиксирует то, что осталось: мы пишем либо
или же
и говорят, что алгоритм имеет временную сложность порядка n 2 . Знак « = » не предназначен для выражения «равно» в его обычном математическом смысле, а скорее для более разговорного «есть», поэтому второе выражение иногда считается более точным (см. Обсуждение « Знак равенства » ниже), в то время как первый рассматривается некоторыми как злоупотребление обозначениями . [6]
Бесконечно малые асимптотики
Big O также может использоваться для описания члена ошибки в приближении математической функции. Наиболее значимые термины записываются явно, а затем наименее значимые термины суммируются в один большой член О. Рассмотрим, например, экспоненциальный ряд и два его выражения, которые действительны, когда x мало:
Второе выражение (один с O ( х 3 )) означает абсолютное-значение ошибки е х - (1 + х + х 2 /2) самый большие несколько раз постоянных | х 3 | когда x достаточно близко к 0.
Характеристики
Если функцию f можно записать как конечную сумму других функций, то наиболее быстро растущая функция определяет порядок f ( n ) . Например,
В частности, если функция может быть ограничена полиномом от n , то по мере того, как n стремится к бесконечности , можно не учитывать младшие члены полинома. Множества O ( n c ) и O ( c n ) очень разные. Если c больше единицы, то последний растет намного быстрее. Функция, которая растет быстрее, чем n c для любого c , называется суперполиномиальной . Функция, которая растет медленнее любой экспоненциальной функции вида c n , называется субэкспоненциальной . Алгоритму может потребоваться время, которое является как суперполиномиальным, так и субэкспоненциальным; Примеры этого включают самые быстрые известные алгоритмы для целочисленной факторизации и функцию n log n .
Мы можем игнорировать любые степени n внутри логарифмов. Набор O (log n ) точно такой же, как O (log ( n c )) . Логарифмы различаются только постоянным множителем (поскольку log ( n c ) = c log n ), и, таким образом, большая нотация O игнорирует это. Точно так же бревна с разными постоянными основаниями эквивалентны. С другой стороны, экспоненты с разными основаниями не одного порядка. Например, 2 n и 3 n не одного порядка.
Изменение единиц измерения может повлиять или не повлиять на порядок результирующего алгоритма. Изменение единиц эквивалентно умножению соответствующей переменной на константу, где бы она ни появлялась. Например, если алгоритм выполняется в порядке n 2 , замена n на cn означает, что алгоритм работает в порядке c 2 n 2 , а нотация большого O игнорирует константу c 2 . Это можно записать как c 2 n 2 = O ( n 2 ) . Однако, если алгоритм выполняется в порядке 2 n , замена n на cn дает 2 cn = (2 c ) n . Это не эквивалентно 2 n в целом. Изменение переменных также может повлиять на порядок результирующего алгоритма. Например, если время выполнения алгоритма , является O ( п ) при измерении в терминах числа п из цифр входного числа х , то его время работы составляет O (журнал х ) при измерении , как функция от входного числа х сама , поскольку n = O (log x ) .
Продукт
Сумма
Из этого следует , что обозначает - выпуклый конус .
Умножение на константу
- Пусть k будет постоянным. Потом:
- если k ненулевое.
Несколько переменных
Большой O (и маленький o, Ω и т. Д.) Также можно использовать с несколькими переменными. Чтобы формально определить большой O для нескольких переменных, предположим а также две функции, определенные на некотором подмножестве . Мы говорим
тогда и только тогда, когда [7]
Эквивалентно условие, что для некоторых можно заменить условием, что , где обозначает чебышевскую норму . Например, заявление
утверждает, что существуют такие константы C и M , что
где g ( n , m ) определяется как
Это определение допускает все координаты увеличивать до бесконечности. В частности, заявление
(т.е. ) сильно отличается от
(т.е. ).
Согласно этому определению, подмножество, на котором определяется функция, имеет значение при обобщении утверждений от одномерного параметра до многомерного. Например, если а также , тогда если мы ограничим а также к , но не если они определены на .
Это не единственное обобщение большого O на многомерные функции, и на практике существует некоторая непоследовательность в выборе определения. [8]
Вопросы обозначений
Знак равенства
Утверждение « f ( x ) равно O ( g ( x ))», как определено выше, обычно записывается как f ( x ) = O ( g ( x )) . Некоторые считают, что это злоупотребление обозначениями , поскольку использование знака равенства может вводить в заблуждение, так как предполагает симметрию, которой нет в этом утверждении. Как говорит де Брёйн , O ( x ) = O ( x 2 ) верно, а O ( x 2 ) = O ( x ) - нет. [9] Кнут описывает такие утверждения как «односторонние равенства», поскольку, если бы стороны могли быть поменяны местами, «мы могли бы вывести такие нелепые вещи, как n = n 2, из тождеств n = O ( n 2 ) и n 2 = O ( п 2 ) ". [10]
По этим причинам было бы более точно использовать обозначение множества и писать f ( x ) ∈ O ( g ( x )) (читается как: « f ( x ) является элементом O ( g ( x ))», или « f ( x ) находится в множестве O ( g ( x ))»), считая O ( g ( x )) классом всех функций h ( x ) таких, что | h ( x ) | ≤ C | g ( x ) | для некоторых постоянная C . [10] Однако обычно используется знак равенства. [ необходима цитата ]
Другие арифметические операторы
Обозначение Big O может также использоваться в сочетании с другими арифметическими операторами в более сложных уравнениях. Например, h ( x ) + O ( f ( x )) обозначает набор функций, имеющих рост h ( x ) плюс часть, рост которой ограничен ростом f ( x ). Таким образом,
выражает то же, что и
Пример
Предположим , что разрабатывается алгоритм для работы с набором из n элементов. Его разработчики заинтересованы в поиске функции T ( n ), которая выражает, сколько времени потребуется алгоритму для выполнения (в некотором произвольном измерении времени) с точки зрения количества элементов во входном наборе. Алгоритм работает, сначала вызывая подпрограмму для сортировки элементов в наборе, а затем выполняет свои собственные операции. Сортировка имеет известную временную сложность O ( n 2 ), и после запуска подпрограммы алгоритм должен сделать еще 55 n 3 + 2 n + 10 шагов, прежде чем он завершится. Таким образом, общая временная сложность алгоритма может быть выражена как T ( n ) = 55 n 3 + O ( n 2 ) . Здесь члены 2 n + 10 включены в быстрорастущий O ( n 2 ). Опять же, это использование игнорирует некоторые формальные значения символа «=», но позволяет использовать нотацию большой буквы O в качестве удобного заполнителя.
Многократное использование
В более сложном использовании O (...) может появляться в разных местах уравнения, даже несколько раз с каждой стороны. Например, для
Смысл таких утверждений следующий: для любых функций, которые удовлетворяют каждому O (...) в левой части, есть некоторые функции, удовлетворяющие каждому O (...) в правой части, такие, что замена всех этих функций в уравнение уравнивает две стороны. Например, третье уравнение выше означает: «Для любой функции f ( n ) = O (1) существует некоторая функция g ( n ) = O ( e n ) такая, что n f ( n ) = g ( n ). " В терминах «обозначения множества» выше это означает, что класс функций, представленных левой стороной, является подмножеством класса функций, представленных правой стороной. В этом случае «=» является формальным символом, который, в отличие от обычного использования «=», не является симметричным отношением . Таким образом, например, n O (1) = O ( e n ) не подразумевает ложное утверждение O ( e n ) = n O (1)
Верстка
Big O набирается курсивом в верхнем регистре "O", как в следующем примере: . [11] [12] В TeX это получается простым вводом O в математическом режиме. В отличие от обозначений Бахмана – Ландау с греческими именами, он не требует специального символа. Однако некоторые авторы используют каллиграфический вариант.вместо. [13] [14]
Порядки общих функций
Вот список классов функций, которые обычно встречаются при анализе времени работы алгоритма. В каждом случае c - положительная константа, а n неограниченно возрастает. Обычно сначала перечисляются медленнорастущие функции.
Обозначение | Имя | Пример |
---|---|---|
постоянный | Определение, четное или нечетное двоичное число; Расчет; Использование таблицы поиска постоянного размера | |
двойной логарифмический | Количество сравнений, проведенных при поиске элемента с помощью интерполяционного поиска в отсортированном массиве равномерно распределенных значений | |
логарифмический | Поиск элемента в отсортированном массиве с помощью двоичного поиска или сбалансированного дерева поиска, а также все операции в биномиальной куче | |
полилогарифмический | Упорядочение цепочки матриц может быть решено за полилогарифмическое время на параллельной машине с произвольным доступом . | |
дробная мощность | Поиск в дереве kd | |
линейный | Нахождение элемента в несортированном списке или в несортированном массиве; сложение двух n -битных целых чисел путем переноса методом пульсации | |
п журнал-звезда п | Выполнение триангуляции простого многоугольника с использованием алгоритма Зейделя , или алгоритм профсоюза найти . Обратите внимание, что | |
linearithmic , loglinear, квазилинейный или «п войти п» | Выполнение быстрого преобразования Фурье ; Самая быстрая сортировка сравнения ; heapsort и merge sort | |
квадратичный | Умножение двух n- значных чисел простым алгоритмом; простые алгоритмы сортировки, такие как пузырьковая сортировка , сортировка по выбору и сортировка по вставке ; ( в худшем случае) , связанные с некоторыми обычно быстрее алгоритмов сортировки , таких как быстрая сортировка , ShellSort и дерево рода | |
полиномиальный или алгебраический | Парсинг грамматики, примыкающей к дереву ; максимальное соответствие для двудольных графов ; нахождение определителя с LU-разложением | |
L-запись или субэкспоненциальная | Факторизация числа с помощью квадратного сита или сита числового поля | |
экспоненциальный | Нахождение (точного) решения задачи коммивояжера с помощью динамического программирования ; определение эквивалентности двух логических операторов с помощью перебора | |
факториал | Решение задачи коммивояжера методом перебора; генерирование всех неограниченных перестановок чугуна ; нахождение определителя с разложением Лапласа ; перечисление всех разделов набора |
Заявление иногда ослабляется до для вывода более простых формул асимптотической сложности. Для любой а также , это подмножество для любой , поэтому его можно рассматривать как полином большего порядка.
Связанные асимптотические обозначения
Big O широко используется в информатике. Вместе с некоторыми другими родственными обозначениями он образует семейство обозначений Бахмана – Ландау. [ необходима цитата ]
Маленькая нотация
Интуитивно, утверждение « f ( x ) is o ( g ( x )) » (читается « f ( x ) is little-o of g ( x ) ») означает, что g ( x ) растет намного быстрее, чем f ( x ). . Пусть, как и раньше, f - вещественная или комплексная функция, а g - вещественная функция, обе определены на некотором неограниченном подмножестве положительных действительных чисел , так что g ( x ) строго положительна для всех достаточно больших значений x . Один пишет
если для любой положительной постоянной ε существует такая постоянная N , что
- [15]
Например, есть
- а также
Разница между предыдущим определением нотации большого O и настоящим определением little-o состоит в том, что, хотя первое должно быть истинным по крайней мере для одной константы M , последнее должно выполняться для любой положительной константы ε , какой бы малой она ни была. [16] Таким образом, нотация small-o делает более сильное утверждение, чем соответствующая нотация big-O: каждая функция, которая является little-o от g , также является большой O для g , но не каждая функция, которая является big-O от g также немногое от g . Например, но .
Поскольку g ( x ) отлична от нуля или, по крайней мере, становится отличной от нуля после определенной точки, соотношение эквивалентно
- (и именно так Ландау [15] первоначально определил обозначение small-o).
Мало-o уважает ряд арифметических операций. Например,
- если c - ненулевая константа и тогда , а также
- если а также тогда
Он также удовлетворяет соотношению транзитивности :
- если а также тогда
Обозначение Big Omega
Еще одно асимптотическое обозначение: , прочтите "большая омега". [17] Есть два широко распространенных и несовместимых определения утверждения.
- в виде ,
где a - некоторое действительное число, ∞ или −∞, где f и g - действительные функции, определенные в окрестности a , и где g положительно в этой окрестности.
Определение Харди – Литтлвуда используется главным образом в аналитической теории чисел , а определение Кнута - в основном в теории сложности вычислений ; определения не эквивалентны.
Определение Харди – Литтлвуда
В 1914 году Годфри Гарольд Харди и Джон Эденсор Литтлвуд представили новый символ., [18] который определяется следующим образом:
- в виде если
Таким образом это отрицание .
В 1916 году те же авторы ввели два новых символа. а также , определяется как: [19]
- в виде если ;
- в виде если
Эти символы использовались Эдмундом Ландау с теми же значениями в 1924 году. [20] После Ландау обозначения больше никогда не использовались именно так; стал а также стал . [ необходима цитата ]
Эти три символа , также как и (означающий, что а также оба удовлетворены), в настоящее время используются в аналитической теории чисел . [21] [22]
Простые примеры
У нас есть
- в виде
а точнее
- в виде
У нас есть
- в виде
а точнее
- в виде
тем не мение
- в виде
Определение Кнута
В 1976 году Дональд Кнут опубликовал статью, в которой обосновал использование-символ для описания более сильного свойства. [23] Кнут писал: «Для всех приложений, которые я видел до сих пор в информатике, более сильное требование ... гораздо более уместно». Он определил
с комментарием: «Хотя я изменил определение Харди и Литтлвуда , Я считаю оправданным поступать так, потому что их определение никоим образом не широко используется, и потому что есть другие способы сказать то, что они хотят сказать, в сравнительно редких случаях, когда их определение применимо » [23].
Семейство обозначений Бахмана – Ландау.
Обозначение | Имя [23] | Описание | Формальное определение | Определение предела [24] [25] [26] [23] [18] |
---|---|---|---|---|
Большой O; Большой Ой; Большой Омикрон | ограничено сверху g (с точностью до постоянного множителя) асимптотически | |||
Большая Тета | f ограничена как сверху, так и снизу через g асимптотически | а также (Версия Кнута) | ||
Большая Омега в теории сложности (Кнут) | f ограничена снизу g асимптотически | |||
Маленький O; Маленький О | f асимптотически преобладает над g | |||
В порядке | f асимптотически равна g | |||
Малая Омега | f асимптотически доминирует над g | |||
Большая Омега в теории чисел (Харди – Литтлвуд) | не доминирует g асимптотически |
Определения пределов предполагают для достаточно большого . Таблица (частично) отсортирована от наименьшего к наибольшему в том смысле, что (Версия Кнута) по функциям соответствуют на действительной прямой [26] (версия Харди-Литтлвудаоднако не соответствует какому-либо такому описанию).
Информатика использует большие , большая тета , маленький , маленькая омега и большая Омега Кнута обозначения. [27] Аналитическая теория чисел часто использует большие, небольшой , Большая Омега Харди – Литтлвуда (с индексами +, - или ± или без них) и обозначения. [21] Маленькая омегаобозначения не так часто используются при анализе. [28]
Использование в информатике
Неформально, особенно в информатике, нотация большого O часто может использоваться несколько иначе для описания асимптотической жесткой границы, где использование нотации большого Theta Θ может быть более уместным с фактической точки зрения в данном контексте. [ необходима цитата ] Например, при рассмотрении функции T ( n ) = 73 n 3 + 22 n 2 + 58 все нижеследующее обычно приемлемо, но более жесткие границы (например, числа 2 и 3 ниже) обычно настоятельно предпочтительны. по более свободным границам (например, номер 1 ниже).
- Т ( п ) = О ( п 100 )
- Т ( п ) = О ( п 3 )
- Т ( п ) = Θ ( п 3 )
Эквивалентные английские утверждения соответственно:
- T ( n ) растет асимптотически не быстрее, чем n 100
- T ( n ) растет асимптотически не быстрее, чем n 3
- T ( n ) растет асимптотически так же быстро, как n 3 .
Таким образом, хотя все три утверждения верны, в каждом содержится все больше информации. В некоторых полях, однако, большая нотация O (цифра 2 в приведенных выше списках) будет использоваться чаще, чем большая нотация Theta (элементы с номером 3 в списках выше). Например, если T ( n ) представляет время работы недавно разработанного алгоритма для входного размера n , изобретатели и пользователи алгоритма могут быть более склонны установить верхнюю асимптотическую границу того, сколько времени потребуется для выполнения, не делая явное утверждение о нижней асимптотической оценке.
Другие обозначения
В своей книге Введение в алгоритмы , Кормена , Лейзерсон , Ривест и Stein рассмотрим множество функций F , которые удовлетворяют условию
В правильных обозначениях это множество можно, например, назвать O ( g ), где
- . [29]
Авторы заявляют, что использование оператора равенства (=) для обозначения членства в множестве, а не оператора членства в множестве (∈) является злоупотреблением нотацией, но это имеет преимущества. [6] Внутри уравнения или неравенства использование асимптотической записи означает анонимную функцию в множестве O ( g ), что исключает члены более низкого порядка и помогает уменьшить несущественный беспорядок в уравнениях, например: [30]
Расширения обозначений Бахмана – Ландау.
Другое обозначение, которое иногда используется в информатике, - это Õ (читай soft-O ): f ( n ) = Õ ( g ( n )) является сокращением для f ( n ) = O ( g ( n ) log k g ( n )) для некоторые к . [31] По сути, это большая нотация O, игнорирующая логарифмические факторы, потому что эффекты скорости роста некоторой другой суперлогарифмической функции указывают на резкий рост скорости роста входных параметров большого размера, что более важно для прогнозирования плохой производительности во время выполнения. чем эффекты более тонкой точки, вносимые логарифмическими факторами роста. Это обозначение часто используется, чтобы избежать «придирок» в пределах темпов роста, которые заявлены как слишком жестко ограниченные для рассматриваемых вопросов (поскольку log k n всегда равно o ( n ε ) для любой константы k и любого ε > 0 ).
Также обозначение L , определенное как
удобен для функций, которые находятся между полиномиальной и экспоненциальной в терминах.
Обобщение на функции, принимающие значения в любом нормированном векторном пространстве, является простым (заменяя абсолютные значения нормами), где f и g не должны принимать свои значения в одном и том же пространстве. Обобщение на функцию г , принимающие значения в любом топологической группы также возможно [ править ] . «Ограничивающий процесс» x → x o также может быть обобщен путем введения произвольной базы фильтров , то есть направленных сетей f и g . О нотации может быть использована для определения производных и дифференцируемого в довольно общих пространства, а также (асимптотическая) эквивалентность функций,
которое является отношением эквивалентности и более ограничительным понятием, чем отношение « f is Θ ( g )» сверху. (Это сводится к lim f / g = 1, если f и g - положительные вещественные функции.) Например, 2 x - это Θ ( x ), но 2 x - x не является o ( x ).
История (обозначения Бахмана – Ландау, Харди и Виноградова)
Символ O был впервые введен теоретиком чисел Полем Бахманном в 1894 году во втором томе его книги Analytische Zahlentheorie (« аналитическая теория чисел »). [1] Теоретик чисел Эдмунд Ландау принял его и, таким образом, был вдохновлен ввести в 1909 году обозначение o; [2] поэтому оба теперь называются символами Ландау. Эти обозначения использовались в прикладной математике в 1950-х годах для асимптотического анализа. [32] Символ(в смысле «не о из») была введена в 1914 году Харди и Литтлвуда. [18] Харди и Литтлвуд также ввели в 1916 году символы ("право") и («слева»), [19] предшественники современных символов («не меньше маленького о») и («не больше маленького о»). Таким образом, символы Омеги (с их первоначальным значением) иногда также называют «символами Ландау». Это обозначениестал широко использоваться в теории чисел, по крайней мере, с 1950-х годов. [33] В 1970-х годах большой O был популяризирован в компьютерных науках Дональдом Кнутом , который ввел соответствующую нотацию Theta и предложил другое определение нотации Omega. [23]
Ландау никогда не использовал большие символы теты и малые омега.
Символы Харди были (с точки зрения современной нотации O )
- а также
(Однако Харди никогда не определял и не использовал обозначение , ни , как иногда сообщалось). Харди представил символы а также (а также некоторые другие символы) в своем трактате 1910 года «Ордена бесконечности» и использовал их только в трех статьях (1910–1913). В своих почти 400 оставшихся статьях и книгах он постоянно использовал символы Ландау O и o.
Обозначения Харди больше не используются. С другой стороны, в 1930-х годах [34] русский теоретик чисел Иван Матвеевич Виноградов ввел свои обозначения, который все чаще используется в теории чисел вместо обозначение. У нас есть
и часто оба обозначения используются в одной и той же статье.
Большой-O изначально означает «порядок» («Ordnung», Bachmann 1894) и, таким образом, является латинской буквой. Ни Бахманн, ни Ландау никогда не называли его «Омикрон». Символ был гораздо позже (1976 г.) рассматривается Кнут как капитал OMICRON , [23] , вероятно , ссылаясь на его определение символа Omega . Цифру ноль использовать не следует.
Смотрите также
- Асимптотическое разложение : приближение функций, обобщающих формулу Тейлора
- Асимптотически оптимальный алгоритм : фраза, часто используемая для описания алгоритма, который имеет верхнюю границу асимптотически в пределах константы нижней границы для задачи.
- Большой O в вероятностной записи : O p , o p
- Верхний предел и нижний предел : объяснение некоторых обозначений пределов, используемых в этой статье
- Основная теорема (анализ алгоритмов) : для анализа рекурсивных алгоритмов «разделяй и властвуй» с использованием нотации Big O
- Теорема Нахбина : точный метод ограничения комплексных аналитических функций так, чтобы можно было указать область сходимости интегральных преобразований
- Порядки приближения
- Вычислительная сложность математических операций
Ссылки и примечания
- ^ a b Бахманн, Пауль (1894). Analytische Zahlentheorie [ Аналитическая теория чисел ] (на немецком языке). 2 . Лейпциг: Тойбнер.
- ^ а б Ландау, Эдмунд (1909). Handbuch der Lehre von der Verteilung der Primzahlen [ Справочник по теории распределения простых чисел ] (на немецком языке). Лейпциг: BG Teubner. п. 883.
- ^ Мор, Остин. «Квантовые вычисления в теории сложности и теории вычислений» (PDF) . п. 2 . Проверено 7 июня 2014 .
- ^ Ландау, Эдмунд (1909). Handbuch der Lehre von der Verteilung der Primzahlen [ Справочник по теории распределения простых чисел ] (на немецком языке). Лейпциг: BG Teubner. п. 31.
- ^ Майкл Сипсер (1997). Введение в теорию вычислений . Бостон / Массачусетс: PWS Publishing Co. Здесь: Def.7.2, стр.227
- ^ а б Cormen, Thomas H .; Leiserson, Charles E .; Ривест, Рональд Л. (2009). Введение в алгоритмы (3-е изд.). Кембридж / Массачусетс: MIT Press. п. 45 . ISBN 978-0-262-53305-8.
Поскольку θ ( g ( n )) является набором, мы могли бы написать « f ( n ) ∈ θ ( g ( n ))», чтобы указать, что f ( n ) является членом θ ( g ( n )). Вместо этого мы обычно будем писать f ( n ) = θ ( g ( n )), чтобы выразить то же понятие. Вы можете быть сбиты с толку, потому что мы таким образом злоупотребляем равенством, но позже в этом разделе мы увидим, что это имеет свои преимущества.
- ^ Кормен, Томас; Лейзерсон, Чарльз; Ривест, Рональд; Стейн, Клиффорд (2009). Введение в алгоритмы (третье изд.). Массачусетский технологический институт. п. 53 .
- ^ Хауэлл, Родни. «Об асимптотической записи с несколькими переменными» (PDF) . Проверено 23 апреля 2015 .
- ^ Н.Г. де Брёйн (1958). Асимптотические методы анализа . Амстердам: Северная Голландия. С. 5–7. ISBN 978-0-486-64221-5.
- ^ а б Грэм, Рональд ; Кнут, Дональд ; Паташник, Орен (1994). Конкретная математика (2-е изд.). Ридинг, Массачусетс: Аддисон – Уэсли. п. 446. ISBN. 978-0-201-55802-9.
- ^ Дональд Э. Кнут, Искусство компьютерного программирования. Vol. 1. Фундаментальные алгоритмы, третье издание, Addison Wesley Longman, 1997. Раздел 1.2.11.1.
- ^ Рональд Л. Грэм, Дональд Э. Кнут и Орен Паташник, Конкретная математика: Фонд компьютерных наук (2-е изд.) , Аддисон-Уэсли, 1994. Раздел 9.2, с. 443.
- ^ Sivaram Ambikasaran и Эрик Darve, AnБыстрое прямое решение для частичных иерархически полураздельных матриц, J. Scientific Computing 57 (2013), вып. 3, 477–501.
- ^ Сакет Саурабх и Мейрав Зехави,-Max-Cut: An -Временной алгоритм и полиномиальное ядро, Algorithmica 80 (2018), вып. 12, 3844–3860.
- ^ а б Ландау, Эдмунд (1909). Handbuch der Lehre von der Verteilung der Primzahlen [ Справочник по теории распределения простых чисел ] (на немецком языке). Лейпциг: BG Teubner. п. 61.
- ^ Томас Х. Кормен и др., 2001, Введение в алгоритмы, второе издание, гл. 3.1
- ^ Cormen TH, Leiserson CE, Rivest RL, Stein C (2009). Введение в алгоритмы (3-е изд.). Кембридж, Массачусетс: MIT Press. п. 48. ISBN 978-0-262-27083-0. OCLC 676697295 .
- ^ а б в Харди, GH; Литтлвуд, Дж. Э. (1914). «Некоторые проблемы диофантова приближения. Часть II. Тригонометрические ряды, связанные с эллиптическими ϑ-функциями» . Acta Mathematica . 37 : 225. DOI : 10.1007 / BF02401834 .
- ^ a b Г. Х. Харди и Дж. Литтлвуд, «Вклад в теорию дзета-функции Римана и теорию распределения простых чисел», Acta Mathematica , vol. 41, 1916 г.
- ^ Э. Ландау, "Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV." Nachr. Геселл. Wiss. Gött. Math-Phys. Kl. 1924, 137–150.
- ^ a b Александр Ивич. Дзета-функция Римана, глава 9. John Wiley & Sons 1985.
- ^ Джеральд Тененбаум, Введение в аналитическую и вероятностную теорию чисел, Глава I.5. Американское математическое общество, Провиденс, Род-Айленд, 2015.
- ^ а б в г д е Кнут, Дональд (апрель – июнь 1976 г.). «Большой Омикрон, и большая Омега, и большая Тета» (PDF) . Новости SIGACT : 18–24.
- ^ Balcazar, José L .; Габарро, Хоаким. «Неоднородные классы сложности, заданные нижними и верхними границами» (PDF) . RAIRO - Теоретическая информатика и приложения - Теория информатики и приложения . 23 (2): 180. ISSN 0988-3754 . Проверено 14 марта 2017 года .
- ^ Кукер, Фелипе; Бюргиссер, Питер (2013). «A.1 Big Oh, Little Oh и другие сравнения». Условие: геометрия численных алгоритмов . Берлин, Гейдельберг: Springer. С. 467–468. DOI : 10.1007 / 978-3-642-38896-5 . ISBN 978-3-642-38896-5.
- ^ а б Витани, Пол ; Меертенс, Ламберт (апрель 1985 г.). «Большая Омега против диких функций» (PDF) . Новости ACM SIGACT . 16 (4): 56–59. CiteSeerX 10.1.1.694.3072 . DOI : 10.1145 / 382242.382835 .
- ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990]. Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 41–50. ISBN 0-262-03293-7.
- ^ например, он опущен в: Хильдебранд, AJ "Асимптотические обозначения" (PDF) . Кафедра математики. Асимптотические методы анализа . Math 595, осень 2009 г. Урбана, Иллинойс: Университет Иллинойса . Проверено 14 марта 2017 года .
- ^ Cormen, Thomas H .; Leiserson, Charles E .; Ривест, Рональд Л. (2009). Введение в алгоритмы (3-е изд.). Кембридж / Массачусетс: MIT Press. п. 47. ISBN 978-0-262-53305-8.
Когда у нас есть только асимптотическая верхняя граница, мы используем O-нотацию. Для данной функции g ( n ) мы обозначаем через O ( g ( n )) (произносится как «big-oh of g of n » или иногда просто «oh of g of n ») набор функций O ( g ( n )) = { f ( n ): существуют положительные константы c и n 0 такие, что 0 ≤ f ( n ) ≤ cg ( n ) для всех n ≥ n 0 }
- ^ Cormen, Thomas H .; Leiserson, Charles E .; Ривест, Рональд Л. (2009). Введение в алгоритмы (3-е изд.). Кембридж / Массачусетс: MIT Press. п. 49 . ISBN 978-0-262-53305-8.
Когда асимптотическое обозначение стоит отдельно (то есть не в большой формуле) в правой части уравнения (или неравенства), как в n = O (n²), мы уже определили знак равенства для обозначения принадлежности к множеству : n ∈ O (n²). В общем, однако, когда в формуле появляется асимптотическая нотация, мы интерпретируем ее как обозначение некоторой анонимной функции, имя которой нам не нужно. Например, формула 2 n 2 + 3 n + 1 = 2 n 2 + θ ( n ) означает, что 2 n 2 + 3 n + 1 = 2 n 2 + f ( n ), где f ( n ) - некоторая функция в множестве θ ( n ). В этом случае мы полагаем f ( n ) = 3 n + 1, что действительно находится в θ ( n ). Использование асимптотических обозначений таким образом может помочь устранить несущественные детали и беспорядок в уравнении.
- ^ Введение в алгоритмы . Кормен, Томас Х. (Третье изд.). Кембридж, Массачусетс: MIT Press. 2009. с. 63. ISBN 978-0-262-27083-0. OCLC 676697295 .CS1 maint: другие ( ссылка )
- ^ Эрдели, А. (1956). Асимптотические разложения . ISBN 978-0-486-60318-6.
- ↑ EC Titchmarsh, Theory of the Riemann Zeta-Function (Oxford; Clarendon Press, 1951).
- ^ См., Например, «Новая оценка G ( n ) в проблеме Варинга» (рус.). Доклады АН СССР 5, № 5-6 (1934), 249–253. Переведено на английский язык: Избранные произведения / Иван Матвеевич Виноградов; подготовлен Математическим институтом им. В. А. Стеклова АН СССР к 90-летию со дня рождения. Спрингер-Верлаг, 1985.
дальнейшее чтение
- Харди, Г. Х. (1910). Ордена бесконечности: «Infinitärcalcül» Поля дю Буа-Реймона . Издательство Кембриджского университета .
- Кнут, Дональд (1997). «1.2.11: Асимптотические представления». Фундаментальные алгоритмы . Искусство программирования. 1 (3-е изд.). Аддисон-Уэсли. ISBN 978-0-201-89683-1.
- Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001). «3.1: Асимптотические обозначения». Введение в алгоритмы (2-е изд.). MIT Press и McGraw – Hill. ISBN 978-0-262-03293-3.
- Сипсер, Майкл (1997). Введение в теорию вычислений . PWS Publishing. С. 226 –228. ISBN 978-0-534-94728-6.
- Авигад, Джереми; Доннелли, Кевин (2004). Формализация нотации O в Isabelle / HOL (PDF) . Международная совместная конференция по автоматическому мышлению. DOI : 10.1007 / 978-3-540-25984-8_27 .
- Блэк, Пол Э. (11 марта 2005 г.). Блэк, Пол Э. (ред.). "нотация большого О" . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Проверено 16 декабря 2006 года .
- Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). "маленькая нотация" . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Проверено 16 декабря 2006 года .
- Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). «Ω» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Проверено 16 декабря 2006 года .
- Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). «ω» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Проверено 16 декабря 2006 года .
- Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). «Θ» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Проверено 16 декабря 2006 года .
Внешние ссылки
- Рост последовательностей - OEIS (онлайн-энциклопедия целочисленных последовательностей) Wiki
- Введение в асимптотические обозначения [ постоянная мертвая ссылка ]
- Символы Ландау
- Обозначение Big-O - для чего это нужно
- Обозначение Big O на простом английском
- Пример Big O в точности центральной схемы разделенных разностей для первой производной
- Нежное введение в анализ сложности алгоритмов