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

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

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

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

В частности:

  • фраза «сложность алгоритма есть O(n!)» означает, что с увеличением параметра n, характеризующего количество входной информации алгоритма, время работы алгоритма растёт не быстрее, чем пропорционально 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“ большим („о“ малым) от 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 → 0 верно, что

O(x²) = o(x),

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

o(x) = O(x²).

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

x² + x³ ∈ O(x²)

или

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

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

x² + x³ = O(x²)

и

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

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

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

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

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

Обозначение Интуитивное объяснение Определение
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 — проколотая окрестность точки n0.

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

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

  • \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}

Другие

  • const × o(f) = o(f); const × O(f) = O(f);
  • o(const × f) = o(f); O(const × 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(fg); o(f) × o(g) = o(fg);
  • O(O(f)) = O(f);
  • o(o(f)), o(O(f)), O(o(f)) = o(f);
  • o(-f) = o(f), O(-f) = O(f) (следствия из п. 2)

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

  • Если в правой части уравнения находится только асимптотическое обозначение (например n = O(n²)), то знак равенства обозначает принадлежность множеству (nO(n²)).
  • Если в уравнении асимптотические обозначения встречается в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при 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 — выражения, которые могут содержать асимптотические обозначения.

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

  • ex = 1 + x + x²/2 + O(x³) при x → 0.
  • n! = O((n/e)n+1/2) при n → ∞.
  • T(n)=(n+1)^2=O(n^2) при n → ∞.
Доказательство:
Если положить n_0=1 и c=4, то для n≥1 будет выполняться неравенство (n+1)^2<4n^2. Отметим, что нельзя положить n_0=0, так как T(0)=1 и, следовательно, это значение при любой константе c больше c0^2=0.
  • Функция T(n)=3n^3+2n^2 при n → ∞ имеет степень роста O(n^3). Чтобы это показать, надо положить n_0=0 и c=5. Можно, конечно, сказать, что T(n) имеет порядок O(n^4), но это более слабое утверждение, чем то, что T(n) имеет порядок роста O(n^3).
  • Докажем, что функция 3^n при n → ∞ не может иметь порядок O(2^n). Предположим, что существуют константы c и n_0 такие, что для всех nn0 выполняется неравенство 3nc2n. Тогда c ≥ (3/2)n для всех nn0. Но (3/2)n принимает любое, как угодно большое, значение при достаточно большом n, поэтому не существует такой константы c, которая могла бы мажорировать (3/2)n для всех n больших некоторого n0.
  • T(n)=n^3+2n^2 есть \Omega(n^3) при n → ∞. Для проверки достаточно положить c=1. Тогда T(n)>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. — С. 230—204. — ISBN 5-8459-0857-4
  • Бугров, Никольский Высшая математика, том 2.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Полезное


Смотреть что такое "«O» большое и «o» малое" в других словарях:

  • Чужое не прочно и большое, а свое и малое, да правое. — Чужое не прочно и большое, а свое и малое, да правое. См. СВОЕ ЧУЖОЕ …   В.И. Даль. Пословицы русского народа

  • Большое кольцо метрополитена — Большое кольцо Московского метрополитена проект второй кольцевой линии Московского метрополитена. Разрабатывался с начала 1970 х годов. По мысли проектировщиков, Большое кольцо должно было значительно разгрузить пассажиропоток на станциях… …   Википедия

  • Малое Загарино (Нижегородская область) — Село Малое Загарино Страна РоссияРоссия Субъект …   Википедия

  • Малое Загарино — Село Малое Загарино Страна РоссияРоссия Субъект федерации …   Википедия

  • Малое кольцо МЖД — Малое кольцо Московской железной дороги (МК МЖД) (Малая окружная железная дорога (МОЖД), Малое московское кольцо (ММК)) окружная железная дорога в Москве, предназначенная для осуществления грузовых транзитных перевозок между всеми 10… …   Википедия

  • Большое Денисьево — У этого топонима есть и другие значения, см. Большое Денисьево. Деревня Большое Денисьево Страна РоссияРоссия …   Википедия

  • Малое Кикерино — Деревня Малое Кикерино Страна РоссияРоссия …   Википедия

  • Малое Московское Кольцо — А107 Московское Малое Кольцо …   Википедия

  • Малое Московское кольцо — А107 Московское Малое Кольцо …   Википедия

  • Малое московское кольцо — А107 Московское Малое Кольцо …   Википедия

  • Большое Кикерино — У этого термина существуют и другие значения, см. Кикерино (значения). Деревня Большое Кикерино Страна РоссияРоссия …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»