Обозначение 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 ) = 6 x 4 − 2 x 3 + 5 и предположим, что мы хотим упростить эту функцию, используя обозначение O , чтобы описать скорость ее роста, когда x приближается к бесконечности. Эта функция представляет собой сумму трёх слагаемых: 6 x 4 , −2 x 3 и 5 . Из этих трех членов тот, у которого самая высокая скорость роста, имеет наибольший показатель степени в зависимости от x , а именно 6 x 4 . Теперь можно применить второе правило: 6 х 4 — это произведение 6 и х 4 , в котором первый множитель не зависит от х . Отсутствие этого фактора приводит к упрощенной форме x 4 . Таким образом, мы говорим, что f ( x ) — это «большое О» x4 . Математически мы можем написать f ( x ) = O ( x 4 ) . Подтвердить этот расчет можно с помощью формального определения: пусть f ( x ) = 6 x 4 − 2 x 3 + 5 и g ( x ) = x 4 . Применяя формальное определение, данное выше, утверждение, что f ( x ) = O ( x 4 ) , эквивалентно его расширению,
Обозначение Big O имеет две основные области применения:
В обоих приложениях функция g ( x ) , входящая в число O (·), обычно выбирается как можно более простой, без учета постоянных множителей и членов более низкого порядка.
Есть два формально близких, но заметно различающихся варианта использования этого обозначения :
Однако это различие существует только в применении, а не в принципе - формальное определение «большого О» одинаково для обоих случаев, только с разными пределами для аргумента функции. [ оригинальное исследование? ]
Обозначение Big O полезно при анализе эффективности алгоритмов . Например, время (или количество шагов), необходимое для решения задачи размера n , можно определить как T ( n ) = 4 n 2 − 2 n + 2 . По мере увеличения n член n 2 станет доминировать, так что всеми остальными членами можно пренебречь — например, когда n = 500 , член 4 n 2 в 1000 раз больше, чем член 2 n . Игнорирование последнего оказало бы незначительное влияние на значение выражения для большинства целей. Кроме того, коэффициенты становятся нерелевантными, если мы сравниваем их с выражением любого другого порядка , например с выражением, содержащим термин n 3 или n 4 . Даже если T ( n ) = 1 000 000 n 2 , если U ( n ) = n 3 , последнее всегда будет превышать первое, как только n станет больше 1 000 000 , а именно. Т (1 000 000) = 1 000 000 3 = U (1 000 000) . Кроме того, количество шагов зависит от деталей модели машины, на которой работает алгоритм, но разные типы машин обычно различаются только на постоянный коэффициент количества шагов, необходимых для выполнения алгоритма. Таким образом, большая запись О отражает то, что осталось: мы пишем либо
или
и скажем, что алгоритм имеет временную сложность порядка n 2 . Знак « = » не предназначен для выражения «равно» в его обычном математическом смысле, а скорее для более разговорного «есть», поэтому второе выражение иногда считается более точным (см. обсуждение «Знака равенства» ниже), в то время как первое рассматривается некоторыми как злоупотребление обозначениями . [6]
Большой О также можно использовать для описания ошибки при приближении математической функции. Наиболее значимые термины записываются явно, а затем наименее значимые термины суммируются в один большой термин О. Рассмотрим, например, показательный ряд и два его выражения, которые справедливы, когда x мал:
Среднее выражение (то, что с O ( x 3 )) означает, что абсолютное значение ошибки e x − (1 + x + x 2 /2) не превышает некоторых постоянных раз | х 3 | когда x достаточно близок к 0.
Если функцию f можно записать как конечную сумму других функций, то наиболее быстро растущая из них определяет порядок f ( n ) . Например,
В частности, если функция может быть ограничена полиномом от n , то, когда n стремится к бесконечности , можно игнорировать члены полинома низшего порядка . Множества O ( nc ) и O ( cn ) сильно различаются . Если c больше единицы, то последняя растет гораздо быстрее. Функция, которая растет быстрее, чем nc для любого c , называется суперполиномиальной . Та, которая растет медленнее любой показательной функции вида cn , называется субэкспоненциальной . Алгоритму может потребоваться время, которое является как суперполиномиальным, так и субэкспоненциальным; примеры этого включают самые быстрые известные алгоритмы факторизации целых чисел и функцию n log n .
Мы можем игнорировать любые степени n внутри логарифмов. Набор O (log n ) точно такой же, как O ( log( nc )) . Логарифмы отличаются только постоянным коэффициентом (поскольку 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 ( 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 ) и n 2 = O ( п 2 ) ». [10] В другом письме Кнут также указал, что «знак равенства не симметричен относительно таких обозначений», поскольку в этом обозначении «математики обычно используют знак =, как они используют слово «is» в английском языке: Аристотель — человек, но мужчина не обязательно Аристотель». [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 + O ( n 2 ) . Здесь члены 2 n + 10 включены в состав быстрорастущего O ( n 2 ). Опять же, такое использование игнорирует часть формального значения символа «=", но позволяет использовать большую букву О в качестве своего рода удобного заполнителя.
В более сложном использовании O (·) может появляться в разных местах уравнения, даже несколько раз с каждой стороны. Например, для :
Большой O набирается как заглавная буква «O», выделенная курсивом, как в следующем примере: . [12] [13] В TeX он создается простым вводом O в математическом режиме. В отличие от нотации Бахмана – Ландау, имеющей греческое название, для нее не требуется специальный символ. Однако некоторые авторы вместо этого используют каллиграфический вариант. [14] [15]
Вот список классов функций, которые обычно встречаются при анализе времени работы алгоритма. В каждом случае c является положительной константой, а n неограниченно увеличивается. Медленнорастущие функции обычно перечисляются первыми.
Иногда это утверждение ослабляют, чтобы вывести более простые формулы для асимптотической сложности. Для любого и является подмножеством для любого , поэтому его можно рассматривать как полином большего порядка.
Big 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] Таким образом, обозначение «маленькое-о» является более сильным утверждением , чем соответствующее обозначение «большое-О»: каждая функция, которая является «маленьким-О» для g , также является «большим-О» для g , но не каждая функция, которая является «большим-О» для g , но не каждая функция, которая является «большим-О» для g. g также мало-о от g . Например, но .
Поскольку g ( x ) не равно нулю или, по крайней мере, становится ненулевым после определенной точки, отношение эквивалентно
Little-o поддерживает ряд арифметических операций. Например,
Он также удовлетворяет соотношению транзитивности :
Другое асимптотическое обозначение — читай «большая омега». [18] Существует два широко распространенных и несовместимых определения высказывания.
где a — некоторое действительное число, или , где f и g — действительные функции, определенные в окрестности a , и где g положительна в этой окрестности.
Определение Харди-Литтлвуда используется в основном в аналитической теории чисел , а определение Кнута — в основном в теории сложности вычислений ; определения не эквивалентны.
В 1914 году Годфри Гарольд Харди и Джон Эденсор Литтлвуд представили новый символ [19] , который определяется следующим образом:
Таково отрицание .
В 1916 году те же авторы ввели два новых символа и , определяемые как: [20]
Эти символы использовались Эдмундом Ландау с тем же значением в 1924 году. [21] После Ландау обозначения никогда больше не использовались именно таким образом; стал и стал . [ нужна цитата ]
Эти три символа , а также (имеется в виду, что и оба выполняются) сейчас используются в аналитической теории чисел . [22] [23]
У нас есть
и точнее
У нас есть
и точнее
однако
В 1976 году Дональд Кнут опубликовал статью, оправдывающую использование символа - для описания более сильного свойства. [24] Кнут писал: «Для всех приложений, которые я до сих пор видел в информатике, более строгие требования... гораздо более уместны». Он определил
с комментарием: «Хотя я изменил определение Харди и Литтлвуда , я чувствую себя оправданным, потому что их определение ни в коем случае не широко используется, и потому что есть другие способы сказать то, что они хотят сказать, в сравнительно редких случаях. когда применимо их определение». [24]
Определения пределов предполагают достаточно большие . Таблица (частично) отсортирована от наименьшего к наибольшему в том смысле, что (версия Кнута) на функциях соответствует реальной строке [27] (однако версия Харди-Литтлвуда не соответствует ни одному такому описанию). ).
В информатике используются обозначения «большая -большая тета» , «маленькая -маленькая омега» и «большая омега» Кнута . [28] Аналитическая теория чисел часто использует большую , маленькую , большую Омегу Харди-Литтлвуда (с индексами +, - или ± или без них) и обозначения. [22] Маленькие омега- нотации используются в анализе не так часто. [29]
Неофициально, особенно в информатике, обозначение большого O часто может использоваться несколько по-другому для описания асимптотической жесткой границы, где использование обозначения большого числа Theta Θ может быть более подходящим фактически в данном контексте. [30] Например, при рассмотрении функции T ( n ) = 73 n 3 + 22 n 2 + 58 все следующие значения обычно приемлемы, но более точные границы (такие как числа 2 и 3 ниже) обычно предпочтительнее, чем более свободные границы (например, номер 1 ниже).
Эквивалентные английские утверждения соответственно:
Таким образом, хотя все три утверждения верны, каждое из них содержит все больше информации. Однако в некоторых областях большая нотация О (номер 2 в списках выше) будет использоваться чаще, чем большая нотация Тета (пункты под номером 3 в списках выше). Например, если T ( n ) представляет время работы недавно разработанного алгоритма для входного размера n , изобретатели и пользователи алгоритма могут быть более склонны установить верхнюю асимптотическую границу того, сколько времени потребуется для работы без создания явное утверждение о нижней асимптотической границе.
В своей книге «Введение в алгоритмы» Кормен , Лейзерсон , Ривест и Стайн рассматривают набор функций f , удовлетворяющих условиям
В правильных обозначениях это множество можно, например, назвать O ( g ), где
Авторы заявляют, что использование оператора равенства (=) для обозначения членства в множестве вместо оператора членства в множестве (ε) является злоупотреблением обозначениями, но это имеет преимущества. [6] Внутри уравнения или неравенства использование асимптотических обозначений означает анонимную функцию в множестве O ( g ), что исключает члены низшего порядка и помогает уменьшить несущественный беспорядок в уравнениях, например: [32]
Другое обозначение, иногда используемое в информатике, — Õ (читай soft-O ), которое скрывает полилогарифмические коэффициенты. Используются два определения: некоторые авторы используют f ( n ) = Õ ( g ( n )) как сокращение для f ( n ) = O ( g ( n ) log k n ) для некоторого k , в то время как другие используют его как сокращение для ж ( п ) знак равно О ( г ( п ) журнал k г ( п )) . [33] Когда g ( n ) является полиномиальным по n , разницы нет; однако последнее определение позволяет, например, сказать, что первое определение допускает любую константу k . Некоторые авторы пишут О * с той же целью, что и последнее определение. [34] По сути, это обозначение большого О , игнорирующее логарифмические коэффициенты , поскольку эффекты скорости роста некоторой другой суперлогарифмической функции указывают на взрывной темп роста для входных параметров большого размера, что более важно для прогнозирования плохой производительности во время выполнения. чем более мелкие эффекты, вносимые фактором(ами) логарифмического роста. Это обозначение часто используется, чтобы избежать «придирок» к темпам роста, которые заявлены как слишком жестко ограниченные для рассматриваемых вопросов (поскольку log k 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-х годах для асимптотического анализа. [35] Символ (в смысле «не является буквой о ») был введен в 1914 году Харди и Литтлвудом. [19] Харди и Литтлвуд также ввели в 1916 году символы («правый») и («левый»), [20] предшественники современных символов («не меньше маленькой буквы») и («не больше чем маленькое о»). Таким образом, символы Омеги (с их первоначальным значением) иногда также называют «символами Ландау». Это обозначение стало широко использоваться в теории чисел, по крайней мере, с 1950-х годов. [36] В 1970-х годах большая буква О была популяризирована в информатике Дональдом Кнутом , который ввёл родственную нотацию Тета и предложил другое определение нотации Омега. [24]
Ландау никогда не использовал символы большой теты и маленькой омеги.
Символы Харди были (в современной системе обозначений O )
(Однако Харди никогда не определял и не использовал обозначение , как и , как иногда сообщалось). Харди представил символы и (а также некоторые другие символы) в своем трактате 1910 года «Порядки бесконечности» и использовал их только в трех статьях (1910–1913). В своих почти 400 сохранившихся статьях и книгах он последовательно использовал символы Ландау О и О.
Обозначения Харди больше не используются. С другой стороны, в 1930-е годы [37] русский теоретик чисел Иван Матвеевич Виноградов ввёл свою систему обозначений , которая всё чаще используется в теории чисел вместо обозначений. У нас есть
и часто в одной статье используются оба обозначения.
Большая буква О первоначально означает «порядок» («Ordnung», Bachmann 1894) и, таким образом, является латинской буквой. Ни Бахман, ни Ландау никогда не называли его «Омикрон». Намного позже (1976 г.) этот символ был рассмотрен Кнутом как заглавный омикрон [24] , вероятно, в связи с его определением символа Омега . Цифру ноль использовать нельзя.
Поскольку θ ( g ( n )) является множеством, мы могли бы написать « f ( n ) ∈ θ ( g ( n ))», чтобы указать, что f ( n ) является членом θ ( g ( n )). Вместо этого мы обычно будем писать f ( n ) = θ ( g ( n )) для выражения того же понятия. Вы можете быть сбиты с толку, поскольку таким образом мы злоупотребляем равенством, но позже в этом разделе мы увидим, что это имеет свои преимущества.
{{cite journal}}
: CS1 maint: bot: original URL status unknown (link)Когда у нас есть только асимптотическая верхняя граница, мы используем 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 }
Когда асимптотическое обозначение стоит отдельно (то есть не в более широкой формуле) в правой части уравнения (или неравенства), как в n = O(n 2 ), мы уже определили знак равенства для обозначения множества членство: n ∈ O(n 2 ). Однако в целом, когда в формуле появляется асимптотическое обозначение, мы интерпретируем его как обозначение некоторой анонимной функции, которую мы не хотим называть. Например, формула 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 ) = 3n + 1, что действительно находится в θ ( n ). Использование асимптотических обозначений таким образом может помочь устранить несущественные детали и беспорядок в уравнении.