Обозначение Big O

Обозначение, описывающее ограничивающее поведение Пример записи Big O: f (x) ∈ O (g (x)) as существует c>0 (например, c = 1) и x 0 (например, x 0 = 5) такие, что f (x) ≤ cg (x) всякий раз, когда x ≥ x 0.

Нотация Big O - это математическая запись, которая имеет ограничивающее поведение функции , когда аргумент стремится к определенному значению или бесконечности. Big O является членом семейства нотаций, изобретенных Полом Бахманном, Эдмундом Ландау и другими, которые в совокупности ас именуются нотацией Бахмана - Ландау или>имптотическими нотациями .

В информатике нотация большого O используется для классификации алгоритмов в соответствии с тем, как их время выполнения или требований к пространству растут по мере увеличения размера ввода. В аналитической теории чисел нотация большой буквы O часто используется для выражения границы разницы между арифметической функцией и более понятным приближением; известный пример такой разницы - остаточный член в теореме о простых числах..

Нотация Big O соответствует функциям с одинаковой скоростью роста O.

Буква O используется, потому что скорость роста также называется порядком функции . Описание функций в терминах нотации большого O обычно дает только верхнюю границу скорости функции роста. С обозначением большого количества связанных обозначений, в которых используются символы o, Ω, ω и Θ для описания других видов ограничений на асимптотические скорости роста.

Обозначение Big O также используется во многих других областях получения аналогичных оценок.

Содержание

• 1 Формальное определение
• 2 Пример
• 3 Использование
  • 3.1 Бесконечная асимптотика
  • 3.2 Бесконечная асимптотика
• 4 Свойства
  • 4.1 Продукт
  • 4.2 Сумма
  • 4.3 Умножение на константу
• 5 Несколько чисел
• 6 Обозначения
  • 6.1 Знак равенства
  • 6.2 Другие арифметические операторы
    • 6.2.1 Пример
  • 6.3 Многократное использование
  • 6.4 Набор текста
• 7 Порядки общих функций
• 8 Связанные асимптотические обозначения
  • 8.1 Малые обозначения
  • 8.2 Обозначения Big Omega
    • 8.2.1 Определение Харди - Литтлвуда
      • 8.2.1.1 Простые примеры
    • 8.2.2 Определение К
  • 8.3 Семейство нотаций Бахмана - Ландау
  • 8.4 Использование в информатике
  • 8.5 Другие нотации
  • 8.6 Расширения нотаций Бахмана - Ландау
• 9 Обобщения и связанные с ними употребления
• 10 История (обозначения Бахмана - Ландау, Харди и Виноградова)
• 11 См.
• 12 Ссылки и примечания
• 13 Дополнительная литература
• 14 Внешние ссылки

Формальное определение

Пусть f будет вещественным или комплексная значная функция и g вещественнозначная функция. Пусть обе функции на некотором некотором неограниченном подмножестве положительных вещественных чисел и $g\; (x)\; \{\backslash \; displaystyle\; g\; (x)\}$будет строго положительным для всех достаточно больших значений x. Один записывает

$f\; (x)\; =\; O\; (g\; (x))\; как\; x\; \to \; \infty \; \{\backslash \; displaystyle\; f\; (x)\; =\; O\; \{\backslash \; bigl\; (\}\; g\; (x)\; \{\backslash \; bigr)\}\; \backslash \; quad\; \{\backslash \; text\; \{\; as\}\}\; x\; \backslash \; to\; \backslash \; infty\}$

, если абсолютное значение из $f\; (x)\; \{\backslash \; displaystyle\; f\; (x)\}$является не более чем положительной константой кратное $g\; (x)\; \{\backslash \; displaystyle\; g\; (x)\}$для всех достаточно больших значений x. То есть $f\; (x)\; =\; O\; (g\; (x))\; \{\backslash \; displaystyle\; f\; (x)\; =\; O\; \{\backslash \; bigl\; (\}\; g\; (x)\; \{\backslash \; bigr)\}\}$, если есть существует положительное действительное число M и действительное число x 0 такие, что

$|\; f\; (x)\; |\; \le \; M\; g\; (x)\; для\; всех\; x\; \ge \; x\; 0.\; \{\backslash \; displaystyle\; |\; f\; (x)\; |\; \backslash \; leq\; Mg\; (x)\; \backslash \; quad\; \{\backslash \; text\; \{for\; all\}\}\; x\; \backslash \; geq\; x\_\; \{0\}.\}$

Во многих контекстах предположение, что мы добавляем в росте скорость, когда переменная x стремится к бесконечности, остается неустановленной, и проще записать, что

$f\; (x)\; =\; O\; (g\; (x)).\; \{\backslash \; displaystyle\; f\; (x)\; =\; O\; \{\backslash \; bigl\; (\}\; g\; (x)\; \{\backslash \; bigr)\}.\}$

Обозначение также может быть для описания поведения около некоторого действительного числа a (часто a = 0): мы говорим

$f\; (x)\; =\; O\; (g\; (x))\; как\; x\; \to \; a\; \{\backslash \; displaystyle\; f\; (x)\; =\; O\; \{\backslash \; bigl\; (\}\; g\; (x)\; \{\backslash \; bigr)\}\; \backslash \; quad\; \{\backslash \; text\; \{as\}\; \}\; x\; \backslash \; to\; a\}$

, если существуют положительные числа $\delta \; \{\backslash \; displaystyle\; \backslash \; delta\}$и M такие, что для всех x с ,

$|\; f\; (x)\; |\; \le \; M\; g\; (x).\; \{\backslash \; displaystyle\; |\; f\; (x)\; |\; \backslash \; leq\; Mg\; (x).\}$

График g (x) выбрано ненулевым для значений x , достаточно близких к a, оба из этих определений можно объединить с помощью верхнего предела :

$f\; (Икс)\; =\; О\; (г\; (Икс))\; как\; Икс\; \to \; a\; \{\backslash \; Displaystyle\; F\; (х)\; =\; О\; \{\backslash \; bigl\; (\}\; г\; (х)\; \{\backslash \; bigr)\}\; \backslash \; quad\; \{\backslash \; text\; \{as\}\}\; х\; \backslash \; к\; a\}$

, если

Пример

В типичном обозначении обозначения O является асимптотическим, то есть относится к очень большим x. В этом случае вкладыш терминов, которые растут «наиболее быстро», в конечном итоге сделает другие неуместными. Сделать следующие правила упрощения:

• Если f (x) является суммой нескольких элементов, если есть одно наибольшее количество скорости роста, его, все остальные опустить.
• Если f (x) является произведением нескольких факторов, любые константы (члены зависят в произведении, которые не от x) могут быть опущены.

Например, пусть f (x) = 6x - 2x + 5, предположим, что мы хотим упростить эту функцию, используя обозначение O, чтобы описать скорость ее роста по мере приближения x к бесконечности. Эта функция является суммой трех членов: 6x, −2x и 5. Из этих трех членов один с наибольшей скоростью имеет наибольший показатель степени как функция x, а именно 6x. Теперь можно применить второе правило: 6x - это произведение 6 и x, в котором первый множитель не зависит от x. Отсутствие этого множителя приводит к упрощенной форме x. Таким образом, мы говорим, что f (x) - это «большой O» x. Математически мы можем написать f (x) = O (x). Этот расчет можно использовать, используя формальное определение: пусть f (x) = 6x - 2x + 5 и g (x) = x. Применяя формальное определение сверху, утверждение, что f (x) = O (x) эквивалентно его расширению,

$|\; f\; (x)\; |\; \le \; М\; Икс\; 4\; \{\backslash \; Displaystyle\; |\; f\; (x)\; |\; \backslash \; leq\; Mx\; ^\; \{4\}\}$

для подходящего выбора из x 0 и M и для всех x>x 0. Чтобы доказать это, пусть x 0 = 1 и M = 13. Тогда для всех x>x 0:

$|\; 6\; х\; 4\; -\; 2\; х\; 3\; +\; 5\; |\; \le \; 6\; х\; 4\; +\; |\; 2\; х\; 3\; |\; +\; 5\; \le \; 6\; x\; 4\; +\; 2\; x\; 4\; +\; 5\; x\; 4\; =\; 13\; x\; 4\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; |\; 6x\; ^\; \{4\}\; -2x\; ^\; \{3\}\; +5\; |\; \backslash \; leq\; 6x\; ^\; \{4\}\; +\; |\; 2x\; ^\; \{3\}\; |\; +5\; \backslash \backslash \; \backslash \; leq\; 6x\; ^\; \{4\}\; +\; 2x\; ^\; \{4\}\; +\; 5x\; ^\; \{4\}\; \backslash \backslash \; =\; 13x\; ^\; \{4\}\; \backslash \; end\; \{align\}\}\}$

так

$|\; 6\; х\; 4\; -\; 2\; х\; 3\; +\; 5\; |\; \le \; 13\; х\; 4.\; \{\backslash \; displaystyle\; |\; 6x\; ^\; \{4\}\; -2x\; ^\; \{3\}\; +5\; |\; \backslash \; leq\; 13x\; ^\; \{4\}.\}$

Использование

Нотация Big O имеет две основные области применения:

• В математике он обычно используется для описания того, насколько конечный ряд приближается к заданной функции, особенно в случае усеченного ряда Тейлора или асимптотическое расширение
• В информатике это полезно при анализа алгоритмов

. В обоих приложениях функция g (x), обычно выбираемая внутри O (...), обычно выбрано как можно более общие, опуская постоянные множители и члены более низкого порядка.

Есть два формально близких, но выделяющихся, использование этой нотации:

• бесконечная астотика
• бесконечно малая асимптотика.

Это различие только в применении, а не в принципе, однако - формальное определение «большого О» одинаково для каждого случая, только с разными ограничениями для аргумента функции.

Бесконечная асимптотика

Графики функций, обычно используемых при анализе алгоритмов, показывающие количество операций в зависимости от размера ввода для каждой функции

Нотация Big O полезна при анализамов для эффективность. Например, время (или количество шагов), необходимое для решения задачи размера n, может оказаться равным T (n) = 4n - 2n + 2. По мере увеличения n член n станет доминирующим, так что всеми остальными членами можно пренебречь - например, когда n = 500, член 4n в 1000 раз больше член 2n. Игнорирование произвольного незначительного влияния на значение выражения для большинства целей. Кроме того, коэффициенты становятся неактуальными при сравнении с другими порядком выражения, например, выражением, содержащим термин n или n. Даже если T (n) = 1000000n, если U (n) = n, последнее всегда будет больше, чем 1000000 (T (1000000) = 1000000 = U (1000000)). Кроме того, количество шагов зависит от деталей модели машины, на которой работает алгоритм, разные типы машин обычно различаются лишь на постоянный коэффициент количества шагов, необходимых для выполнения алгоритма. Таким образом, большая нотация O фиксирует то, что осталось: мы пишем либо

$T\; (n)\; =\; O\; (n\; 2)\; \{\backslash \; displaystyle\; T\; (n)\; =\; O\; (n\; ^\; \{2\})\}$

, либо

$T\; (n)\; \in \; O\; (n\; 2)\; \{\backslash \; displaystyle\; T\; (n)\; \backslash \; in\; O\; (n\; ^\; \{2\})\}$

и скажем, что алгоритм имеет временную сложность порядка n. Знак «=» не предназначенный для выражения «равно» в его обычном математическом смысле, скорее для более разговорного «есть», поэтому второе выражение иногда считается более точным (см. «Знак равенства " обсуждение ниже), Наиболее термины записываются важные функции. в то время как первый вариант как злоупотребление нотацией.

Бесконечно малые асимптотики

Big O также может сообщить ошибки для описания термина в приближение к математической функции. явно, а наименования действующие значимые термины суммируются в один большой член О. Рассмотрим, например, экспоненциальный ряд и два его выражения, которые могут быть, когда x мало:

$ex\; =\; 1\; +\; x\; +\; x\; 2\; 2\; !\; +\; х\; 3\; 3!\; +\; х\; 4\; 4!\; +\; \cdots \; для\; всех\; x\; =\; 1\; +\; x\; +\; x\; 2\; 2\; +\; O\; (x\; 3)\; при\; x\; \to \; 0\; =\; 1\; +\; x\; +\; O\; (x\; 2)\; при\; x\; \to \; 0\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; e\; ^\; \{x\}\; =\; 1\; +\; x\; +\; \{\backslash \; frac\; \{x\; ^\; \{2\}\}\; \{2!\}\}\; +\; \{\backslash \; Frac\; \{x\; ^\; \{3\}\}\; \{3!\}\}\; +\; \{\backslash \; Frac\; \{x\; ^\; \{4\}\}\; \{4!\}\}\; +\; \backslash \; Dotsb\; \{\backslash \; text\; \{для\; всех\}\}\; x\; \backslash \backslash \; =\; 1\; +\; x\; +\; \{\backslash \; frac\; \{x\; ^\; \{2\}\}\; \{2\}\}\; +\; O\; (x\; ^\; \{3\})\; \{\backslash \; text\; \{as\}\}\; x\; \backslash \; to\; 0\; \backslash \backslash \; =\; 1\; +\; x\; +\; O\; (x\; ^\; \{2\})\; \{\; \backslash \; text\; \{as\}\}\; x\; \backslash \; to\; 0\; \backslash \backslash \backslash \; end\; \{align\}\}\}$

Второе выражение (с O (x)) означает, что абсолютное значение e - (1 + x + x / 2) не больше нескольких постоянных времен | х | когда x достаточно близко к 0.

Свойства

Если функция f может быть записана как конечная сумма других функций, то самая быстрорастущая из них определяет порядок f (n). Например,

$f\; (n)\; =\; 9\; log\; \; n\; +\; 5\; (log\; \; n)\; 4\; +\; 3\; n\; 2\; +\; 2\; n\; 3\; =\; O\; (n\; 3)\; при\; n\; \to \; \infty .\; \{\backslash \; displaystyle\; f\; (n)\; =\; 9\; \backslash \; log\; n\; +\; 5\; (\backslash \; log\; n)\; ^\; \{4\}\; +\; 3n\; ^\; \{2\}\; +\; 2n\; ^\; \{3\}\; =\; O\; (n\; ^\; \{3\})\; \backslash \; qquad\; \{\backslash \; text\; \{\; as\}\}\; n\; \backslash \; to\; \backslash \; infty.\}$

В частности, если функция может быть ограничена полиномом от n, тогда, когда n стремится к бесконечности, можно не использовать члены более низкого порядка полинома. Наборы O (n) и O (c) очень разные. Если c больше единицы, то последнее растет намного быстрее. Функция, которая растет быстрее для любого c, называется суперполиномиальной. Функция, которая растет медленнее, чем любая экспоненциальная функция вида c, называется субэкспоненциальной. Для алгоритма может потребоваться время, которое является суперполиномиальным, так и субэкспоненциальным; Примеры этого включают самые быстрые из алгоритмов целочисленной факторизации и функцию n.

Мы игнорируем любую степень внутри логарифмов. Набор O (log n) точно такой же, как O (log (n)). Логарифмы различаются только постоянным множителем (поскольку log (n) = c log n), и, таким образом, большая нотация игнорирует это. Точно так же бревна с разными постоянными основаниями эквивалентны. С другой стороны, экспоненты с разных основаниями не одного порядка. Например, 2 и 3 не одного порядка.

Изменение положения может или не может повлиять на порядок результирующего алгоритма. Изменение эквивалентно умножению форм на константу, где бы она ни появлялась. Например, если алгоритм выполняется в порядке n, замена n на cn означает, что выполняется в порядке cn, а нотация большого O игнорирует константу c. Это можно записать как cn = O (n). Однако, если алгоритм работает в порядке 2, замена n на cn дает 2 = (2). Это не эквивалентно 2 в целом. Изменение размера также может повлиять на порядок результирующего алгоритма. Например, если время выполнения алгоритма равно O (n) при измерении в терминах числа n цифр входного числа x, то его время выполнения равно O (log x) при измерении как функция самого входного числа x., поскольку n = O (журнал x).

Продукт

$f\; 1\; =\; O\; (g\; 1)\; и\; f\; 2\; =\; O\; (g\; 2)\; \Rightarrow \; f\; 1\; f\; 2\; =\; O\; (g\; 1\; g\; 2)\; \{\backslash \; displaystyle\; f\_\; \{1\}\; =\; O\; (\; g\_\; \{1\})\; \{\backslash \; text\; \{и\}\}\; f\_\; \{2\}\; =\; O\; (g\_\; \{2\})\; \backslash \; Rightarrow\; f\_\; \{1\}\; f\_\; \{2\}\; =\; O\; (g\_\; \{1\}\; g\_\; \{2\})\}$

$е\; \cdot \; O\; (g)\; знак\; равно\; O\; (fg)\; \{\backslash \; displaystyle\; f\; \backslash \; cdot\; O\; (g)\; =\; O\; (fg)\}$

Sum

$f\; 1\; =\; O\; (g\; 1)\; и\; f\; 2\; =\; O\; (g\; 2)\; \Rightarrow \; f\; 1\; +\; f\; 2\; =\; O\; (max\; (g\; 1,\; g\; 2))\; \{\backslash \; displaystyle\; f\_\; \{1\}\; =\; O\; (g\_\; \{1\})\; \{\backslash \; text\; \{and\}\}\; f\_\; \{2\}\; =\; O\; (g\_\; \{\; 2\})\; \backslash \; Rightarrow\; f\_\; \{1\}\; +\; f\_\; \{2\}\; =\; O\; (\backslash \; max\; (g\_\; \{1\},\; g\_\; \{2\}))\}$

Отсюда следует $f\; 1\; =\; O\; (g)\; и\; f\; 2\; Знак\; равно\; O\; (g)\; \Rightarrow \; е\; 1\; +\; f\; 2\; \in \; O\; (g)\; \{\backslash \; displaystyle\; f\_\; \{1\}\; =\; O\; (g)\; \{\backslash \; text\; \{и\}\}\; f\_\; \{2\}\; =\; O\; (g)\; \backslash \; Rightarrow\; f\_\; \{1\; \}\; +\; f\_\; \{2\}\; \backslash \; in\; O\; (g)\}$, что означает, что $O\; (g)\; \{\backslash \; displaystyle\; O\; (g)\}$является выпуклым конусом.

Умножение на константу

Пусть k будет постоянным. Тогда:

$O\; (|\; k\; |\; g)\; =\; O\; (g)\; \{\backslash \; displaystyle\; O\; (|\; k\; |\; g)\; =\; O\; (g)\}$, если k не равно нулю.

$f\; =\; O\; (ж)\; \Rightarrow \; kf\; =\; O\; (g).\; \{\backslash \; displaystyle\; f\; =\; O\; (g)\; \backslash \; Rightarrow\; kf\; =\; O\; (g).\}$

Несколько чисел

Большое O (и маленькое o, Ω и т. д.) также можно использовать с переменными. Чтобы формально определить большой O для нескольких чисел, предположим, что $f\; \{\backslash \; displaystyle\; f\}$и $g\; \{\backslash \; displaystyle\; g\}$- две функции, отсутствие в некотором подмножестве $Р\; n\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{R\}\; ^\; \{n\}\}$. Мы говорим, что

$f\; (x\; \to )\; равно\; O\; (g\; (x\; \to )),\; когда\; x\; \to \; \to \; \infty \; \{\backslash \; displaystyle\; f\; (\{\backslash \; vec\; \{x\}\})\; \{\backslash \; text\; \{is\}\}\; O\; (g\; (\{\backslash \; vec\; \{x\}\}))\; \backslash \; quad\; \{\backslash \; text\; \{as\}\}\; \{\backslash \; vec\; \{x\}\}\; \backslash \; to\; \backslash \; infty\}$

тогда и только тогда, когда

$\exists \; M\; \exists \; C>0\; такой,\; что\; для\; всех\; x\; \to \; с\; xi\; \ge \; M\; для\; некоторого\; i,\; |\; f\; (x\; \to )\; |\; \le \; C\; |\; g\; (x\; \to )\; |.\; \{\backslash \; displaystyle\; \backslash \; exists\; M\; \backslash \; exists\; C>0\; ~\; \{\backslash \; text\; \{такой,\; что\; для\; всех\}\}\; ~\; \{\backslash \; vec\; \{x\}\}\; ~\; \{\backslash \; text\; \{with\}\}\; ~\; x\_\; \{i\}\; \backslash \; geq\; M\; ~\; \{\backslash \; текст\; \{для\; некоторых\}\}\; ~\; i,\; |\; f\; (\{\backslash \; vec\; \{x\}\})\; |\; \backslash \; leq\; C\; |\; g\; (\{\backslash \; vec\; \{x\}\})\; |\; ~.\}$

Эквивалентно условие, что $xi\; \ge \; M\; \{\backslash \; displaystyle\; x\_\; \{i\}\; \backslash \; geq\; M\}$для некоторых $i\; \{\backslash \; displaystyle\; i\}$можно заменить условием, что $\Vert \; x\; \to \; \Vert \; \infty \; \ge \; M\; \{\backslash \; displaystyle\; \backslash \; |\; \{\backslash \; vec\; \{x\}\}\; \backslash \; |\; \_\; \{\backslash \; infty\}\; \backslash \; geq\; M\}$, где $\Vert \; x\; \to \; \Vert \; \infty \; \{\backslash \; displaystyle\; \backslash \; |\; \{\backslash \; vec\; \{x\}\}\; \backslash \; |\; \_\; \{\backslash \; infty\}\}$обозначает норму Чебышева. Например, выражение

$f\; (n,\; m)\; =\; n\; 2\; +\; m\; 3\; +\; О\; (n\; +\; m)\; как\; n,\; m\; \to \; \infty \; \{\backslash \; displaystyle\; f\; (n,\; m)\; =\; n\; ^\; \{2\}\; +\; m\; ^\; \{3\}\; +\; O\; (n\; +\; m)\; \backslash \; quad\; \{\backslash \; text\; \{as\}\}\; n,\; m\; \backslash \; to\; \backslash \; infty\}$

утверждает, что существует константы C и M такие, что

$\forall \; \Vert \; (n,\; m)\; \Vert \; \infty \; \ge \; M:\; |\; g\; (n,\; m)\; |\; \le \; C\; |\; п\; +\; м\; |\; \{\backslash \; displaystyle\; \backslash \; forall\; \backslash \; |\; (n,\; m)\; \backslash \; |\; \_\; \{\backslash \; infty\}\; \backslash \; geq\; M:\; \backslash \; quad\; |\; g\; (n,\; m)\; |\; \backslash \; leq\; C\; |\; n\; +\; m\; |\; ~\}$

где g ( n, m) определяется как

$f\; (n,\; m)\; =\; n\; 2\; +\; m\; 3\; +\; g\; (n,\; m).\; \{\backslash \; displayst\; yle\; f\; (n,\; m)\; =\; n\; ^\; \{2\}\; +\; m\; ^\; \{3\}\; +\; g\; (n,\; m)\; ~.\}$

Это определение допускает все координаты $x\; \to \; \{\backslash \; displaystyle\; ~\; \{\backslash \; vec\; \{\; x\}\}\; ~\}$для увеличения до бесконечности. В частности, выражение

$f\; (n,\; m)\; =\; O\; (nm)\; как\; n,\; m\; \to \; \infty \; \{\backslash \; displaystyle\; f\; (n,\; m)\; =\; O\; (n\; ^\; \{m\})\; \backslash \; quad\; \{\backslash \; text\; \{as\}\; \}\; n,\; m\; \backslash \; to\; \backslash \; infty\; ~\}$

(т.е. $\exists \; C\; \exists \; M\; \forall \; n\; \forall \; m\dots \; \{\backslash \; displaystyle\; \backslash \; exists\; C\; \backslash \; exists\; M\; \backslash \; forall\; n\; \backslash \; forall\; m\; \backslash \; dots\}$) сильно отличается от

$\forall \; m:\; f\; (n,\; m)\; =\; O\; (nm)\; при\; n\; \to \; \infty \; \{\backslash \; displaystyle\; \backslash \; forall\; m\; \backslash \; двоеточие\; ~\; f\; (n,\; m)\; =\; O\; (n\; ^\; \{\; m\})\; \backslash \; quad\; \{\backslash \; text\; \{as\}\}\; n\; \backslash \; to\; \backslash \; infty\}$

(т.е. $\forall \; m\; \exists \; C\; \exists \; M\; \forall \; n\dots \; \{\backslash \; displaystyle\; \backslash \; forall\; m\; \backslash \; exists\; C\; \backslash \; exists\; M\; \backslash \; forall\; n\; \backslash \; point\}$).

Согласно определению, подмножество, на котором определена функция, имеет значение при обобщении операторов от одного параметра до многомерного. Например, если $f\; (n,\; m)\; =\; 1\; \{\backslash \; displaystyle\; ~\; f\; (n,\; m)\; =\; 1\; ~\}$и $g\; (n,\; m)\; =\; n\; \{\backslash \; displaystyle\; ~\; g\; (n,\; m)\; =\; n\; ~\}$, затем $f\; (n,\; m)\; =\; O\; (g\; (n,\; m))\; \{\backslash \; displaystyle\; ~\; f\; (n,\; m)\; =\; O\; (\; g\; (n,\; m))\; ~\}$, если мы ограничим $f\; \{\backslash \; displaystyle\; f\}$и $g\; \{\backslash \; displaystyle\; g\}$на $[1,\; \infty )\; 2\; \{\backslash \; displaystyle\; ~\; [1,\; \backslash \; infty)\; ^\; \{2\}\; ~\}$, но не, если они устойчивые $[0,\; \infty )\; 2\; \{\; \backslash \; displaystyle\; [0,\; \backslash \; infty)\; ^\; \{2\}\; ~\}$.

Это не единственное обобщение большого O на многомерные функции, и практика существует некоторая непоследовательность в выборе определений.

Обозначения

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

Выражение «f (x) равно O (g (x))», как определено выше, обычно записывается как f (x) = O (г (х)). Некоторые считают, что это использование обозначения, поскольку знак равенства может вводить в заблуждение, так как предполагает симметрию, которая нет в этом утверждении. Как говорит де Брюйн, O (x) = O (x) истинно, а O (x) = O (x) - нет. Кнут представил такие утверждения как «односторонние равенства», поскольку если бы стороны могли быть поменяны местами, «мы могли бы вывести нелепые вещи вроде n = n из тождеств n = O (n) и n = O ( n) ".

По этим причинам это было бы более точно использовать обозначение набора и писать f (x) ∈ O (g (x)), считая O (g (x)) классом всех функций h (x), что | h (x) | ≤ C | g (x) | для некоторой константы C. Однако обычно используется знак равенства. «Is» на английском языке: Аристотель - человек, но человек не обязательно Аристотель ».

Другие арифметические операторы

Обозначение Big O может также служить вместе с другими арифметическими операторами в более сложных уравнениях., h (x) + O (f (x)) обозначает набор функций, имеющих рост h (x) плюс часть, рост которой ограничен ростом f (x). Таким образом,

$g\; (x)\; =\; h\; (x)\; +\; O\; (е\; (х))\; \{\backslash \; displayst\; yle\; g\; (x)\; =\; h\; (x)\; +\; O\; (f\; (x))\}$

выражает то же самое, что

$g\; (x)\; -\; h\; (x)\; =\; O\; (f\; (x)).\; \{\backslash \; displaystyle\; g\; (x)\; -h\; (x)\; =\; O\; (f\; (x)).\}$

Пример

Предположим, что алгоритм разрабатывается для работы с набором n элементов. Его разработчики предлагают в поиске функции T (n), которая определяет, сколько времени алгоритму для выполнения (в некотором произвольном измерении времени) с точки зрения количества элементов во входном наборе. Алгоритм работает, сначала вызывая подпрограмму для сортировки элементов в наборе, а затем свои собственные операции. Сортировка имеет известную временную сложность O (n), и после запуска подпрограммы алгоритм должен сделать еще 55n + 2n + 10 шагов, прежде чем он завершится. Таким образом, общая временная сложность алгоритма может быть выражена как T (n) = 55n + O (n). Здесь члены 2n + 10 включены в быстрорастущий O (n). Опять же, это использование игнорирует некоторые формальные символы символов «=», но позволяет использовать нотацию большой буквы O в качестве удобного заполнителя.

Многократное использование

В более сложном использовании O (...) может появляться в разных местах уравнения, даже несколько раз с каждой стороны. Например, для $n\; \to \; \infty \; \{\backslash \; displaystyle\; n\; \backslash \; to\; \backslash \; infty\}$

$(n\; +\; 1)\; 2\; =\; n\; 2\; +\; O\; (n)\; \{\backslash \; displaystyle\; (n\; +\; 1)\; ^\; \{\; 2\}\; =\; n\; ^\; \{2\}\; +\; O\; (n)\}$

$(n\; +\; O\; (n\; 1/2))\; (n\; +\; O\; (log\; \; n))\; 2\; =\; n\; 3\; +\; O\; (n\; 5/2)\; \{\backslash \; Displaystyle\; (п\; +\; О\; (п\; ^\; \{1/2\}))\; (п\; +\; О\; (\backslash \; журнал\; п))\; ^\; \{2\}\; =п\; ^\; \{3\}\; +\; О\; (п\; ^\; \{5/2\})\}$

$п\; O\; (1)\; =\; O\; (en).\; \{\backslash \; displaystyle\; n\; ^\; \{O\; (1)\}\; =\; O\; (e\; ^\; \{n\}).\}$

Смысл таких операторов следующие: для любых функций, которые удовлетворяют каждому O (...) в левой части, есть некоторые функции, так что подстановка всех этих функций в уравнение уравнивает две стороны, O (...) с правой стороны. Например, третье уравнение выше означает: «Для любой функции f (n) = O (1) существует некоторая функция g (n) = O (e) такая, что n = g (n)». В терминах "обозначения числа" выше, это означает, что класс функций, представленный левой стороной, является подмножеством класса функций, представленной правой стороной. В этом случае "=" является формальным символом, который отличается от обычного использования "=" не является симметричным отношением. Таким образом, например, n = O (e) не подразумевает ложное утверждение O (e) = n

Набор текста

Big O состоит только из прописной буквы «O». В отличие от обозначений Бахмана - Ландау с греческими именами, он не требует специальных символов. Тем не менее, часто используются варианты каллиграфии, такие как $O\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{O\}\}\}$, доступны в LaTeX и производных системах набора.

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

Вот список функций, которые обычно встречаются при анализе времени работы алгоритма. В каждом случае c - положительная константа, неограниченно возрастает. Обычно сначала медленнорастущие функции.

Обозначение	Имя	Пример
$O\; (1)\; \{\backslash \; displaystyle\; O\; (1)\}$	константа	Определение четности или нечетности двоичного числа; Вычисление $(-\; 1)\; n\; \{\backslash \; displaystyle\; (-1)\; ^\; \{n\}\}$; Использование таблицы поиска постоянного размера
$O\; (log\; \; log\; \; n)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; \backslash \; log\; n)\}$	двойной логарифмический	Количество сравнений, проведенных для поиска элемента с Использование поиск с интерполяцией в отсортированном массиве равномерно распределенных значений
$O\; (log\; \; n)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n)\}$	логарифмический	Поиск элемента в отсортированном массиве с двоичным поиском или сбалансированным деревом поиска , а также все операции в биномиальной куче
$O\; ((log\; \; n)\; c)\; \{\backslash \; displaystyle\; O\; ((\backslash \; log\; n)\; ^\; \{c\})\}$. $c>1\; \{\backslash \; displaystyle\; \backslash \; scriptstyle\; c>1\}$	полилогарифмический	упорядочение цепочки матриц может быть решено за полилогарифмическое время на <304c .	дробная степень	поиск в дереве kd
$O\; (n)\; \{\backslash \; displaystyle\; O\; (n)\}$	линейный	Нахождение элемента в несортированном списке или в несортированном массиве; сложение двух n-битных целых чисел с помощью переноса пульсации
$O\; (n\; log\; \ast \; \; n)\; \{\backslash \; displaystyle\; O\; (n\; \backslash \; log\; ^\; \{*\}\; n)\}$	n log-star n	Выполнение триангуляция Простое многоугольника с использованием алгоритма Зейделя или алгоритма объединения-поиска. Обратите внимание, что $log\; \ast \; \; (n)\; =\; \{0,\; если\; n\; \le \; 1\; 1\; +\; log\; \ast \; \; (log\; \; n),\; если\; n>1\; \{\backslash \; displaystyle\; \backslash \; log\; ^\; \{*\}\; (n)\; =\; \{\; \backslash \; begin\; \{case\}\; 0,\; \{\backslash \; text\; \{if\}\}\; n\; \backslash \; leq\; 1\; \backslash \backslash \; 1+\; \backslash \; log\; ^\; \{*\}\; (\backslash \; log\; n),\; \{\backslash \; text\; \{if\}\}\; n>1\; \backslash \; end\; \{case\; \}\}\}$
$O\; (n\; log\; \; n)\; =\; O\; (log\; \; n!)\; \{\backslash \; Displaystyle\; O\; (n\; \backslash \; log\; n)\; =\; O\; (\backslash \; log\; n!)\}$	нофмический, логлинейный, квазилинейный или "n log n"	Выполнение быстрого преобразования Фурье ; максимально быстрая сравнительная сортировка ; heapsort и сортировка слиянием
$O\; (n\; 2)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{2\})\}$	квадратичная	Умножение двух n-значных чисел простого алгоритма; простые алгоритмы сортировки, такие как пузырьковая сортировка, сортировка выбора и вставка сортировки ; (худший случай) привязаны к некоторым обычно более быстрым алгоритам сортировки, таким как quicksort, Shellsort и сортировка по
$O\; (nc)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{c\})\}$	многочлен или алгебраический	грамматика, примыкающая к дереву синтаксический анализ; максимальное соответствие для двудольных графов ; нахождение определителя с помощью разложения LU
$L\; n\; [\alpha ,\; c]\; =\; e\; (c\; +\; o\; (1))\; (ln\; \; n)\; \alpha \; (ln\; \; ln\; \; n)\; 1\; -\; \alpha \; \{\backslash \; Displaystyle\; L\_\; \{п\}\; [\backslash \; альфа,\; с]\; =\; е\; ^\; \{(с\; +\; о\; (1))\; (\backslash \; пер\; п)\; ^\; \{\backslash \; альфа\}\; (\backslash \; пер\; \backslash \; пер\; п)\; ^\; \{1-\; \backslash \; альфа\}\; \}\}$.	L-нотация или субэкспоненциальная	Факторизация числа с использованием квадратного сита или сита числового поля
$O\; (cn)\; \{\backslash \; displaystyle\; O\; (\; c\; ^\; \{n\})\}$. $c>1\; \{\backslash \; displaystyle\; \backslash \; scriptstyle\; c>1\}$	экспоненциальное	Поиск (точного) решения коммивояжера с помощью >; определение эквивалентности двух логических операторов с помощью перебора
$O\; (n!)\; \{\backslash \; Displaystyle\; O\; (n!)\}$	факториала	Решение задача коммивояжера с помощью пере; генерация всех неограниченных перестановок poset ; поиск детерминант с разложением Лапласа ; перечисление всех разделов набора

Оператор $f\; (n)\; =\; O\; (n!)\; \{\backslash \; displaystyle\; f\; (n)\; =\; O\; (n!)\}$иногда ослабляется в $f\; (n)\; =\; O\; (nn)\; \{\backslash \; displaystyle\; f\; (n)\; =\; O\; \backslash \; left\; (n\; ^\; \{n\}\; \backslash \; right)\}$, чтобы получить более простые формулы для асимптотической сложности. Для любого $k>0\; \{\backslash \; displaystyle\; k>0\}$и $c>0\; \{\backslash \; displaystyle\; c>0\}$, $O\; (nc\; (log\; \; n)\; k)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{c\}\; (\; \backslash \; log\; n)\; ^\; \{k\})\}$является подмножеством $O\; (nc\; +\; \epsilon )\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{c\; +\; \backslash \; varepsilon\})\}$для любого $\epsilon >0\; \{\backslash \; displaystyle\; \backslash \; varepsilon>0\}$, поэтому его можно рассматривать как полином большего порядка.

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

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

Небольшое обозначение

Интуитивно, утверждение «f (x) есть o (g (x))» (читается «f (x) мало-o от g (x)» ") означает, что g (x) растет намного быстрее, чем f (x). Как и раньше, f будет вещественной или комплексной функцией, а g - вещественная функция, обе на некотором неограниченном подмножестве положительных вещественных чисел, так что g (x) строго положительна для всех достаточно больших значений Икс. Один записывает

$f\; (x)\; =\; o\; (g\; (x))\; как\; x\; \to \; \infty \; \{\backslash \; displaystyle\; f\; (x)\; =\; o\; (g\; (x))\; \backslash \; quad\; \{\backslash \; text\; \{as\}\}\; x\; \backslash \; to\; \backslash \; infty\}$

, если для любой положительной константы ε существует такая константа N, что

$|\; f\; (x)\; |\; \le \; \epsilon \; g\; (x)\; для\; всех\; x\; \ge \; N.\; \{\backslash \; displaystyle\; |\; f\; (x)\; |\; \backslash \; leq\; \backslash \; varepsilon\; g\; (x)\; \backslash \; quad\; \{\backslash \; text\; \{for\; all\}\}\; x\; \backslash \; geq\; N.\}$

Например, у одного есть

$2\; x\; знак\; равно\; о\; (Икс\; 2)\; \{\backslash \; Displaystyle\; 2x\; =\; о\; (х\; ^\; \{2\})\}$и $1\; /\; х\; =\; о\; (1).\; \{\backslash \; Displaystyle\; 1\; /\; х\; =\; о\; (1).\}$

Разница между предыдущим определением для обозначен Первая по крайней мере одна константы M, последняя должна быть какой-либо положительной константы ε, какой бы малой она ни была. Таким образом, нотация small-o делает более сильное утверждение, чем соответствующая нотация big-O: каждая функция, которая является big-O для g, также является большой-O для g, но не каждая функция, которая big-O для g, также является мало-о г. Например, $2\; x\; 2\; =\; O\; (x\; 2)\; \{\backslash \; displaystyle\; 2x\; ^\; \{2\}\; =\; O\; (x\; ^\; \{2\})\}$но $2\; x\; 2\; \ne \; o\; (x\; 2).\; \{\backslash \; displaystyle\; 2x\; ^\; \{2\}\; \backslash \; neq\; o\; (x\; ^\; \{2\}).\}$

Буква g (x) отличен от нуля или, по крайней мере, становится ненулевым после стандартной точки, отношение $f\; (x)\; знак\; равно\; о\; (г\; (х))\; \{\backslash \; displaystyle\; f\; (x)\; =\; o\; (g\; (x))\}$эквивалентно

$lim\; x\; \to \; \infty \; f\; (x)\; g\; (x)\; =\; 0\; \{\backslash \; displaystyle\; \backslash \; lim\; \_\; \{x\; \backslash \; to\; \backslash \; infty\}\; \{\backslash \; frac\; \{f\; (x)\}\; \{g\; (x)\}\}\; =\; 0\}$(именно так Ландау установлен определил маленькую -o нотация).

Мало-о соблюдает ряд арифметических операций. Например,

, если c - ненулевая константа и $f\; =\; o\; (g)\; \{\backslash \; displaystyle\; f\; =\; o\; (g)\}$, то $c\; \cdot \; f\; =\; o\; (g)\; \{\backslash \; displaystyle\; c\; \backslash \; cdot\; f\; =\; o\; (g)\}$и

, если $f\; =\; o\; (F)\; \{\backslash \; displaystyle\; f\; =\; o\; (F)\}$и $g\; =\; o\; (G)\; \{\backslash \; displaystyle\; g\; =\; o\; (G)\}$, затем $f\; \cdot \; g\; =\; o\; (F\; \cdot \; G).\; \{\backslash \; displaystyle\; f\; \backslash \; cdot\; g\; =\; o\; (F\; \backslash \; cdot\; G).\}$

Он также удовлетворяет действию транзитивности :

если $f\; =\; o\; (g)\; \{\backslash \; displaystyle\; f\; =\; о\; (g)\}$и $g\; =\; o\; (h)\; \{\backslash \; displaystyle\; g\; =\; o\; (h)\}$, $f\; =\; o\; (h).\; \{\backslash \; displaystyle\; f\; =\; o\; (h).\}$

Обозначение Big Omega

Еще одно асимптотическое обозначение - $\Omega \; \{\backslash \; displaystyle\; \backslash \; Omega\}$, читается как «big Omega ». К сожалению, есть два широко распространенных и несовместимых определения выражения

$f\; (x)\; =\; \Omega \; (g\; (x))\; \{\backslash \; displaystyle\; f\; (x)\; =\; \backslash \; Omega\; (g\; (x))\}$как $x\; \to \; a,\; \{\backslash \; displaystyle\; x\; \backslash \; rightarrow\; a,\}$,

где a - некоторое действительное число, ∞ или −∞, где f и g - действующие функции, условия в окрестности a, и где g положительна в этой окрестности.

Первый (хронологически) используется в аналитической теории чисел, а другой - в теории сложности вычислений. Когда два встречаются, эта ситуация неизбежно вызовет замешательство.

Определение Харди - Литтлвуда

В 1914 году Годфри Гарольд Харди и Джон Эденсор Литтлвуд представили новый символ $\Omega \; \{\backslash \; displaystyle\; \backslash \; Omega\; \}$, который определяется следующим образом:

$f\; (x)\; =\; \Omega \; (g\; (x))\; \{\backslash \; displaystyle\; f\; (x)\; =\; \backslash \; Omega\; (g\; (x))\}$как $x\; \to \; \infty \; \{\backslash \; displaystyle\; x\; \backslash \; rightarrow\; \backslash \; infty\}$если $lim\; sup\; x\; \to \; \infty \; |\; f\; (x)\; g\; (x)\; |>0.\; \{\backslash \; displaystyle\; \backslash \; limsup\; \_\; \{x\; \backslash \; to\; \backslash \; infty\}\; \backslash \; left\; |\; \{\backslash \; frac\; \{f\; (x)\}\; \{g\; (x)\}\}\; \backslash \; right\; |>0.\}$

Таким образом, $f\; (x)\; =\; \Omega \; (g\; (x))\; \{\backslash \; displaystyle\; f\; (x)\; =\; \backslash \; Omega\; (g\; (x))\}$- отрицание $f\; (x)\; =\; o\; (g\; (x))\; \{\backslash \; displaystyle\; f\; (x)\; =\; o\; (g\; (x))\}$.

В 1916 году те же авторы ввели два новых символа $\Omega \; R\; \{\backslash \; displaystyle\; \backslash \; Omega\; \_\; \{R\}\}$и $\Omega \; L\; \{\backslash \; displaystyle\; \backslash \; Omega\; \_\; \{L\}\}$, определяемый как:

$f\; (x)\; =\; \Omega \; R\; (g\; (x))\; \{\backslash \; displaystyle\; f\; (x)\; =\; \backslash \; Omega\; \_\; \{R\}\; (g\; (x))\}$как $x\; \to \; \infty \; \{\backslash \; displaystyle\; x\; \backslash \; rightarrow\; \backslash \; infty\}$, если $lim\; sup\; x\; \to \; \infty \; е\; (х)\; г\; (х)>0\; \{\backslash \; displaystyle\; \backslash \; limsup\; \_\; \{x\; \backslash \; to\; \backslash \; infty\}\; \{\backslash \; frac\; \{f\; (x)\}\; \{g\; (x)\}\}>0\}$;

$f\; (x)\; =\; \Omega \; L\; (g\; (x))\; \{\backslash \; displaystyle\; f\; (x)\; =\; \backslash \; Omega\; \_\; \{L\}\; (g\; (x))\}$как $x\; \to \; \infty \; \{\backslash \; displaystyle\; x\; \backslash \; rightarrow\; \backslash \; infty\}$если

Эти символы использовались Эдмундом Ландау с теми же значениями в 1924 году. После Ландау эти обозначения больше никогда не использовались именно так; $\Omega \; R\; \{\backslash \; displaystyle\; \backslash \; Omega\; \_\; \{R\}\}$стало $\Omega \; +\; \{\backslash \; displaystyle\; \backslash \; Omega\; \_\; \{+\}\}$и $\Omega \; L\; \{\; \backslash \; displaystyle\; \backslash \; Omega\; \_\; \{L\}\}$стал $\Omega \; -\; \{\backslash \; displaystyle\; \backslash \; Omega\; \_\; \{-\}\}$.

Эти три символа $\Omega ,\; \Omega \; +,\; \Omega \; -\; \{\backslash \; displaystyle\; \backslash \; Omega,\; \backslash \; Omega\; \_\; \{+\},\; \backslash \; Omega\; \_\; \{-\}\}$, а также $f\; (x)\; =\; \Omega \; \pm \; (g\; (x))\; \{\backslash \; displaystyle\; f\; (x)\; =\; \backslash \; Omega\; \_\; \{\backslash \; pm\}\; (g\; (x))\}$(что означает, что $f\; (x)\; =\; \Omega \; +\; (g\; (x))\; \{\backslash \; displaystyle\; f\; (x)\; =\; \backslash \; Omega\; \_\; \{+\}\; (g\; (x))\}$и $f\; (x)\; =\; \Omega \; -\; (g\; (x))\; \{\backslash \; displaystyle\; f\; (x)\; =\; \backslash \; Omega\; \_\; \{-\}\; (g\; (x))\}$удовлетворены), в настоящее время используются в аналитической теории чисел.

Простые примеры

У нас есть

$sin\; \; x\; =\; \Omega \; (1)\; \{\backslash \; displaystyle\; \backslash \; sin\; x\; =\; \backslash \; Omega\; (1)\}$как $x\; \to \; \infty ,\; \{\backslash \; displaystyle\; x\; \backslash \; rightarrow\; \backslash \; infty,\}$

и, точнее,

$sin\; \; x\; Знак\; равно\; \Omega \; \pm \; (1)\; \{\backslash \; displaystyle\; \backslash \; sin\; x\; =\; \backslash \; Omega\; \_\; \{\backslash \; pm\}\; (1)\}$как $x\; \to \; \infty .\; \{\backslash \; displaystyle\; x\; \backslash \; rightarrow\; \backslash \; infty.\}$

Мы имеем

$sin\; \; x\; +\; 1\; =\; \Omega \; (1)\; \{\backslash \; displaystyle\; \backslash \; sin\; x\; +\; 1\; =\; \backslash \; Omega\; (1)\}$как $Икс\; \to \; \infty ,\; \{\backslash \; Displaystyle\; x\; \backslash \; rightarrow\; \backslash \; infty,\}$

и, точнее,

$sin\; \; x\; +\; 1\; =\; \Omega \; +\; (1)\; \{\backslash \; displaystyle\; \backslash \; sin\; x\; +\; 1\; =\; \backslash \; Omega\; \_\; \{\; +\}\; (1)\}$при $x\; \to \; \infty ;\; \{\backslash \; displaystyle\; x\; \backslash \; rightarrow\; \backslash \; infty;\}$

однако

$грех\; \; x\; +\; 1\; \ne \; \Omega \; -\; (1)\; \{\backslash \; displaystyle\; \backslash \; sin\; x\; +\; 1\; \backslash \; not\; =\; \backslash \; Omega\; \_\; \{-\}\; (1)\}$при $x\; \to \; \infty .\; \{\backslash \; displaystyle\; x\; \backslash \; rightarrow\; \backslash \; infty.\}$

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

В 1976 Дональд Кнут опубликовал статью, в которой обосновал использование $\Omega \; \{\backslash \; displaystyle\; \backslash \; Omega\; \}$-символ для описания более сильного свойства. Кнут писал: «Для всех приложений, которые я видел до сих пор в информатике, более строгие требования... гораздо более уместны». Он определил

$f\; (x)\; =\; \Omega \; (g\; (x))\; \iff \; g\; (x)\; =\; O\; (f\; (x))\; \{\backslash \; displaystyle\; f\; (x)\; =\; \backslash \; Omega\; (g\; (x))\; \backslash \; Leftrightarrow\; g\; (\; x)\; =\; O\; (f\; (x))\}$

с комментарием: «Хотя я изменил определение Харди и Литтлвуда для $\Omega \; \{\backslash \; displaystyle\; \backslash \; Omega\}$, я считаю, что так что их определение отнюдь не широко используется, и потому что есть другие способы сказать то, что они хотят сказать, в сравнительно редких случаях, когда их определение применимо. "

Семейство нотатов Бахмана – Ландау

Обозначение	Имя	Описание	Формальное определение	Определение предела
$f\; (n)\; =\; O\; (g\; (n))\; \{\backslash \; displaystyle\; f\; (n)\; =\; O\; (g\; (n))\}$	Большой O; Большой Ох; Большой Омикрон	$|\; f\; |\; \{\backslash \; displaystyle\; |\; f\; |\}$асимптотически ограничено g (с точностью до постоянного множителя)	$\exists \; k>0\; \exists \; n\; 0\; \forall \; n>n\; 0:\; |\; f\; (n)\; |\; \le \; К\; \cdot \; г\; (N)\; \{\backslash \; Displaystyle\; \backslash \; существует\; к>0\; \backslash \; существует\; n\_\; \{0\}\; \backslash \; forall\; n>n\_\; \{0\}\; \backslash \; двоеточие\; |\; f\; (n)\; |\; \backslash \; leq\; k\; \backslash \; cdot\; g\; (n)\}$
$f\; (\; n)\; =\; \Theta \; (g\; (n))\; \{\backslash \; displaystyle\; f\; (n)\; =\; \backslash \; Theta\; (g\; (n))\}$	Большая Theta	f ограничено как сверху, так и снизу с помощью g асимптотически	$\exists \; К\; 1>0\; \exists \; К\; 2>0\; \exists \; N\; 0\; \forall \; N>N\; 0:\; \{\backslash \; Displaystyle\; \backslash \; существует\; k\_\; \{1\}>0\; \backslash \; существует\; k\_\; \{2\}>0\; \backslash \; существует\; n\_\; \{0\}\; \backslash \; forall\; n>n\_\; \{0\}\; \backslash \; двоеточие\}$$k\; 1\; \cdot \; g\; (n)\; \le \; f\; (n)\; \le \; k\; 2\; \cdot \; g\; (\; п)\; \{\backslash \; Displaystyle\; к\_\; \{1\}\; \backslash \; CDOT\; г\; (п)\; \backslash \; Leq\; F\; (п)\; \backslash \; Leq\; K\_\; \{2\}\; \backslash \; CDOT\; г\; (п)\}$	$F\; (п)\; =\; О\; (г\; (п))\; \{\; \backslash \; displaystyle\; f\; (n)\; =\; O\; (g\; (n))\}$и d $f\; (n)\; =\; \Omega \; (g\; (n))\; \{\backslash \; displaystyle\; f\; (n)\; =\; \backslash \; Omega\; (g\; (n))\}$(версия Кнута)
$f\; (n)\; =\; \Omega \; (g\; (n))\; \{\backslash \; displaystyle\; f\; (n)\; =\; \backslash \; Omega\; (g\; (n))\}$	Большая Омега в теории сложности (Кнут)	f асимптотически ограничена g снизу	$\exists \; К>0\; \exists \; N\; 0\; \forall \; N>N\; 0:\; е\; (n)\; \ge \; К\; \cdot \; g\; (n)\; \{\backslash \; displaystyle\; \backslash \; exists\; k>0\; \backslash \; exists\; n\_\; \{0\}\; \backslash \; forall\; n>n\_\; \{0\}\; \backslash \; двоеточие\; f\; (n)\; \backslash \; geq\; k\; \backslash \; cdot\; g\; (n)\}$	$lim\; inf\; n\; \to \; \infty \; е\; (п)\; г\; (п)>0\; \{\backslash \; displaystyle\; \backslash \; liminf\; \_\; \{n\; \backslash \; to\; \backslash \; infty\}\; \{\backslash \; frac\; \{f\; (n)\}\; \{g\; (n)\}\}>0\}$
$f\; (n)\; =\; о\; (г\; (п))\; \{\backslash \; Displaystyle\; е\; (п)\; =\; о\; (г\; (п))\}$	Маленький О; Маленький Oh	f асимптотически преобладает над g		$lim\; n\; \to \; \infty \; |\; е\; (п)\; |\; г\; (п)\; знак\; равно\; 0\; \{\backslash \; displaystyle\; \backslash \; lim\; \_\; \{n\; \backslash \; to\; \backslash \; infty\}\; \{\backslash \; frac\; \{\backslash \; left\; |\; е\; (n)\; \backslash \; право\; |\}\; \{g\; (n)\}\}\; =\; 0\}$
$f\; (n)\; \sim \; g\; (n)\; \{\backslash \; displaystyle\; f\; (n)\; \backslash \; sim\; g\; (n)\}$	Порядка	f равно асимптотически равно g		$lim\; n\; \to \; \infty \; е\; (n)\; g\; (n)\; =\; 1\; \{\backslash \; displaystyle\; \backslash \; lim\; \_\; \{n\; \backslash \; to\; \backslash \; infty\}\; \{f\; (n)\; \backslash \; над\; g\; (n)\}\; =\; 1\}$
$f\; (\; n)\; =\; \omega \; (g\; (n))\; \{\backslash \; displaystyle\; f\; (n)\; =\; \backslash \; omega\; (g\; (n))\}$	Маленькая Омега	f доминирует над g асимптотическим ly	$\forall \; k>0\; \exists \; n\; 0\; \forall \; n>n\; 0:\; |\; f\; (n)\; |>k\; \cdot \; |\; г\; (п)\; |\; \{\backslash \; displaystyle\; \backslash \; forall\; k>0\; \backslash \; exists\; n\_\; \{0\}\; \backslash \; forall\; n>n\_\; \{0\}\; \backslash \; двоеточие\; |\; f\; (n)\; |>k\; \backslash \; cdot\; |\; g\; (n)\; |\}$	$lim\; n\; \to \; \infty \; |\; е\; (n)\; g\; (n)\; |\; знак\; равно\; \infty \; \{\backslash \; displaystyle\; \backslash \; lim\; \_\; \{n\; \backslash \; к\; \backslash \; infty\}\; \backslash \; влево\; |\; \{\backslash \; гидроразрыва\; \{f\; (n)\}\; \{g\; (n)\}\}\; \backslash \; right\; |\; =\; \backslash \; infty\}$
$f\; (n)\; =\; \Omega \; (g\; (n))\; \{\backslash \; displaystyle\; f\; (n)\; =\; \backslash \; Omega\; (g\; (n))\}$	Большая Омега в теории чисел (Харди - Литтлвуд)	$|\; f\; |\; \{\backslash \; displaystyle\; |\; f\; |\}$асимптотически не доминирует g	$\exists \; К>0\; \forall \; N\; 0\; \exists \; N>N\; 0:\; |\; е\; (п)\; |\; \ge \; к\; \cdot \; g\; (\; n)\; \{\backslash \; displaystyle\; \backslash \; exists\; k>0\; \backslash \; forall\; n\_\; \{0\}\; \backslash \; exists\; n>n\_\; \{0\}\; \backslash \; двоеточие\; |\; f\; (n)\; |\; \backslash \; geq\; k\; \backslash \; cdot\; g\; (n)\}$	$lim\; sup\; n\; \to \; \infty \; |\; f\; (n)\; g\; (n)\; |>0\; \{\backslash \; displaystyle\; \backslash \; limsup\; \_\; \{n\; \backslash \; to\; \backslash \; infty\}\; \backslash \; left\; |\; \{\backslash \; frac\; \{f\; (n)\}\; \{g\; (n)\}\}\; \backslash \; right\; |>0\}$

Определения пределов предполагают $g\; (n)>0\; \{\backslash \; displaystyle\; g\; (n)>0\}$для достаточно большого n. Таблица (частично) отсортирована от наименьшего к наибольшему в том смысле, что o, O, Θ, ∼, (версия Кнута) Ω, ω на функции соответствуют <, ≤, ≈, =, ≥,>на вещественной прямой прямой (версия Харди-Литтлвуда Ω, однако, никакому такому описанию) не соответствует).

Информатика использует нотации большого O, большого Theta Θ, маленького o, маленького omega ω и большого Omega Ω Кнута. Аналитическая теория чисел часто использует большие O, маленькие o, большие Omega Ω Харди - Литтлвуда (с индексами +, - или ± или без них) и обозначения $\sim \; \{\backslash \; displaystyle\; \backslash \; sim\}$. Строчная нотация омега ω не так часто используется в анализе.

Использование в информатике

Неформально, особенно в информатике, большая нотация O часто может использоваться несколько иначе для описания асимптотики. плотная граница, где использование большой нотации Theta might может быть более уместным в данном контексте. Например, при рассмотрении функции T (n) = 73n + 22n + 58 все нижеследующее обычно является приемлемым, но более жесткие границы (такие как числа 2 и 3 ниже) обычно предпочтительнее более свободных границ (например, числа 1 ниже).

1. T (n) = O (n)
2. T (n) = O (n)
3. T (n) = Θ (n)

Эквивалентные английские утверждения соответственно:

1. T (n) растет асимптотически не быстрее, чем n
2. T (n) растет асимптотически не быстрее, чем n
3. T (n) растет асимптотически с n.

Итак, хотя все три утверждения верны, в каждом содержится все больше информации. Однако в некоторых полях большая нотация O (цифра 2 в приведенных выше списках) будет использоваться чаще, чем большая нотация Theta (элементы с номером 3 в списках выше). Например, если T (n) представляет время работы недавно разработанного алгоритма для входного размера n, изобретатели и пользователи алгоритма могут быть более склонны устанавливать верхнюю асимптотическую границу того, сколько времени потребуется для выполнения, не делая явное утверждение о нижней асимптотической оценке.

Другие обозначения

В своей книге Введение в алгоритмы, Cormen, Leiserson, Rivest и Стейн рассмотрим набор функций f, которые удовлетворяют

$f\; (n)\; =\; O\; (g\; (n))\; (n\; \to \; \infty ).\; \{\backslash \; displaystyle\; f\; (n)\; =\; O\; (g\; (n))\; \backslash \; quad\; (n\; \backslash \; rightarrow\; \backslash \; infty)\; ~.\}$

В правильной записи этот набор можно, например, назвать O (g), где

$O\; (g)\; =\; \{f:\; \{\backslash \; displaystyle\; O\; (g)\; =\; \backslash \; \{f:\}$существуют положительные константы c и $n\; 0\; \{\backslash \; displaystyle\; n\_\; \{0\}\}$такое, что $0\; \le \; f\; (n)\; \le \; cg\; (n)\; \{\backslash \; displaystyle\; 0\; \backslash \; leq\; f\; (n)\; \backslash \; leq\; cg\; (n)\}$для всех $n\; \ge \; n\; 0\}\; \{\backslash \; displaystyle\; n\; \backslash \; geq\; n\_\; \{0\}\; \backslash \}\}$.

Авторы заявляют, что использование оператора равенства (=) для обозначения членства в множестве, а не оператора членства в множестве (∈) является злоупотреблением нотацией, но в этом есть свои преимущества. Внутри уравнения или неравенства использование асимптотической записи обозначает анонимную функцию в множестве O (g), что исключает члены более низкого порядка и помогает уменьшить несущественный беспорядок в уравнениях, например:

$2\; n\; 2\; +\; 3\; п\; +\; 1\; знак\; равно\; 2\; п\; 2\; +\; О\; (п).\; \{\backslash \; displaystyle\; 2n\; ^\; \{2\}\; +\; 3n\; +\; 1\; =\; 2n\; ^\; \{2\}\; +\; O\; (n).\}$

Расширения нотаций Бахмана – Ландау

Еще одно обозначение, которое иногда используется в информатике, - это Õ (читайте soft-O): f (n) = Õ (g (n)) - это сокращение от f (n) = O (g (n) log g (n)) для некоторого k. По сути, это большая нотация O, игнорирующая логарифмические факторы, потому что эффекты скорости роста некоторой другой суперлогарифмической функции указывают на взрыв скорости роста для входных параметров большого размера, которые более важны для прогнозирования плохой производительности во время выполнения, чем более точные -точечные эффекты, вносимые логарифмическими факторами роста. Это обозначение часто используется, чтобы избежать «придирок» в пределах темпов роста, которые заявлены как слишком жестко ограниченные для рассматриваемых вопросов (поскольку log n всегда o (n) для любой константы k и любого ε>0).

Также обозначение L, определенное как

$L\; n\; [\alpha ,\; c]\; =\; e\; (c\; +\; o\; (1))\; (ln\; \; n)\; \alpha \; (ln\; \; ln\; \; п)\; 1\; -\; \alpha \; \{\backslash \; Displaystyle\; L\_\; \{п\}\; [\backslash \; альфа,\; с]\; =\; е\; ^\; \{(с\; +\; о\; (1))\; (\backslash \; ln\; n)\; ^\; \{\backslash \; альфа\}\; (\backslash \; ln\; \backslash \; ln\; n)\; ^\; \{1\; -\; \backslash \; alpha\}\}\}$

удобен для функций, которые находятся между полиномом и экспонентой в терминах $ln\; \; n\; \{\backslash \; displaystyle\; \backslash \; ln\; n\}$.

Обобщения и связанные с ними виды использования

Обобщение на функции, принимающие значения в любом нормированном векторном пространстве, является простым (заменяя абсолютные значения нормами), где f и g не должны принимать свои значения в одном и том же пространстве.. Также возможно обобщение на функции g, принимающие значения в любой топологической группе . «Ограничивающий процесс» x → x o также можно обобщить, введя произвольную базу фильтра, то есть на направленные сети f и g. Обозначение o может использоваться для определения производных и дифференцируемости в довольно общих пространствах, а также (асимптотической) эквивалентности функций,

$f\; \sim \; g\; ⟺\; (f\; -\; g)\; \in \; о\; (g)\; \{\backslash \; displaystyle\; f\; \backslash \; sim\; g\; \backslash \; iff\; (fg)\; \backslash \; in\; o\; (g)\}$

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

История (обозначения Бахмана – Ландау, Харди и Виноградова)

Символ O был впервые введен теоретиком чисел Полом Бахманном в 1894 году во втором томе его книга Analytische Zahlentheorie ("аналитическая теория чисел "). Теоретик чисел Эдмунд Ландау принял его и, таким образом, был вдохновлен ввести в 1909 году обозначение o; поэтому оба теперь называются символами Ландау. Эти обозначения использовались в прикладной математике в 1950-х годах для асимптотического анализа. Символ $\Omega \; \{\backslash \; displaystyle\; \backslash \; Omega\}$(в смысле «не является o of») был введен в 1914 году Харди и Литтлвудом. Харди и Литтлвуд также ввели в 1918 году символы $\Omega \; R\; \{\backslash \; displaystyle\; \backslash \; Omega\; \_\; \{R\}\}$(«справа») и $\Omega \; L\; \{\backslash \; displaystyle\; \backslash \; Omega\; \_\; \{L\}.\; \}$(«слева»), предшественники современных символов $\Omega \; +\; \{\backslash \; displaystyle\; \backslash \; Omega\; \_\; \{+\}\}$(«не меньше маленького o из») и $\Omega \; -\; \{\backslash \; displaystyle\; \backslash \; Omega\; \_\; \{-\}\}$("не больше, чем малое o"). Таким образом, символы Омеги (с их первоначальным значением) иногда также называют «символами Ландау». Это обозначение $\Omega \; \{\backslash \; displaystyle\; \backslash \; Omega\}$стало широко использоваться в теории чисел, по крайней мере, с 1950-х годов. В 1970-х годах большая O была популяризирована в компьютерных науках Дональдом Кнутом, который ввел соответствующую нотацию Theta и предложил другое определение для обозначения Omega.

Ландау никогда не использовал большую Theta. и маленькие символы омега.

символы Харди были (в терминах современной нотации O)

$f\; \preccurlyeq \; g\; ⟺\; f\; \in \; O\; (g)\; \{\backslash \; displaystyle\; f\; \backslash \; preccurlyeq\; g\; \backslash \; iff\; f\; \backslash \; in\; O\; (g)\}$и $f\; \prec \; g\; ⟺\; f\; \in \; o\; (g);\; \{\backslash \; displaystyle\; f\; \backslash \; prec\; g\; \backslash \; iff\; f\; \backslash \; in\; o\; (g);\}$

(Харди, однако, никогда не определял и не использовал обозначение $\prec \; \prec \; \{\backslash \; displaystyle\; \backslash \; prec\; \backslash !\; \backslash !\; \backslash \; Prec\}$, ни $\ll \; \{\backslash \; displaystyle\; \backslash \; ll\}$, как иногда сообщалось). Харди представил символы $\preccurlyeq \; \{\backslash \; displaystyle\; \backslash \; preccurlyeq\}$и $\prec \; \{\backslash \; displaystyle\; \backslash \; prec\}$(а также некоторые другие символы) в своем трактате 1910 г. " Ордена бесконечности », и использовал их только в трех статьях (1910–1913). В своих почти 400 оставшихся статьях и книгах он постоянно использовал символы Ландау O и o.

Обозначения Харди больше не используются. С другой стороны, в 1930-х годах русский теоретик чисел Иван Матвеевич Виноградов ввел свою нотацию $\ll \; \{\backslash \; displaystyle\; \backslash \; ll\}$, которая все чаще использовалась в теории чисел. вместо обозначения $O\; \{\backslash \; displaystyle\; O\}$. У нас есть

$f\; \ll \; g\; ⟺\; f\; \in \; O\; (g),\; \{\backslash \; displaystyle\; f\; \backslash \; ll\; g\; \backslash \; iff\; f\; \backslash \; in\; O\; (g),\}$

, и часто оба обозначения используются в одной и той же статье.

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

См. Также

• Асимптотическое расширение : Аппроксимация функций, обобщающих формулу Тейлора
• Асимптотически оптимальный алгоритм : фраза, часто используемая для описания алгоритма, имеющего верхнюю границу асимптотически в пределах константы нижней границы проблемы
• Big O в вероятностной нотации : O p,op
• Верхний предел и нижний предел : объяснение некоторых обозначений предела, используемых в этой статье
• Основная теорема ( анализ алгоритмов) : для анализа рекурсивных алгоритмов «разделяй и властвуй» с использованием нотации Big O
• Теорема Нахбина : точный метод ограничения комплексных аналитических функций так, чтобы область сходимости интегральных преобразований можно указать
• Порядок аппроксимации
• Вычислительная сложность математических операций

Ссылки и примечания

Дополнительная литература

• Hardy, GH ( 1910 г.). Ордены Бесконечности: «Бесконечная калькуляция» Поля дю Буа-Реймонда. Cambridge University Press.
• Knuth, Donald (1997). «1.2.11: Асимптотические представления». Фундаментальные алгоритмы. Искусство программирования. 1 (3-е изд.). Аддисон-Уэсли. ISBN 978-0-201-89683-1.
• Кормен, Томас Х. ; Лейзерсон, Чарльз Э. ; Ривест, Рональд Л. ; Стейн, Клиффорд (2001). «3.1: Асимптотические обозначения». Введение в алгоритмы (2-е изд.). MIT Press и McGraw – Hill. ISBN 978-0-262-03293-3.
• Сипсер, Майкл (1997). Введение в теорию вычислений. PWS Publishing. Стр. 226 –228. ISBN 978-0-534-94728-6.
• Авигад, Джереми; Доннелли, Кевин (2004). Формализация O-нотации в Isabelle / HOL (PDF). Международная совместная конференция по автоматизированному мышлению. doi : 10.1007 / 978-3-540-25984-8_27.
• Блэк, Пол Э. (11 марта 2005 г.). Блэк, Пол Э. (ред.). "нотация большого О". Словарь алгоритмов и структур данных. Национальный институт стандартов и технологий США. Проверено 16 декабря 2006 г.
• Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). "Маленькая нотация". Словарь алгоритмов и структур данных. Национальный институт стандартов и технологий США. Проверено 16 декабря 2006 г.
• Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). "Ом". Словарь алгоритмов и структур данных. Национальный институт стандартов и технологий США. Проверено 16 декабря 2006 г.
• Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). "ω". Словарь алгоритмов и структур данных. Национальный институт стандартов и технологий США. Проверено 16 декабря 2006 г.
• Блэк, Пол Э. (17 декабря 2004 г.). Блэк, Пол Э. (ред.). "Θ". Словарь алгоритмов и структур данных. Национальный институт стандартов и технологий США. Проверено 16 декабря 2006 г.

Внешние ссылки

В Викибуке Структуры данных есть страница по теме: Нотация Big-O

Викиверситет решил Задача MyOpenMath с использованием нотации Big-O

• Рост последовательностей - OEIS (Онлайн энциклопедия целочисленных последовательностей) Wiki
• Введение в асимптотические обозначения
• Символы Ландау
• Big- Обозначение O - Чем хороша для
• нотация Big O, объяснение на простом английском
• Пример большого O в точности центральной схемы разделенных разностей для первой производной
• Нежное введение в анализ сложности алгоритма