Русская Википедия:«O» большое и «o» малое

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

В частности:

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

Определения

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

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

  <math>|f(x)| \leqslant C |g(x)|</math>;

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

  <math>|f(x)| < \varepsilon |g(x)|.</math>

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

Обозначение

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

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

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

<math> f(x) = O(g(x)) </math> (или <math> f(x) = o(g(x)) </math>),

но выражения

<math> O(g(x)) = f(x) </math> (или <math> o(g(x)) = f(x) </math>)

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

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

<math> O(x^2) = o(x) </math>

но

<math> o(x) \ne O(x^2) </math>.

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

<math> o(x) = O(x) </math>,

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

<math> O(x) \ne o(x) .</math>

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

<math> x^3 + x^2 \in O(x^3) </math>

или

<math>\mathop O(x^2)\subset o(x)</math>

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

<math> x^3 + x^2 = O(x^3) </math>

и

<math>\mathop O(x^2) = o(x)</math>

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

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

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

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

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

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

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

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

<math>\begin{matrix}f(n)=\Theta(g(n)) \land g(n)=\Theta(h(n)) & \implies & f(n) = \Theta (h(n)) \\ f(n)=O(g(n)) \land g(n)=O (h(n)) & \implies & f(n) = O (h(n)) \\ f(n)=\Omega(g(n)) \land g(n)=\Omega(h(n)) & \implies & f(n) = \Omega(h(n)) \\ f(n)=o(g(n)) \land g(n)= o (h(n)) & \implies & f(n) = o (h(n)) \\ f(n)=\omega(g(n)) \land g(n)=\omega(h(n)) & \implies & f(n) = \omega(h(n))\end{matrix}</math>

Рефлексивность

<math>f(n)=\Theta(f(n))</math>; <math>f(n)=O(f(n))</math>; <math>f(n)=\Omega(f(n))</math>

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

<math> f(n)=\Theta(g(n)) \Leftrightarrow g(n)=\Theta(f(n)) </math>

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

<math> \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}</math>

Другие

• <math> C \cdot o(f) = o(f) </math>

<math> C \cdot O(f) = O(f) </math>

• <math> o(C \cdot f) = o(f) </math>

<math> O(C \cdot f) = O(f) </math>

и, как следствия,

<math> o(-f) = o(f) </math>

<math> O(-f) = O(f) </math>

• <math> o(f) + o(f) = o(f) </math>

<math> o(f) + O(f) = O(f) + O(f) = O(f) </math>

• <math> O(f) \cdot O(g) = O(fg) </math>

<math> o(f) \cdot O(g) = o(f) \cdot o(g) = o(fg) </math>

• <math> O(O(f)) = O(f) </math>

<math> o(o(f)) = o(O(f)) = O(o(f)) = o(f) </math>

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

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

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

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

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

• <math>e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \ldots + \frac{x^n}{n!} + \ldots = 1 + x + \frac{x^2}{2} + O(x^3) </math> при <math>x \rightarrow 0</math>.

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

• <math>T(n)=(n+1)^2=O(n^2)</math> при <math>n \rightarrow \infty</math>.

При <math>n > 1</math> выполнено неравенство <math>(n+1)^2<4n^2</math>. Поэтому положим <math>n_0=1, c=4</math>.

Отметим, что нельзя положить <math>n_0=0</math>, так как <math>T(0)=1</math> и, следовательно, это значение при любой константе <math>c</math> больше <math>c \cdot 0^2=0</math>.

• Функция <math>T(n)=3n^3+2n^2</math> при <math>n \rightarrow \infty</math> имеет степень роста <math>O(n^3)</math>.

Чтобы это показать, надо положить <math>n_0=0</math> и <math>c=5</math>. Можно, конечно, сказать, что <math>T(n)</math> имеет порядок <math>O(n^4)</math>, но это более слабое утверждение, чем то, что <math>T(n) = O(n^3)</math>.

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

Предположим, что существуют константы <math>c</math> и <math>n_0</math> такие, что для всех <math>n \geq n_0</math> выполняется неравенство <math>3^n \leq c \cdot 2^n</math>.

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

• <math>T(n)=n^3+2n^2 = \Omega(n^3), n \rightarrow \infty </math>.

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

История

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

См. также

• Бесконечно малая и бесконечно большая

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Книга:CLRS
• Шаблон:Книга
• Шаблон:Cite web