Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

«O» большое и «o» малоематематические обозначения для сравнения асимптотического поведения функций. Используются в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также при оценке сложности алгоритмов. В частности, фраза «сложность алгоритма есть O(n!)» означает, что при больших n время работы алгоритма (или общее количество операций) не более чем C · n!, где C — некая положительная константа (обычно в качестве параметра 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 году; с работами последнего связана и популяризация обоих обозначений, в связи с чем их также называют символами Ландау.pl:Notacja dużego Osr:Велико О sv:Ordo th:สัญกรณ์โอใหญ่uk:Нотація Ландау

Викия-сеть

Случайная вики