«O» большое и «o» малое

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

«O» большое и «o» малое (O и o) — математические обозначения для сравнения асимптотического поведения функций. Используются в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также в информатике и теории алгоритмов.

o(f), «о малое от f» обозначает «бесконечно малое относительно f»[1], пренебрежимо малую величину при рассмотрении f. Смысл термина «О большое» зависит от его области применения, но всегда O(f) растёт не быстрее, чем f (точные определения приведены ниже).

В частности:

  • фраза «сложность алгоритма есть O(f(n))» означает, что с увеличением параметра n, характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем некоторая константа, умноженная на f(n);
  • фраза «функция f(x) является „о“ малым от функции g(x) в окрестности точки p» означает, что с приближением x к p f(x) уменьшается быстрее, чем g(x) (отношение \left |f(x)\right |/\left |g(x)\right | стремится к нулю).

Определения[править | править вики-текст]

Пусть f(x) и g(x) — две функции, определенные в некоторой проколотой окрестности точки x_0, причем в этой окрестности g не обращается в ноль. Говорят, что:

  • f является «O» большим от g при x\to x_0, если существует такая константа C>0, что для всех x из некоторой окрестности точки x_0 имеет место неравенство
    |f(x)| \leqslant C |g(x)|;
  • f является «о» малым от g при x\to x_0, если для любого \varepsilon>0 найдется такая проколотая окрестность U_{x_0}' точки x_0, что для всех x\in U_{x_0}' имеет место неравенство
    |f(x)| < \varepsilon |g(x)|.

Иначе говоря, в первом случае отношение |f|/|g| в окрестности точки x_0 ограничено сверху, а во втором оно стремится к нулю при x\to x_0.

Обозначение[править | править вики-текст]

Обычно выражение «f является O большим (o малым) от g» записывается с помощью равенства f(x) = O(g(x)) (соответственно, f(x) = o(g(x)) ).

Это обозначение очень удобно, но требует некоторой осторожности при использовании (а потому в наиболее элементарных учебниках его могут избегать). Дело в том, что это не равенство в обычном смысле, а несимметричное отношение.

В частности, можно писать

 f(x) = O(g(x)) (или  f(x) = o(g(x)) ),

но выражения

 O(g(x)) = f(x) (или  o(g(x)) = f(x) )

бессмысленны.

Другой пример: при  x \rightarrow 0 верно, что

 O(x^2) = o(x)

но неверно, что

 o(x) = O(x^2) .

При любом x верно

 o(x) = O(x) ,

т.е. бесконечно малая величина является ограниченной, но неверно, что ограниченная величина является бесконечно малой:

 O(x) = o(x) .

Вместо знака равенства методологически правильнее было бы употреблять знаки принадлежности и включения, понимая O({\,}) и o({\,}) как обозначения для множеств функций, то есть, используя запись в форме

 x^3 + x^2 \in O(x^2)

или

\mathop O(x^2)\subset o(x)

вместо, соответственно,

 x^3 + x^2 = O(x^2)

и

\mathop O(x^2) = o(x)

Однако на практике такая запись встречается крайне редко, в основном, в простейших случаях.

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

Другие подобные обозначения[править | править вики-текст]

Для функций f(n) и g(n) при n \to n_0 используются следующие обозначения:

Обозначение Интуитивное объяснение Определение
f(n) \in O(g(n)) f ограничена сверху функцией g (с точностью до постоянного множителя) асимптотически \exists (C>0), U : \forall (n \in U) \; |f(n)| \leq C|g(n)|
f(n) \in \Omega(g(n)) f ограничена снизу функцией g (с точностью до постоянного множителя) асимптотически \exists (C>0), U : \forall (n \in U) \; C|g(n)| \leq |f(n)|
f(n) \in \Theta(g(n)) f ограничена снизу и сверху функцией g асимптотически \exists (C>0), (C'>0), U : \forall (n \in U) \; C|g(n)| \leq |f(n)| \leq C'|g(n)|
f(n) \in o(g(n)) g доминирует над f асимптотически \forall (C>0) ,\exists U : \forall(n \in U) \; |f(n)| < C|g(n)|
f(n) \in \omega(g(n)) f доминирует над g асимптотически \forall (C>0) ,\exists U : \forall(n \in U) \; C|g(n)| < |f(n)|
f(n) ~\sim~ g(n) f эквивалентна g асимптотически \lim_{n \to n_0} \frac{f(n)}{g(n)} = 1

где U — проколотая окрестность точки n_0.

Основные свойства[править | править вики-текст]

Транзитивность[править | править вики-текст]

  • \begin{matrix}f(n)=\Theta(g(n)) \land g(n)=\Theta(h(n)) & \Rightarrow & f(n) = \Theta (h(n)) \\
f(n)=O(g(n)) \land g(n)=O (h(n)) & \Rightarrow & f(n) = O (h(n)) \\
f(n)=\Omega(g(n)) \land g(n)=\Omega(h(n)) & \Rightarrow & f(n) = \Omega(h(n)) \\
f(n)=o(g(n)) \land g(n)= o (h(n)) & \Rightarrow & f(n) = o (h(n)) \\
f(n)=\omega(g(n)) \land g(n)=\omega(h(n)) & \Rightarrow & f(n) = \omega(h(n))\end{matrix}

Рефлексивность[править | править вики-текст]

  • f(n)=\Theta(f(n))
  • f(n)=O(f(n))
  • f(n)=\Omega(f(n))

Симметричность[править | править вики-текст]

  •  f(n)=\Theta(g(n)) \Leftrightarrow g(n)=\Theta(f(n))

Перестановочная симметрия[править | править вики-текст]

 \begin{matrix}
f(n)= O(g(n)) & \Leftrightarrow & g(n)=\Omega(f(n)) \\
f(n)= o(g(n)) & \Leftrightarrow & g(n)=\omega(f(n)) 
\end{matrix}

Другие[править | править вики-текст]

  •  C \cdot o(f) = o(f)
 C \cdot O(f) = O(f)
  •  o(C \cdot f) = o(f)
 O(C \cdot f) = O(f)
и, как следствия,
 o(-f) = o(f)
 O(-f) = O(f)
  •  o(f) + o(f) = o(f)
 o(f) + O(f) =  O(f) + O(f) = O(f)
  •  O(f) \cdot O(g) = O(fg)
 o(f) \cdot O(g) = o(f) \cdot o(g) = o(fg)
  •  O(O(f)) = O(f)
 o(o(f)) = o(O(f)) = O(o(f)) = o(f)

Асимптотические обозначения в уравнениях[править | править вики-текст]

  • Если в правой части уравнения находится только асимптотическое обозначение (например n = O(n^2)), то знак равенства обозначает принадлежность множеству (n \in O(n^2)).
  • Если в уравнении асимптотические обозначения встречается в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при x → 0 формула e^x-1 = x + o(x) обозначает, что e^x-1 = x + f(x), где f(x) — функция, о которой известно только то, что она принадлежит множеству o(x). Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например,   \sum_{i=0}^nO(n_i^2)   — содержит только одну функцию из класса O(n^2).
  • Если асимптотические обозначения встречаются в левой части уравнения, используют следующее правило:
    какие бы мы функции ни выбрали (в соответствии с предыдущим правилом) взамен асимптотических обозначений в левой части уравнения, можно выбрать функции вместо асимптотических обозначений (в соответствии с предыдущим правилом) в правой части так, что уравнение будет правильным.
    Например, запись x+o(x)=O(x) обозначает, что для любой функции f(x)\in o(x), существует некоторая функция g(x)\in O(x) такая, что выражение x+f(x)=g(x) — верно для всех x.
  • Несколько таких уравнений могут быть объединены в цепочки. Каждое из уравнений в таком случае следует интерпретировать в соответствии с предыдущим правилом.
    Например: 4n^4+4n^2+1=4n^4+\Theta(n^2)=\Theta(n^4). Отметим, что такая интерпретация подразумевает выполнение соотношения 4n^4+4n^2+1=\Theta(n^4).

Приведенная интерпретация подразумевает выполнение соотношения:

\left. \begin{matrix}A = B \\ B = C \end{matrix} \right\} \Rightarrow A = C, где A, B, C — выражения, которые могут содержать асимптотические обозначения.

Примеры использования[править | править вики-текст]

  • e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + ... + \frac{x^n}{n!} + ... = 1 + x + \frac{x^2}{2} + O(x^3) при x \rightarrow 0
  • T(n)=(n+1)^2=O(n^2) при n \rightarrow \infty.
При n \geq 1 выполнено неравенство (n+1)^2<4n^2. Поэтому положим n_0=1, c=4.
Отметим, что нельзя положить n_0=0, так как T(0)=1 и, следовательно, это значение при любой константе c больше c \cdot 0^2=0.
  • Функция T(n)=3n^3+2n^2 при n \rightarrow \infty имеет степень роста O(n^3).
Чтобы это показать, надо положить n_0=0 и c=5. Можно, конечно, сказать, что T(n) имеет порядок O(n^4), но это более слабое утверждение, чем то, что T(n) = O(n^3).
  • Докажем, что функция 3^n при n \rightarrow \infty не может иметь порядок O(2^n).
Предположим, что существуют константы c и n_0 такие, что для всех n \geq n_0 выполняется неравенство 3^n \leq c \cdot 2^n.
Тогда c \geq \left( \frac{3}{2} \right)^n для всех  n \geq n_0 . Но  \left( \frac{3}{2} \right)^n принимает любое, как угодно большое, значение при достаточно большом n, поэтому не существует такой константы c, которая могла бы мажорировать  \left( \frac{3}{2} \right)^n для всех n больших некоторого n_0.
  • T(n)=n^3+2n^2 = \Omega(n^3), n \rightarrow \infty .
Для проверки достаточно положить c=1. Тогда  T(n) \geq cn^3 для n=0, 1, ....

История[править | править вики-текст]

Обозначение «„O“ большое» введено немецким математиком Паулем Бахманом (англ.) во втором томе его книги «Analytische Zahlentheorie» (Аналитическая теория чисел), вышедшем в 1894 году. Обозначение «„о“ малое» впервые использовано другим немецким математиком, Эдмундом Ландау в 1909 году; с работами последнего связана и популяризация обоих обозначений, в связи с чем их также называют символами Ландау. Обозначение пошло от немецкого слова «Ordnung» (порядок).

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. И. А. Шведов. Компактный курс математического анализа. Часть 1. Функции одной переменной. Новосибирск, 2003. С.43.

Литература[править | править вики-текст]

  • Д. Грин, Д. Кнут Математические методы анализа алгоритмов. — Пер. с англ. — М.: Мир, 1987. — 120 с.
  • Дж. Макконелл Основы современных алгоритмов. — Изд. 2 доп. — М.: Техносфера, 2004. — 368 с. — ISBN 5-94836-005-9.
  • Джон Э. Сэвидж Сложность вычислений. — М.: Факториал, 1998. — 368 с. — ISBN 5-88688-039-9.
  • В. Н. Крупский Введение в сложность вычислений. — М.: Факториал Пресс, 2006. — 128 с. — ISBN 5-88688-083-6.
  • Herbert S. Wilf Algorithms and Complexity.
  • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 3. Рост функций // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 87—108. — ISBN 5-8459-0857-4.
  • Бугров, Никольский Высшая математика, том 2.
  • Dionysis Zindros. Введение в анализ сложности алгоритмов (рус.) (2012). Проверено 11 октября 2013.