большого О Обозначение
Подходящее приближение |
---|
Концепции |
Другие основы |
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 ) эквивалентно его расширению,
Использование [ править ]
Обозначение 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 (·) может появляться в разных местах уравнения, даже несколько раз с каждой стороны. Например, для :
Набор текста [ править ]
Большой О набирается как заглавная буква «О», выделенная курсивом, как в следующем примере: . [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.
- Теорема Нахбина : точный метод ограничения комплексных аналитических область сходимости интегральных преобразований. функций, позволяющий определить
- Порядок приближения
- Вычислительная сложность математических операций
Ссылки и примечания [ править ]
- ↑ Перейти обратно: Перейти обратно: а б Бахманн, Пол (1894). Analytische Number Theory [ Аналитическая теория чисел ] (на немецком языке). Том 2. Лейпциг: Тойбнер.
- ↑ Перейти обратно: Перейти обратно: а б Ландау, Эдмунд (1909). теории распределения простых чисел ( Справочник по на немецком языке). Лейпциг: Б. Г. Тойбнер. п. 883.
- ^ Мор, Остин. «Квантовые вычисления в теории сложности и теории вычислений» (PDF) . п. 2. Архивировано (PDF) из оригинала 8 марта 2014 г. Проверено 7 июня 2014 г.
- ^ Ландау, Эдмунд (1909). теории распределения простых чисел ( Справочник по на немецком языке). Лейпциг: Б. Г. Тойбнер. п. 31.
- ^ Майкл Сипсер (1997). Введение в теорию вычислений . Бостон/Массачусетс: PWS Publishing Co. Здесь: Def.7.2, стр.227.
- ↑ Перейти обратно: Перейти обратно: а б Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л. (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 г.
- ↑ Перейти обратно: Перейти обратно: а б Н.Г. де Брейн (1958). Асимптотические методы анализа . Амстердам: Северная Голландия. стр. 5–7. ISBN 978-0-486-64221-5 . Архивировано из оригинала 17 января 2023 г. Проверено 15 сентября 2021 г.
- ↑ Перейти обратно: Перейти обратно: а б с Грэм, Рональд ; Кнут, Дональд ; Паташник, Орен (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.
- ↑ Перейти обратно: Перейти обратно: а б Ландау, Эдмунд (1909). теории распределения простых чисел ( Справочник по на немецком языке). Лейпциг: Б. Г. Тойбнер. п. 61.
- ^ Томас Х. Кормен и др., 2001, Введение в алгоритмы, второе издание, гл. 3.1. Архивировано 16 января 2009 г. на Wayback Machine.
- ^ Кормен Т.Х., Лейзерсон К.Э., Ривест Р.Л., Штейн С. (2009). Введение в алгоритмы (3-е изд.). Кембридж, Массачусетс: MIT Press. п. 48. ИСБН 978-0-262-27083-0 . OCLC 676697295 .
- ↑ Перейти обратно: Перейти обратно: а б с Харди, GH; Литтлвуд, Дж. Э. (1914). «Некоторые задачи диофантовой аппроксимации: Часть II. Тригонометрический ряд, связанный с эллиптическими θ-функциями» . Акта Математика . 37 : 225. дои : 10.1007/BF02401834 . Архивировано из оригинала 12 декабря 2018 г. Проверено 14 марта 2017 г.
- ↑ Перейти обратно: Перейти обратно: а б GH Hardy и JE Littlewood, «Вклад в теорию дзета-функции Римана и теорию распределения простых чисел», Acta Mathematica , vol. 41, 1916.
- ^ Э. Ландау, «О количестве точек сетки на определенных участках. IV». Общество сообщений Знать. Бог. Математика-физ. кл. 1924, 137–150.
- ↑ Перейти обратно: Перейти обратно: а б Александр Ивич . Дзета-функция Римана, глава 9. John Wiley & Sons, 1985.
- ^ Джеральд Тененбаум , Введение в аналитическую и вероятностную теорию чисел, Глава I.5. Американское математическое общество, Провиденс, Род-Айленд, 2015.
- ↑ Перейти обратно: Перейти обратно: а б с д и ж Кнут, Дональд (апрель – июнь 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 .
- ↑ Перейти обратно: Перейти обратно: а б с Витаньи, Пол ; Меертенс, Ламберт (апрель 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 .
- ↑ Перейти обратно: Перейти обратно: а б Джеральд Тененбаум, Введение в аналитическую и вероятностную теорию чисел, «Обозначения», страница 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.
- Нежное введение в анализ сложности алгоритмов