большое и малое

«O» большое и «o» малое (OO и oo) — математические обозначения для сравнения асимптотического поведения (асимптотики) функций. Используются в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также в информатике и теории алгоритмов. Под асимптотикой понимается характер изменения функции при её стремлении к определённой точке. o(f)o(f), «о малое от ff» обозначает «бесконечно малое относительно ff», пренебрежимо малую величину при рассмотрении ff. Смысл термина «О большое» зависит от его области применения, но всегда O(f)O(f) растёт не быстрее, чем ff (точные определения приведены ниже). В частности:

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

Определения

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

  • ff является «O» большим от gg при xx0xx0, если существует такая константа C>0C>0, что для всех xx из некоторой окрестности точки x0x0 имеет место неравенство |f(x)|C|g(x)||f(x)|C|g(x)|;
  • ff является «о» малым от gg при xx0xx0, если для любого ε>0ε>0 найдется такая проколотая окрестность Ux0Ux0 точки x0x0, что для всех xUx0xUx0 имеет место неравенство |f(x)|<ε|g(x)|.|f(x)|<ε|g(x)|.
Иначе говоря, в первом случае отношение $\frac{| == Обозначение == Обычно выражение «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верно.Прилюбомxверноo(x) = O(x),т.е.бесконечномалаявеличинаявляетсяограниченной,ноневерно,чтоограниченнаявеличинаявляетсябесконечномалой:,т.е.бесконечномалаявеличинаявляетсяограниченной,ноневерно,чтоограниченнаявеличинаявляетсябесконечномалой:O(x) = o(x).Вместознакаравенстваметодологическиправильнеебылобыупотреблятьзнакипринадлежностиивключения,понимая.Вместознакаравенстваметодологическиправильнеебылобыупотреблятьзнакипринадлежностиивключения,понимаяO({\,})ииo({\,})какобозначениядлямножествфункций,тоесть,используязаписьвформекакобозначениядлямножествфункций,тоесть,используязаписьвформеx^3 + x^2 \in O(x^3)илиили\mathop O(x^2)\subset o(x)вместо,соответственно,вместо,соответственно,x^3 + x^2 = O(x^3)ии\mathop O(x^2) = o(x)$ Однако на практике такая запись встречается крайне редко, в основном, в простейших случаях. При использовании данных обозначений должно быть явно оговорено (или очевидно из контекста), о каких окрестностях (одно- или двусторонних; содержащих целые, вещественные или комплексные числа и т. п.) и о каких допустимых множествах функций идет речь (поскольку такие же обозначения употребляются и применительно к функциям многих переменных, к функциям комплексной переменной, к матрицам и др.).

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

Для функций f(n)f(n) и g(n)g(n) при nn0nn0 используются следующие обозначения:
где UU — проколотая окрестность точки n0n0.

Основные свойства

Транзитивность


  • \{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)=Θ(f(n))f(n)=Θ(f(n))
  • f(n)=O(f(n))f(n)=O(f(n))
  • f(n)=Ω(f(n))f(n)=Ω(f(n))

Симметричность


  • f(n)=Θ(g(n))g(n)=Θ(f(n))f(n)=Θ(g(n))g(n)=Θ(f(n))

Перестановочная симметрия

f(n)=O(g(n))g(n)=Ω(f(n))f(n)=o(g(n))g(n)=ω(f(n))f(n)=O(g(n))f(n)=o(g(n))g(n)=Ω(f(n))g(n)=ω(f(n))

Другие


  • Co(f)=o(f)
CO(f)=O(f)

  • o(Cf)=o(f)
O(Cf)=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)O(g)=O(fg)
o(f)O(g)=o(f)o(g)=o(fg)

  • O(O(f))=O(f)
o(o(f))=o(O(f))=O(o(f))=o(f)

Асимптотические обозначения в уравнениях


  • Если в правой части уравнения находится только асимптотическое обозначение (например n=O(n2)), то знак равенства обозначает принадлежность множеству (nO(n2)).
  • Если в уравнении асимптотические обозначения встречается в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при x → 0 формула ex1=x+o(x) обозначает, что ex1=x+f(x), где f(x) — функция, о которой известно только то, что она принадлежит множеству o(x). Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например,   ni=0O(n2i)   — содержит только одну функцию из класса O(n2).
  • Если асимптотические обозначения встречаются в левой части уравнения, используют следующее правило:\\ какие бы мы функции ни выбрали (в соответствии с предыдущим правилом) взамен асимптотических обозначений в левой части уравнения, можно выбрать функции вместо асимптотических обозначений (в соответствии с предыдущим правилом) в правой части так, что уравнение будет правильным.\\ Например, запись x+o(x)=O(x) обозначает, что для любой функции f(x)o(x), существует некоторая функция g(x)O(x) такая, что выражение x+f(x)=g(x) — верно для всех x.
  • Несколько таких уравнений могут быть объединены в цепочки. Каждое из уравнений в таком случае следует интерпретировать в соответствии с предыдущим правилом.\\ Например: 4n4+4n2+1=4n4+Θ(n2)=Θ(n4). Отметим, что такая интерпретация подразумевает выполнение соотношения 4n4+4n2+1=Θ(n4).
Приведенная интерпретация подразумевает выполнение соотношения: A=BB=C}A=C, где A, B, C — выражения, которые могут содержать асимптотические обозначения.

Примеры использования


  • ex=1+x+x22!+x33!+...+xnn!+...=1+x+x22+O(x3) при x0

  • n!=O((ne)n+12) при n (следует из формулы Стирлинга)

  • T(n)=(n+1)2=O(n2) при n.
При n1 выполнено неравенство (n+1)2<4n2. Поэтому положим n0=1,c=4. Отметим, что нельзя положить n0=0, так как T(0)=1 и, следовательно, это значение при любой константе c больше c02=0.

  • Функция T(n)=3n3+2n2 при n имеет степень роста O(n3).
Чтобы это показать, надо положить n0=0 и c=5. Можно, конечно, сказать, что T(n) имеет порядок O(n4), но это более слабое утверждение, чем то, что T(n)=O(n3).

  • Докажем, что функция 3n при n не может иметь порядок O(2n).
Предположим, что существуют константы c и n0 такие, что для всех nn0 выполняется неравенство 3nc2n. Тогда c(32)n для всех nn0. Но (32)n принимает любое, как угодно большое, значение при достаточно большом n, поэтому не существует такой константы c, которая могла бы мажорировать (32)n для всех n больших некоторого n0.

  • T(n)=n3+2n2=Ω(n3),n.
Для проверки достаточно положить c=1. Тогда T(n)cn3 для n=0,1,....

История

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