большого О Обозначение
Подходящее приближение |
---|
Концепции |
Другие основы |
Big O Обозначение — это математическое обозначение, которое описывает предельное поведение функции , когда аргумент стремится к определенному значению или бесконечности. Big O — член семейства обозначений, изобретенных немецкими математиками Паулем Бахманом . [1] Эдмунд Ландау , [2] и другие, которые вместе называются нотацией Бахмана – Ландау или асимптотической нотацией . Буква О была выбрана Бахманом для обозначения Ordnung , что означает порядок приближения .
В информатике обозначение big O используется для классификации алгоритмов в зависимости от того, как растут требования к их времени выполнения или пространству по мере увеличения размера входных данных. [3] В аналитической теории чисел обозначение большого О часто используется для выражения границы разницы между арифметической функцией и более понятным приближением; известный пример такой разницы — остаточный член в теореме о простых числах . Обозначение Big O также используется во многих других областях для получения аналогичных оценок.
Обозначение Big O характеризует функции в соответствии со скоростью их роста: разные функции с одинаковой асимптотической скоростью роста могут быть представлены с использованием одного и того же обозначения O. Буква O используется потому, что скорость роста функции также называется порядком функции . Описание функции в терминах большой записи O обычно дает только верхнюю границу скорости роста функции.
С обозначением большого O связано несколько связанных обозначений, в которых используются символы o , Ω, ω и Θ для описания других видов границ асимптотических скоростей роста.
Формальное определение
[ редактировать ]Позволять , функция, которую нужно оценить, является действительной или комплекснозначной функцией, и пусть , функция сравнения, является вещественнозначной функцией. Пусть обе функции определены на некотором неограниченном подмножестве положительных действительных чисел и быть строго положительным для всех достаточно больших значений . [4] Один пишет и это читается" большой О из «если абсолютное значение не более чем положительное постоянное кратное для всех достаточно больших значений . То есть, если существует положительное действительное число и реальное число такой, что Во многих контекстах предположение о том, что нас интересуют темпы роста как переменная уходит в бесконечность, остается неустановленным, и проще пишут, что Обозначения также можно использовать для описания поведения около какого-то действительного числа (часто, ): мы говорим если существуют положительные числа и такой, что для всех определенных с , Как выбирается строго положительным для таких значений оба этих определения можно унифицировать, используя верхний предел : если И в обоих этих определениях предельная точка (ли или нет) является точкой кластера доменов и , я. е., в каждом районе должно быть бесконечно много общих точек. Более того, как указано в статье о пределе нижнего и верхнего предела , (по крайней мере, на расширенной линии действительных чисел ) всегда существует.
В информатике распространено несколько более строгое определение: и оба должны быть функциями от некоторого неограниченного подмножества целых положительных чисел до неотрицательных действительных чисел; затем если существуют положительные целые числа и такой, что для всех . [5]
Пример
[ редактировать ]В типичном использовании обозначение O является асимптотическим, то есть оно относится к очень большим x . В таких условиях вклад терминов, которые растут «наиболее быстро», в конечном итоге сделает остальные нерелевантными. В результате можно применить следующие правила упрощения:
- Если f ( x ) представляет собой сумму нескольких членов, если есть один из них с наибольшей скоростью роста, его можно сохранить, а все остальные опустить.
- Если f ( x ) является произведением нескольких факторов, любые константы (факторы в произведении, не зависящие от x ) можно опустить.
Например, пусть f ( x ) = 6 x 4 − 2 х 3 + 5 , и предположим, что мы хотим упростить эту функцию, используя обозначение O , чтобы описать скорость ее роста, когда x приближается к бесконечности. Эта функция представляет собой сумму трёх слагаемых: 6 x 4 , −2 х 3 , и 5 . Из этих трех слагаемых наибольшую скорость роста имеет тот, у которого наибольший показатель степени зависит от x , а именно 6 x 4 . Теперь можно применить второе правило: 6 х 4 является произведением 6 и x 4 в котором первый множитель не зависит от x . Отсутствие этого фактора приводит к упрощенной форме x 4 . Таким образом, мы говорим, что f ( x ) является «большим O» x 4 . Математически мы можем записать f ( x ) = O ( x 4 ) . Подтвердить этот расчет можно с помощью формального определения: пусть f ( x ) = 6 x 4 − 2 х 3 + 5 и г ( х ) = х 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 п + 2 . По мере того, как n становится большим, n 2 член станет доминировать, так что всеми остальными членами можно будет пренебречь — например, когда n = 500 , член 4 n 2 в 1000 раз больше 2n члена . Игнорирование последнего окажет незначительное влияние на значение выражения для большинства целей. Кроме того, коэффициенты становятся нерелевантными, если мы сравниваем их с любым другим порядком выражения, например с выражением, содержащим термин n 3 или н 4 . Даже если T ( n ) = 1 000 000 n 2 , если U ( п ) = п 3 , последнее всегда будет превышать первое, как только n станет больше 1 000 000 , а именно. Т (1 000 000) = 1 000 000 3 = U (1 000 000) . Кроме того, количество шагов зависит от деталей модели машины, на которой работает алгоритм, но разные типы машин обычно различаются только на постоянный коэффициент количества шагов, необходимых для выполнения алгоритма. Таким образом, большая запись О отражает то, что осталось: мы пишем либо
или
и скажем, что алгоритм имеет порядок n 2 временная сложность. Знак « = » не предназначен для выражения «равно» в его обычном математическом смысле, а скорее для более разговорного «есть», поэтому второе выражение иногда считается более точным (см. обсуждение « знака равенства » ниже), в то время как первое рассматривается некоторыми как злоупотребление обозначениями . [6]
Бесконечно малая асимптотика
[ редактировать ]Большой О также можно использовать для описания ошибки при приближении математической функции. Наиболее значимые термины записываются явно, а затем наименее значимые термины суммируются в один большой термин О. Рассмотрим, например, показательный ряд и два его выражения, которые справедливы, когда x мало:
Среднее выражение (то, что с O ( x 3 )) означает абсолютное значение ошибки e х − (1 + х + х 2 /2) не более чем несколько постоянных времен | х 3 | когда x достаточно близок к 0.
Характеристики
[ редактировать ]Если функцию f можно записать как конечную сумму других функций, то наиболее быстро растущая из них определяет порядок f ( n ) . Например,
В частности, если функция может быть ограничена полиномом от n , то, когда n стремится к бесконечности , можно игнорировать низшего порядка члены полинома . Множества O ( n с ) и O ( c н ) очень разные. Если c больше единицы, то последняя растет гораздо быстрее. Функция, которая растет быстрее, чем n с для любого c называется суперполиномиальным . Та, которая растет медленнее, чем любая показательная функция вида c н называется субэкспоненциальным . Алгоритму может потребоваться время, которое является как суперполиномиальным, так и субэкспоненциальным; примеры этого включают самые быстрые известные алгоритмы факторизации целых чисел и функцию n войти в систему .
Мы можем игнорировать любые степени n внутри логарифмов. Множество O (log n ) точно такое же, как и O (log( n с )) . Логарифмы отличаются лишь постоянным множителем (поскольку log( n с ) = c log n ), и поэтому большая запись O игнорирует это. Аналогично, бревна с разными постоянными базами эквивалентны. С другой стороны, экспоненты с разными основаниями не одного порядка. Например, 2 н и 3 н не одного порядка.
Изменение единиц измерения может повлиять или не повлиять на порядок результирующего алгоритма. Изменение единиц эквивалентно умножению соответствующей переменной на константу, где бы она ни появлялась. Например, если алгоритм выполняется в порядке n 2 , замена n на cn означает, что алгоритм работает в порядке c 2 н 2 , а большое обозначение O игнорирует константу c 2 . Это можно записать как c 2 н 2 = О( п 2 ) . Однако если алгоритм работает в порядке 2 н , замена n на cn дает 2 CN = (2 с ) н . Это не эквивалентно 2 н в общем. Изменение переменных также может повлиять на порядок результирующего алгоритма. Например, если время выполнения алгоритма равно O ( n ), если оно измерено в терминах числа n цифр , входного числа x то время его выполнения равно O (log x ), если оно измерено как функция входного числа x. самого , потому что n = O (log x ) .
Продукт
[ редактировать ]Сумма
[ редактировать ]Если и затем . Отсюда следует, что если и затем . Другими словами, это второе утверждение говорит, что представляет собой выпуклый конус .
Умножение на константу
[ редактировать ]Пусть k — ненулевая константа. Затем . Другими словами, если , затем
Несколько переменных
[ редактировать ]Большое О (и маленькое О, Ω и т. д.) также можно использовать с несколькими переменными. Чтобы формально определить большое O для нескольких переменных, предположим, что и две функции, определенные на некотором подмножестве . Мы говорим
тогда и только тогда, когда существуют константы и такой, что для всех с для некоторых [7] Эквивалентно, условие, что для некоторых можно написать , где обозначает чебышевскую норму . Например, заявление
утверждает, что существуют константы C и M такие, что
всякий раз, когда либо или держит. Это определение позволяет использовать все координаты увеличиваться до бесконечности. В частности, заявление
(т.е. ) сильно отличается от
(т.е. ).
Согласно этому определению, подмножество, на котором определена функция, имеет важное значение при обобщении утверждений от одномерной настройки до многомерной настройки. Например, если и , затем если мы ограничим и к , но не в том случае, если они определены на .
Это не единственное обобщение большого О на многомерные функции, и на практике наблюдается некоторая непоследовательность в выборе определения. [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 ) и н 2 = О ( п 2 ) ». [10] В другом письме Кнут также указал, что «знак равенства не симметричен относительно таких обозначений», поскольку в этой записи «математики обычно используют знак =, как они используют слово «есть» в английском языке: Аристотель — это человек, но человек не обязательно Аристотель». [11]
По этим причинам было бы точнее использовать обозначение множества и писать f ( x ) ∈ O ( g ( x )) (читается как: « f ( x ) является элементом O ( g ( x ))», или « f ( x ) находится в множестве O ( g ( x ))»), думая об O ( g ( x )) как о классе всех функций h ( x ) таких, что | час ( Икс ) | ≤ Cg ( x ) для некоторого положительного действительного числа C . [10] Однако использование знака равенства является общепринятым. [9] [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 + О ( н 2 ) . Здесь члены 2 n + 10 включены в быстрорастущий O ( n 2 ). Опять же, такое использование игнорирует часть формального значения символа «=", но позволяет использовать большую букву О в качестве своего рода удобного заполнителя.
Многократное использование
[ редактировать ]В более сложном использовании O (·) может появляться в разных местах уравнения, даже несколько раз с каждой стороны. Например, для : Смысл таких утверждений следующий: для любых функций, удовлетворяющих каждому O (·) в левой части, существуют некоторые функции, удовлетворяющие каждому O (·) в правой части, такие, что подстановка всех этих функций в уравнение дает две стороны равны. Например, третье уравнение выше означает: «Для любой функции f ( n ) = O (1) существует некоторая функция g ( n ) = O ( e н ) такой, что n ж ( п ) = g ( n ).» С точки зрения «нотации множества» выше, это означает, что класс функций, представленных левой частью, является подмножеством класса функций, представленных правой частью. При этом используйте «= " является формальным символом, который, в отличие от обычного использования "=", не является симметричным отношением . Так, например, n О (1) = О ( и н ) не подразумевает ложное утверждение O ( e н ) = п О (1) .
верстка
[ редактировать ]Большой О набирается как заглавная буква «О», выделенная курсивом, как в следующем примере: . [12] [13] В TeX это создается простым вводом O в математическом режиме. В отличие от нотации Бахмана – Ландау, имеющей греческое название, для нее не требуется специальный символ. Однако некоторые авторы используют каллиграфический вариант. вместо. [14] [15]
Порядки общих функций
[ редактировать ]Вот список классов функций, которые обычно встречаются при анализе времени работы алгоритма. В каждом случае c является положительной константой, а n неограниченно увеличивается. Медленно растущие функции обычно перечисляются первыми.
Обозначения | Имя | Пример |
---|---|---|
постоянный | Нахождение медианного значения для отсортированного массива чисел; Расчет ; постоянного размера Использование справочной таблицы | |
обратная функция Аккермана | Амортизированная сложность каждой операции для структуры данных Disjoint-set. | |
двойной логарифмический | Среднее количество сравнений, потраченных на поиск элемента с использованием интерполяционного поиска в отсортированном массиве равномерно распределенных значений | |
логарифмический | Поиск элемента в отсортированном массиве с помощью двоичного поиска или сбалансированного дерева поиска , а также всех операций в биномиальной куче. | |
полилогарифмический | Упорядочение цепочек матриц можно решить за полилогарифмическое время на параллельной машине с произвольным доступом . | |
дробная мощность | Поиск в дереве kd | |
линейный | Поиск элемента в несортированном списке или в несортированном массиве; добавление двух n -битных целых чисел методом пульсирующего переноса | |
n лог-звезда n | Выполнение триангуляции простого многоугольника с помощью алгоритма Зейделя , где | |
линейный , логлинейный, квазилинейный или « n log n » | Выполнение быстрого преобразования Фурье ; самая быстрая сортировка сравнения ; пирамидальная сортировка и сортировка слиянием | |
квадратичный | Умножение двух n -значных чисел по школьному умножению ; простые алгоритмы сортировки, такие как пузырьковая сортировка , сортировка выбором и сортировка вставкой ; (наихудший случай) привязан к некоторым обычно более быстрым алгоритмам сортировки, таким как быстрая сортировка , Шеллсорт и сортировка по дереву. | |
полиномиальный или алгебраический | Парсинг древовидной грамматики ; максимальное совпадение для двудольных графов ; нахождение определителя с помощью LU-разложения | |
L-нотация или субэкспоненциальная | Факторизация числа с использованием квадратичного сита или сита числового поля | |
экспоненциальный | Нахождение (точного) решения задачи коммивояжера с помощью динамического программирования ; определение эквивалентности двух логических утверждений с помощью перебора | |
факториал | Решение задачи коммивояжера методом перебора; генерация всех неограниченных перестановок ЧУУ ; нахождение определителя с помощью разложения Лапласа ; перечисление всех разделов набора |
Заявление иногда ослабевает до вывести более простые формулы асимптотической сложности. Для любого и , является подмножеством для любого , поэтому его можно рассматривать как многочлен большего порядка.
Связанные асимптотические обозначения
[ редактировать ]Big O широко используется в информатике. Вместе с некоторыми другими родственными обозначениями он образует семейство обозначений Бахмана – Ландау. [ нужна ссылка ]
Обозначение Little-o
[ редактировать ]Интуитивно, утверждение « f ( x ) is o ( g ( x )) » (читай « f ( x ) мало-о от g ( x ) ») означает, что g ( x ) растёт гораздо быстрее, чем f ( x ) . Как и раньше, пусть f — действительная или комплексная функция, а g — действительная функция, обе определены на некотором неограниченном подмножестве положительных действительных чисел , так что g ( x ) строго положительна для всех достаточно больших значений x . Один пишет
если для каждой положительной константы ε существует константа такой, что
Например, у одного есть
- и оба как
Разница между определением обозначения big-O и определением small-o заключается в том, что первое должно быть верным хотя бы для одной константы M , а второе должно выполняться для каждой положительной константы ε , какой бы маленькой она ни была. [17] Таким образом, нотация small-o делает более сильное утверждение, чем соответствующее обозначение big-O: каждая функция, которая является small-o для g , также является big-O для g , но не каждая функция, которая является big-O для g, также является маленький-о г . Например, но .
Поскольку g ( x ) не равно нулю или, по крайней мере, становится ненулевым после определенной точки, соотношение эквивалентно
- (и именно так Ландау [16] первоначально определял нотацию «little-o»).
Little-o поддерживает ряд арифметических операций. Например,
- если c — ненулевая константа и затем , и
- если и затем
Он также удовлетворяет соотношению транзитивности :
- если и затем
Обозначение Большой Омеги
[ редактировать ]Другое асимптотическое обозначение: , читай "большая омега". [18] Существует два широко распространенных и несовместимых определения этого высказывания.
- как ,
где а — некоторое действительное число, , или , где f и g — действительные функции, определенные в окрестности точки a , и где g положительна в этой окрестности.
Определение Харди-Литтлвуда используется в основном в аналитической теории чисел , а определение Кнута — в основном в теории сложности вычислений ; определения не эквивалентны.
Определение Харди – Литтлвуда
[ редактировать ]В 1914 году Годфри Гарольд Харди и Джон Эденсор Литтлвуд представили новый символ. , [19] который определяется следующим образом:
- как если
Таким образом это отрицание .
В 1916 году те же авторы ввели два новых символа. и , определяемый как: [20]
- как если ;
- как если
использовал Эдмунд Ландау в 1924 году. Эти символы с теми же значениями [21] После Ландау обозначения в таком виде больше никогда не использовались; [ нужна ссылка ] стал и стал .
Эти три символа , а также (имеется в виду, что и оба условия удовлетворены), в настоящее время используются в аналитической теории чисел . [22] [23]
Простые примеры
[ редактировать ]У нас есть
- как
и точнее
- как
У нас есть
- как
и точнее
- как
однако
- как
Определение Кнута
[ редактировать ]В 1976 году Дональд Кнут опубликовал статью, оправдывающую использование им -символ для описания более сильного свойства. [24] Кнут писал: «Для всех приложений, которые я до сих пор видел в информатике, более строгие требования… гораздо более уместны». Он определил
с комментарием: «Хотя я изменил определение Харди и Литтлвуда, Я чувствую себя оправданным, потому что их определение ни в коем случае не широко используется, и потому что есть другие способы сказать то, что они хотят сказать, в сравнительно редких случаях, когда их определение применимо». [24]
Семейство обозначений Бахмана – Ландау
[ редактировать ]Обозначения | Имя [24] | Описание | Формальное определение | Определение предела [25] [26] [27] [24] [19] |
---|---|---|---|---|
Маленький О; Маленький Ой; Маленький О; Маленький Ох | f асимптотически доминирует g (для любого постоянного множителя ) | |||
Большой О; Большой Ой; Большой Омикрон | асимптотически ограничена сверху величиной g (с точностью до постоянного множителя ) | |||
(обозначение Харди) или (обозначение Кнута) | Того же порядка, что и (Харди); Большая Тета (Кнут) | f асимптотически ограничен g как выше (с постоянным множителем ) и ниже (с постоянным коэффициентом ) | и | |
Асимптотическая эквивалентность | f равно g асимптотически | |||
Большая Омега в теории сложности (Кнут) | f ограничено снизу g асимптотически | |||
Малая Омега; Маленькая Омега | f доминирует над g асимптотически | |||
Большая Омега в теории чисел (Харди – Литтлвуд) | не доминирует g асимптотически |
Определения пределов предполагают для достаточно большого . Таблица (частично) отсортирована от меньшего к большему, в том смысле, что (версия Кнута) по функциям соответствуют на реальной линии [27] (версия Харди-Литтлвуда , однако не соответствует ни одному такому описанию).
Информатика использует большие , большая Тета , маленький , маленькая омега и большая Омега Кнута обозначения. [28] Аналитическая теория чисел часто использует большие , маленький , Харди , [29] Большая Омега Харди-Литтлвуда (с индексами +, - или ± или без них) и обозначения. [22] Маленькая омега обозначения не используются так часто в анализе. [30]
Использование в информатике
[ редактировать ]Неофициально, особенно в информатике, обозначение big O часто может использоваться несколько по-другому для описания асимптотической жесткой границы, где использование обозначения big Theta Θ может быть более подходящим фактически в данном контексте. [31] Например, при рассмотрении функции T ( n ) = 73 n 3 + 22 н 2 + 58, все перечисленное ниже в целом приемлемо, но более жесткие границы (например, номера 2 и 3 ниже) обычно предпочтительнее более слабых границ (например, номер 1 ниже).
- Т ( п ) знак равно О ( п 100 )
- Т ( п ) знак равно О ( п 3 )
- Т ( п ) = Θ( п 3 )
Эквивалентные английские утверждения соответственно:
- T ( n ) асимптотически растет не быстрее, чем n 100
- T ( n ) асимптотически растет не быстрее, чем n 3
- T ( n ) асимптотически растет с такой же скоростью, как n 3 .
Таким образом, хотя все три утверждения верны, каждое из них содержит все больше информации. Однако в некоторых областях большая нотация О (номер 2 в списках выше) будет использоваться чаще, чем большая нотация Тета (пункты под номером 3 в списках выше). Например, если T ( n ) представляет время работы недавно разработанного алгоритма для входного размера n , изобретатели и пользователи алгоритма могут быть более склонны установить верхнюю асимптотическую границу того, сколько времени потребуется для работы без создания явное утверждение о нижней асимптотической границе.
Другие обозначения
[ редактировать ]В своей книге «Введение в алгоритмы» Кормен , Лейзерсон , Ривест и Стайн рассматривают набор функций f , удовлетворяющих условиям
В правильных обозначениях это множество можно, например, назвать O ( g ), где
Авторы заявляют, что использование оператора равенства (=) для обозначения членства в множестве вместо оператора членства в множестве (ε) является злоупотреблением обозначениями, но это имеет преимущества. [6] Внутри уравнения или неравенства использование асимптотических обозначений означает анонимную функцию из множества O ( g ), что исключает члены низшего порядка и помогает уменьшить несущественный беспорядок в уравнениях, например: [33]
Расширения обозначений Бахмана – Ландау.
[ редактировать ]Другое обозначение, иногда используемое в информатике, — Õ (читай soft-O ), которое скрывает полилогарифмические коэффициенты. Используются два определения: некоторые авторы используют f ( n ) = Õ ( g ( n )) как сокращение для f ( n ) = O ( g ( n ) log к n ) для некоторых k , в то время как другие используют его как сокращение для f ( n ) = O ( g ( n ) log к г ( п )) . [34] Когда g ( n ) является полиномом по n , разницы нет; однако последнее определение позволяет сказать, например, что хотя первое определение допускает для любой константы k . Некоторые авторы пишут О * с той же целью, что и последнее определение. [35] По сути, это обозначение большого О , игнорирующее логарифмические коэффициенты , поскольку эффекты скорости роста некоторой другой суперлогарифмической функции указывают на взрывной темп роста для входных параметров большого размера, который более важен для прогнозирования плохой производительности во время выполнения, чем более точный -балльные эффекты, обусловленные фактором(ами) логарифмического роста. Это обозначение часто используется, чтобы избежать «придирок» к темпам роста, которые считаются слишком жестко ограниченными для рассматриваемых вопросов (поскольку журнал к n всегда равно o ( n е ) для любой константы k и любого ε > 0 ).
Кроме того, L обозначение , определенное как
удобен для функций, которые находятся между полиномиальными и экспоненциальными с точки зрения .
Обобщения и связанные с ними обычаи
[ редактировать ]Обобщение на функции, принимающие значения в любом нормированном векторном пространстве, является простым (замена абсолютных значений нормами), при этом f и g не обязательно принимают свои значения в одном и том же пространстве. обобщение на функции g, принимающие значения в любой топологической группе. Также возможно [ нужна ссылка ] .«Предельный процесс» x → x o также можно обобщить, введя произвольную базу фильтров , т. е. направленные сети f и g . Обозначение o можно использовать для определения производных и дифференцируемости в довольно общих пространствах, а также (асимптотической) эквивалентности функций:
которое является отношением эквивалентности и более ограничительным понятием, чем отношение « 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-х годах для асимптотического анализа. [36] Символ (в смысле «не является о ») было введено в 1914 году Харди и Литтлвудом. [19] Харди и Литтлвуд также ввели в 1916 году символы («право») и ("левый"), [20] предшественники современных символов («не меньше маленькой буквы») и («не больше маленькой буквы»). Таким образом, символы Омеги (с их первоначальным значением) иногда также называют «символами Ландау». Это обозначение стал широко использоваться в теории чисел, по крайней мере, с 1950-х годов. [37]
Символ , хотя раньше оно использовалось в разных значениях, [27] современное определение получил Ландау в 1909 году. [38] и Харди в 1910 году. [39] Чуть выше на той же странице своего трактата Харди определил символ , где означает, что оба и удовлетворены. Эти обозначения до сих пор используются в аналитической теории чисел. [40] [29] В своем трактате Харди также предложил символ , где означает, что для некоторой константы .
В 1970-х годах большая буква О была популяризирована в информатике Дональдом Кнутом , который предложил другое обозначение. для Харди и предложил другое определение обозначения Харди и Литтлвуда Омега. [24]
Два других символа, придуманных Харди, были (в терминах современного обозначения O )
- и
(Однако Харди никогда не определял и не использовал обозначение , ни как иногда сообщалось).Харди ввел символы и (а также уже упомянутые другие символы) в своем трактате 1910 года «Порядки бесконечности» и использовал их только в трех статьях (1910–1913). В своих почти 400 сохранившихся статьях и книгах он последовательно использовал символы Ландау О и О.
Символы Харди и (а также ) больше не используются. С другой стороны, в 1930-е гг. [41] российский теоретик чисел Иван Матвеевич Виноградов ввел свои обозначения , который все чаще используется в теории чисел вместо обозначения. У нас есть
и часто в одной и той же статье используются оба обозначения.
Большая буква О первоначально означает «порядок» («Ordnung», Bachmann 1894) и, таким образом, является латинской буквой. Ни Бахман, ни Ландау никогда не называли его «Омикрон». Намного позже (1976 г.) Кнут рассматривал этот символ как заглавный омикрон , [24] вероятно, в отношении его определения символа Омега . Цифру ноль использовать нельзя.
См. также
[ редактировать ]- Асимптотическая вычислительная сложность
- Асимптотическое разложение : Приближение функций, обобщающих формулу Тейлора.
- Асимптотически оптимальный алгоритм : фраза, часто используемая для описания алгоритма, верхняя граница которого асимптотически находится в пределах константы нижней границы задачи.
- Большое О в обозначениях вероятности : O p , o p
- Предел ниже и предел выше : объяснение некоторых обозначений пределов, используемых в этой статье.
- Основная теорема (анализ алгоритмов) : для анализа рекурсивных алгоритмов «разделяй и властвуй» с использованием нотации Big O.
- Теорема Нахбина : точный метод ограничения комплексных аналитических область сходимости интегральных преобразований. функций, позволяющий определить
- Порядок приближения
- Вычислительная сложность математических операций
Ссылки и примечания
[ редактировать ]- ^ Jump up to: Перейти обратно: а б Бахманн, Пол (1894). Аналитическая теория чисел на ( немецком языке). Том 2. Лейпциг: Тойбнер.
- ^ Jump up to: Перейти обратно: а б Ландау, Эдмунд (1909). теории распределения простых чисел ( Справочник по на немецком языке). Лейпциг: Б. Г. Тойбнер. п. 883.
- ^ Мор, Остин. «Квантовые вычисления в теории сложности и теории вычислений» (PDF) . п. 2. Архивировано (PDF) из оригинала 8 марта 2014 г. Проверено 7 июня 2014 г.
- ^ Ландау, Эдмунд (1909). теории распределения простых чисел ( Справочник по на немецком языке). Лейпциг: Б. Г. Тойбнер. п. 31.
- ^ Майкл Сипсер (1997). Введение в теорию вычислений . Бостон/Массачусетс: PWS Publishing Co. Здесь: Def.7.2, стр.227.
- ^ Jump up to: Перейти обратно: а б Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л. (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) . Архивировано (PDF) из оригинала 24 апреля 2015 г. Проверено 23 апреля 2015 г.
- ^ Jump up to: Перейти обратно: а б Н.Г. де Брейн (1958). Асимптотические методы анализа . Амстердам: Северная Голландия. стр. 5–7. ISBN 978-0-486-64221-5 . Архивировано из оригинала 17 января 2023 г. Проверено 15 сентября 2021 г.
- ^ Jump up to: Перейти обратно: а б с Грэм, Рональд ; Кнут, Дональд ; Паташник, Орен (1994). Конкретная математика (2-е изд.). Ридинг, Массачусетс: Аддисон-Уэсли. п. 446. ИСБН 978-0-201-55802-9 . Архивировано из оригинала 17 января 2023 г. Проверено 23 сентября 2016 г.
- ^ Дональд Кнут (июнь – июль 1998 г.). «Учите исчислению с большой буквой О» (PDF) . Уведомления Американского математического общества . 45 (6): 687. Архивировано (PDF) из оригинала 14 октября 2021 г. Проверено 05 сентября 2021 г. ( Полная версия. Архивировано 13 мая 2008 г. на Wayback Machine )
- ^ Дональд Э. Кнут, Искусство компьютерного программирования. Том. 1. Фундаментальные алгоритмы, третье издание, Аддисон Уэсли Лонгман, 1997. Раздел 1.2.11.1.
- ^ Рональд Л. Грэм, Дональд Э. Кнут и Орен Паташник, Конкретная математика: фонд компьютерных наук (2-е изд.) , Аддисон-Уэсли, 1994. Раздел 9.2, с. 443.
- ^ Шиварам Амбикасаран и Эрик Дарве, Ан Быстрый прямой решатель для частичных иерархически полуразделимых матриц, J. Scientific Computing 57 (2013), вып. 3, 477–501.
- ^ Сакет Саураб и Мейрав Зехави, -Макс-Кат: Ан - Алгоритм времени и полиномиальное ядро, Algorithmica 80 (2018), вып. 12, 3844–3860.
- ^ Jump up to: Перейти обратно: а б Ландау, Эдмунд (1909). теории распределения простых чисел ( Справочник по на немецком языке). Лейпциг: Б. Г. Тойбнер. п. 61.
- ^ Томас Х. Кормен и др., 2001, Введение в алгоритмы, второе издание, гл. 3.1. Архивировано 16 января 2009 г. на Wayback Machine.
- ^ Кормен Т.Х., Лейзерсон К.Э., Ривест Р.Л., Штейн С. (2009). Введение в алгоритмы (3-е изд.). Кембридж, Массачусетс: MIT Press. п. 48. ИСБН 978-0-262-27083-0 . OCLC 676697295 .
- ^ Jump up to: Перейти обратно: а б с Харди, GH; Литтлвуд, Дж. Э. (1914). «Некоторые задачи диофантовой аппроксимации: Часть II. Тригонометрический ряд, связанный с эллиптическими θ-функциями» . Акта Математика . 37 : 225. дои : 10.1007/BF02401834 . Архивировано из оригинала 12 декабря 2018 г. Проверено 14 марта 2017 г.
- ^ Jump up to: Перейти обратно: а б GH Hardy и JE Littlewood, «Вклад в теорию дзета-функции Римана и теорию распределения простых чисел», Acta Mathematica , vol. 41, 1916.
- ^ Э. Ландау, «О количестве точек сетки на определенных участках. IV». Общество сообщений Знать. Бог. Математика-физ. кл. 1924, 137–150.
- ^ Jump up to: Перейти обратно: а б Александр Ивич . Дзета-функция Римана, глава 9. John Wiley & Sons, 1985.
- ^ Джеральд Тененбаум , Введение в аналитическую и вероятностную теорию чисел, Глава I.5. Американское математическое общество, Провиденс, Род-Айленд, 2015.
- ^ Jump up to: Перейти обратно: а б с д и ж Кнут, Дональд (апрель – июнь 1976 г.). «Большой Омикрон, большая Омега и большая Тета» (PDF) . Новости СИГАКТ . 8 (2): 18–24. дои : 10.1145/1008328.1008329 . S2CID 5230246 . Архивировано из оригинала (PDF) 8 апреля 2022 г. Получено 8 декабря 2022 г. - через phil.uu.nl.
- ^ Балькасар, Хосе Л.; Габарро, Хоаким. «Классы неоднородной сложности, определяемые нижними и верхними границами» (PDF) . RAIRO – Теоретическая информатика и приложения – Informatique Théorique et Applications . 23 (2): 180. ISSN 0988-3754 . Архивировано (PDF) из оригинала 14 марта 2017 года . Проверено 14 марта 2017 г. - через Numdam.
- ^ Какер, Фелипе; Бюргиссер, Питер (2013). «A.1 Большое о, маленькое о и другие сравнения» . Условие: Геометрия численных алгоритмов . Берлин, Гейдельберг: Springer. стр. 467–468. дои : 10.1007/978-3-642-38896-5 . ISBN 978-3-642-38896-5 .
- ^ Jump up to: Перейти обратно: а б с Витаньи, Пол ; Меертенс, Ламберт (апрель 1985 г.). «Большая Омега против диких функций» (PDF) . Новости ACM SIGACT . 16 (4): 56–59. CiteSeerX 10.1.1.694.3072 . дои : 10.1145/382242.382835 . S2CID 11700420 . Архивировано (PDF) из оригинала 10 марта 2016 г. Проверено 14 марта 2017 г.
- ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 41–50. ISBN 0-262-03293-7 .
- ^ Jump up to: Перейти обратно: а б Джеральд Тененбаум, Введение в аналитическую и вероятностную теорию чисел, «Обозначения», страница xxiii. Американское математическое общество, Провиденс, Род-Айленд, 2015.
- ^ например, он опущен в: Хильдебранд, А.Дж. «Асимптотические обозначения» (PDF) . Кафедра математики. Асимптотические методы анализа . Math 595, осень 2009 г. Урбана, Иллинойс: Университет Иллинойса. Архивировано (PDF) из оригинала 14 марта 2017 года . Проверено 14 марта 2017 г.
- ^ Кормен и др. (2009) , с. 64: «Многие люди продолжают использовать О -нотацию там, где Θ-нотация технически более точна».
- ^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л. (2009). Введение в алгоритмы (3-е изд.). Кембридж/Массачусетс: MIT Press. п. 47. ИСБН 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 }
- ^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л. (2009). Введение в алгоритмы (3-е изд.). Кембридж/Массачусетс: MIT Press. п. 49 . ISBN 978-0-262-53305-8 .
Когда асимптотическое обозначение стоит отдельно (то есть не в более крупной формуле) в правой части уравнения (или неравенства), как в n = O(n 2 ), мы уже определили знак равенства, обозначающий принадлежность к множеству: n ∈ O(n 2 ). Однако в целом, когда в формуле появляется асимптотическое обозначение, мы интерпретируем его как обозначение некоторой анонимной функции, которую мы не хотим называть. Например, формула 2 n 2 + 3н + 1 = 2н 2 + θ ( n ) означает, что 2 n 2 + 3н + 1 = 2н 2 + f ( n ), где f ( n ) — некоторая функция из множества θ ( n ). В этом случае мы полагаем f ( n ) = 3n +1, что действительно находится в θ ( n ). Использование асимптотических обозначений таким образом может помочь устранить несущественные детали и беспорядок в уравнении.
- ^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2022). Введение в алгоритмы (4-е изд.). Кембридж, Массачусетс: MIT Press. стр. 74–75. ISBN 9780262046305 .
- ^ Андреас Бьорклунд, Торе Хусфельдт и Микко Койвисто (2009). «Настройка разделения посредством включения-исключения» (PDF) . SIAM Journal по вычислительной технике . 39 (2): 546–563. дои : 10.1137/070683933 . Архивировано (PDF) из оригинала 3 февраля 2022 г. Проверено 3 февраля 2022 г. См. разд.2.3, стр.551.
- ^ Эрдели, А. (1956). Асимптотические разложения . Курьерская корпорация. ISBN 978-0-486-60318-6 .
- ^ EC Титчмарш, Теория дзета-функции Римана (Оксфорд; Clarendon Press, 1951)
- ^ Ландау, Эдмунд (1909). теории распределения простых чисел ( Справочник по на немецком языке). Лейпциг: Б. Г. Тойбнер. п. 62.
- ^ Харди, GH (1910). Ордены бесконечности: «Бесконечный расчет» Поля дю Буа-Реймона . Издательство Кембриджского университета . п. 2.
- ^ Харди, GH; Райт, Э.М. (2008) [1-е изд. 1938]. «1.6. Некоторые обозначения». Введение в теорию чисел . Отредактировано Д. Р. Хит-Брауном и Дж. Х. Сильверманом , с предисловием Эндрю Уайлса (6-е изд.). Оксфорд: Издательство Оксфордского университета. ISBN 978-0-19-921985-8 .
- ^ См., например, «Новая оценка G ( n ) в задаче Варинга» (рус.). Доклады Академии наук СССР 5, № 5–6 (1934), 249–253. Переведено на английский язык: Избранные произведения / Иван Матвеевич Виноградов; подготовлен Математическим институтом им. Стеклова АН СССР к его 90-летию. Спрингер-Верлаг, 1985.
Дальнейшее чтение
[ редактировать ]- Харди, GH (1910). Ордены бесконечности: «Бесконечный расчет» Поля дю Буа-Реймона . Издательство Кембриджского университета .
- Кнут, Дональд (1997). «1.2.11: Асимптотические представления». Фундаментальные алгоритмы . Искусство компьютерного программирования. Том. 1 (3-е изд.). Аддисон-Уэсли. ISBN 978-0-201-89683-1 .
- Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001). «3.1: Асимптотические обозначения». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. ISBN 978-0-262-03293-3 .
- Сипсер, Майкл (1997). Введение в теорию вычислений . Издательство ПВС. стр. 226–228 . ISBN 978-0-534-94728-6 .
- Авигад, Джереми; Доннелли, Кевин (2004). Формализация нотации O в Isabelle/HOL (PDF) . Международная совместная конференция по автоматизированному рассуждению. дои : 10.1007/978-3-540-25984-8_27 .
- Блэк, Пол Э. (11 марта 2005 г.). Блэк, Пол Э. (ред.). «обозначение большого О» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Проверено 16 декабря 2006 г.
- Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). «нотация «маленькое о»» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Проверено 16 декабря 2006 г.
- Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). «Ом» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Проверено 16 декабря 2006 г.
- Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). «ю» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Проверено 16 декабря 2006 г.
- Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). «Θ» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Проверено 16 декабря 2006 г.
Внешние ссылки
[ редактировать ]- Рост последовательностей — OEIS (Онлайн-энциклопедия целочисленных последовательностей) Wiki
- Введение в асимптотические обозначения
- Обозначение Big-O – для чего это нужно
- Пример большого О в точности схемы центральной разделенной разности для первой производной. Архивировано 7 октября 2018 г. на Wayback Machine.
- Нежное введение в анализ сложности алгоритмов