WikiSort.ru - Не сортированное

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

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

В частности:

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

Определения

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

• ${\displaystyle f}$ является «O» большим от ${\displaystyle g}$ при ${\displaystyle x\to x_{0}}$ , если существует такая константа ${\displaystyle C>0}$ , что для всех ${\displaystyle x}$ из некоторой окрестности точки ${\displaystyle x_{0}}$ имеет место неравенство

  ${\displaystyle |f(x)|\leqslant C|g(x)|}$ ;

• ${\displaystyle f}$ является «о» малым от ${\displaystyle g}$ при ${\displaystyle x\to x_{0}}$ , если для любого ${\displaystyle \varepsilon >0}$ найдется такая проколотая окрестность ${\displaystyle U_{x_{0}}'}$ точки ${\displaystyle x_{0}}$ , что для всех ${\displaystyle x\in U_{x_{0}}'}$ имеет место неравенство

  ${\displaystyle |f(x)|<\varepsilon |g(x)|.}$

Иначе говоря, в первом случае отношение ${\displaystyle {\frac {|f|}{|g|}}\leqslant C}$ в окрестности точки ${\displaystyle x_{0}}$ (то есть ограничено сверху), а во втором оно стремится к нулю при ${\displaystyle x\to x_{0}}$ .

Обозначение

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

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

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

${\displaystyle f(x)=O(g(x))}$ (или ${\displaystyle f(x)=o(g(x))}$ ),

но выражения

${\displaystyle O(g(x))=f(x)}$ (или ${\displaystyle o(g(x))=f(x)}$ )

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

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

${\displaystyle O(x^{2})=o(x)}$

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

${\displaystyle o(x)=O(x^{2})}$ .

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

${\displaystyle o(x)=O(x)}$ ,

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

${\displaystyle O(x)=o(x)}$ .

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

${\displaystyle x^{3}+x^{2}\in O(x^{3})}$

или

${\displaystyle \mathop {O} (x^{2})\subset o(x)}$

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

${\displaystyle x^{3}+x^{2}=O(x^{3})}$

и

${\displaystyle \mathop {O} (x^{2})=o(x)}$

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

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

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

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

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

где ${\displaystyle U}$  — проколотая окрестность точки ${\displaystyle n_{0}}$ .

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

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

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

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

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

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

• ${\displaystyle 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})}$ при ${\displaystyle x\rightarrow 0}$

• ${\displaystyle n!=O\left(\left({\frac {n}{e}}\right)^{n+{\frac {1}{2}}}\right)}$ при ${\displaystyle n\rightarrow \infty }$ (следует из формулы Стирлинга)

• ${\displaystyle T(n)=(n+1)^{2}=O(n^{2})}$ при ${\displaystyle n\rightarrow \infty }$ .

При ${\displaystyle n\geq 1}$ выполнено неравенство ${\displaystyle (n+1)^{2}<4n^{2}}$ . Поэтому положим ${\displaystyle n_{0}=1,c=4}$ .

Отметим, что нельзя положить ${\displaystyle n_{0}=0}$ , так как ${\displaystyle T(0)=1}$ и, следовательно, это значение при любой константе ${\displaystyle c}$ больше ${\displaystyle c\cdot 0^{2}=0}$ .

• Функция ${\displaystyle T(n)=3n^{3}+2n^{2}}$ при ${\displaystyle n\rightarrow \infty }$ имеет степень роста ${\displaystyle O(n^{3})}$ .

Чтобы это показать, надо положить ${\displaystyle n_{0}=0}$ и ${\displaystyle c=5}$ . Можно, конечно, сказать, что ${\displaystyle T(n)}$ имеет порядок ${\displaystyle O(n^{4})}$ , но это более слабое утверждение, чем то, что ${\displaystyle T(n)=O(n^{3})}$ .

• Докажем, что функция ${\displaystyle 3^{n}}$ при ${\displaystyle n\rightarrow \infty }$ не может иметь порядок ${\displaystyle O(2^{n})}$ .

Предположим, что существуют константы ${\displaystyle c}$ и ${\displaystyle n_{0}}$ такие, что для всех ${\displaystyle n\geq n_{0}}$ выполняется неравенство ${\displaystyle 3^{n}\leq c\cdot 2^{n}}$ .

Тогда ${\displaystyle c\geq \left({\frac {3}{2}}\right)^{n}}$ для всех ${\displaystyle n\geq n_{0}}$ . Но ${\displaystyle \left({\frac {3}{2}}\right)^{n}}$ принимает любое, как угодно большое, значение при достаточно большом ${\displaystyle n}$ , поэтому не существует такой константы ${\displaystyle c}$ , которая могла бы мажорировать ${\displaystyle \left({\frac {3}{2}}\right)^{n}}$ для всех ${\displaystyle n}$ больших некоторого ${\displaystyle n_{0}}$ .

• ${\displaystyle T(n)=n^{3}+2n^{2}=\Omega (n^{3}),n\rightarrow \infty }$ .

Для проверки достаточно положить ${\displaystyle c=1}$ . Тогда ${\displaystyle T(n)\geq cn^{3}}$ для ${\displaystyle n=0,1,...}$ .

История

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

См. также

• Бесконечно малая величина

Примечания

Литература

• Д. Грин, Д. Кнут. Математические методы анализа алгоритмов. — Пер. с англ. — М.: Мир, 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.