Введение

Описывает предельное поведение функции

Нотация «Большое О» — это математическая нотация, описывающая предельное поведение функции, когда аргумент стремится к определенному значению или бесконечности. «Большое О» является частью семейства нотаций, изобретенных немецким математиком Полом Бахманом. В аналитической теории чисел нотация «Большое О» часто используется для выражения границы разности между арифметической функцией и более понятным приближением; известным примером такой разности является остаточный член в теореме о простых числах. Нотация «Большое О» также используется во многих других областях для предоставления аналогичных оценок. Нотация «Большое О» характеризует функции по их скорости роста: различные функции с одинаковой асимптотической скоростью роста могут быть представлены с использованием одной и той же нотации «Большое О». Буква O используется, поскольку скорость роста функции также называют порядком функции. Описание функции в терминах «Большое О» обычно предоставляет только верхнюю границу скорости роста функции. С нотацией «Большое О» связаны несколько связанных нотаций, использующих символы o, Ω, ω и Θ для описания других видов границ асимптотических скоростей роста.

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

Утверждение "f(x) = O(g(x))", как определено выше, обычно записывается как 1=f(x) = O(g(x)). Некоторые считают это злоупотреблением обозначениями, поскольку использование знака равенства может ввести в заблуждение, так как предполагает симметрию, которой в этом утверждении нет. Как говорит де Брюйен, 1=O(x) = O(x²) верно, но 1=O(x²) = O(x) – неверно. Кнут описывает такие утверждения как "односторонние равенства", поскольку, если бы стороны можно было поменять местами, "мы могли бы вывести абсурдные вещи, такие как 1 = n = n² из тождеств 1 = n = O(n²) и 1 = n² = O(n²)". В другом письме Кнут также отметил, что "знак равенства не симметричен по отношению к таким обозначениям", поскольку в этом обозначении "математики обычно используют знак = так же, как слово "is" в английском языке: Аристотель – человек, но человек не обязательно является Аристотелем". По этим причинам было бы точнее использовать обозначение множества и писать f(x) ∈ O(g(x)) (читается как: "f(x) является элементом O(g(x))", или "f(x) принадлежит множеству O(g(x))"), рассматривая O(g(x)) как класс всех функций h(x), таких что |h(x)| ≤ Cg(x) для некоторого положительного действительного числа C. В TeX это достигается простым вводом O в математическом режиме. В отличие от греческих обозначений Бахмана — Ландау, ему не требуется специальный символ. Однако некоторые авторы используют вместо этого каллиграфический вариант.

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

Вот список классов функций, которые обычно встречаются при анализе времени работы алгоритма. В каждом случае c – положительная константа, а n стремится к бесконечности. Функции с более медленным ростом обычно перечисляются первыми. Обозначение Название Пример константа Поиск медианы в отсортированном массиве чисел; Вычисление ; Использование таблицы поиска фиксированного размера двойной логарифмической Среднее количество сравнений при поиске элемента методом интерполяционного поиска в отсортированном массиве равномерно распределенных значений логарифмической Поиск элемента в отсортированном массиве с использованием бинарного поиска или сбалансированного дерева поиска, а также все операции в биномиальной куче полилогарифмической Упорядочение цепочки матриц можно решить за полилогарифмическое время на параллельной машине с произвольным доступом к памяти. дробной степени Поиск в k-d дереве линейной Поиск элемента в несортированном списке или массиве; сложение двух n-битных целых чисел с использованием последовательного переноса n log*n Триангуляция простого многоугольника алгоритмом Зайдела, где линеаримической, логлинейной, квазилинейной или "n log n" Быстрое преобразование Фурье; самая быстрая возможная сортировка сравнением; сортировка кучей и сортировка слиянием квадратичной Умножение двух n-значных чисел методом школьной арифметики; простые алгоритмы сортировки, такие как сортировка пузырьком, сортировка выбором и сортировка вставками; (в худшем случае) оценка для некоторых обычно более быстрых алгоритмов сортировки, таких как быстрая сортировка, Shellsort и сортировка деревьями полиномиальной или алгебраической Разбор грамматики смежных деревьев; поиск максимального паросочетания в двудольном графе; вычисление определителя методом LU-разложения субэкспоненциальной Факторизация числа с использованием квадратичного решета или решета числового поля экспоненциальной Поиск (точного) решения задачи коммивояжера с использованием динамического программирования; определение эквивалентности двух логических выражений методом полного перебора факториальной Решение задачи коммивояжера методом полного перебора; генерация всех перестановок неупорядоченного множества; вычисление определителя методом разложения по Лапласу; перечисление всех разбиений множества. Утверждение иногда ослабляется до для получения более простых формул асимптотической сложности. Для любых и , является подмножеством для любого , поэтому можно рассматривать как многочлен более высокой степени.

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

Большое O широко используется в информатике. Вместе с некоторыми другими связанными обозначениями оно составляет семейство обозначений Бахмана — Ландау.

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

В 1976 году Дональд Кнут опубликовал статью, чтобы обосновать использование им символа для описания более строгого свойства.

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

Обобщение на функции, принимающие значения в любом нормированном векторном пространстве, прямолинейно (заменяются абсолютные значения на нормы), при этом f и g не обязаны принимать значения в одном и том же пространстве. Возможно также обобщение на функции g, принимающие значения в любой топологической группе. "Процесс предельного перехода" x → xo также можно обобщить, вводя произвольную фильтровальную базу, то есть рассматривая направленные сети f и g. О-нотация может быть использована для определения производных и дифференцируемости в весьма общих пространствах, а также (асимптотической) эквивалентности функций, которая является отношением эквивалентности и более строгим понятием, чем отношение "f = Θ(g)", указанное выше. (Оно сводится к lim f/g = 1, если f и g – положительные функции, принимающие вещественные значения.) Например, 2x является Θ(x), но 1 = 2x − x не является o(x).

История (Бахманн-Ландау, Харди и Виноградов)

Символ O был впервые введен теоретиком чисел Полом Бахманом в 1894 году во втором томе его книги Analytische Zahlentheorie ("аналитическая теория чисел"). Теоретик Эдмунд Ландау принял его и, вдохновившись этим, в 1909 году ввел обозначение o; следовательно, оба символа теперь называются символами Ландау. Эти обозначения использовались в прикладной математике в 1950-х годах для асимптотического анализа. Символ (в смысле "не является o") был введен в 1914 году Харди и Литтлвудом. Символ , хотя он использовался ранее с различными значениями, и Харди в 1910 году. Чуть выше на той же странице своего трактата Харди определил символ , где означает, что выполняются оба условия и . Эта нотация до сих пор используется в аналитической теории чисел. В своем трактате Харди также предложил символ , где означает, что для некоторой константы .

В 1970-х годах большое O стало популярным в информатике благодаря Дональду Кнуту, который предложил другую нотацию для обозначения Харди и другое определение для нотации Омега Харди и Литтлвуда. Русский теоретик чисел Иван Матвеевич Виноградов ввел свою нотацию , которая все чаще используется в теории чисел вместо нотации . Мы имеем

и часто оба обозначения используются в одной и той же работе. Изначально большая O обозначала "порядок" ("Ordnung", Бахман, 1894), и, следовательно, является латинской буквой. Ни Бахман, ни Ландау никогда не называли её "Омикрон". Символ был гораздо позже (в 1976 году) воспринят Кнутом как большая буква омикрон, вероятно, в связи с его определением символа Омега. Цифру ноль использовать не следует.