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

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

Содержание

Определения

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

  • f является «O» большим от g при xx0, если существует такая положительная константа C, что для всех x из некоторой окрестности точки x0 имеет место неравенство
|f(x)| < C |g(x)|;
  • f является «о» малым от g при xx0, если для любой положительной константы c найдется такая окрестность точки x0, что для всех x из этой окрестности имеет место неравенство
|f(x)| < c |g(x)|.

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

Обозначение

Обычно выражение

«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(x2) = o(x),

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

o(x) = O(x2).

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

x2 + x3O(x2)

или

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

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

x2 + x3 = O(x2)

и

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

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

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

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

  • o(f) = 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(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).

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

  • ex = 1 + x + x2/2 + O(x3) при x → 0;
  • n! = O((n/e)n+1/2) при n \to \infty.

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

Реже используются обозначения:

  • f = Ω(g) при xx0, если отношение |f(x)/g(x)| ограничено снизу положительной константой в некоторой окрестности точки x0;
  • f = Θ(g) при xx0, если отношение |f(x)/g(x)| ограничено положительными константами и сверху, и снизу, т. е. если одновременно f = O(g) и g = O(f).

История

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

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home