Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

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

Из Википедии — свободной энциклопедии

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

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

В частности:

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

Определения

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

  • является «O» большим от при , если существует такая константа , что для всех из некоторой окрестности точки имеет место неравенство
    ;
  • является «о» малым от при , если для любого найдется такая проколотая окрестность точки , что для всех имеет место неравенство

Иначе говоря, в первом случае отношение в окрестности точки (то есть ограничено сверху), а во втором оно стремится к нулю при .

Обозначение

Обычно выражение « является большим ( малым) от » записывается с помощью равенства (соответственно, ).

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

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

(или ),

но выражения

(или )

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

Другой пример: при верно, что

но

.

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

,

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

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

или

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

и

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

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

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

Для функций и при используются следующие обозначения:

Обозначение Интуитивное объяснение Определение
ограничена сверху функцией (с точностью до постоянного множителя) асимптотически
ограничена снизу функцией (с точностью до постоянного множителя) асимптотически
ограничена снизу и сверху функцией асимптотически
доминирует над асимптотически
доминирует над асимптотически
эквивалентна асимптотически

где  — проколотая окрестность точки .

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

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

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

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

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

Другие

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

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

  • Если в правой части уравнения находится только асимптотическое обозначение (например ), то знак равенства обозначает принадлежность множеству ().
  • Если в уравнении асимптотические обозначения встречаются в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при x → 0 формула обозначает, что , где  — функция, о которой известно только то, что она принадлежит множеству . Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например,     — содержит только одну функцию из класса .
  • Если асимптотические обозначения встречаются в левой части уравнения, используют следующее правило:
    какие бы мы функции ни выбрали (в соответствии с предыдущим правилом) взамен асимптотических обозначений в левой части уравнения, можно выбрать функции вместо асимптотических обозначений (в соответствии с предыдущим правилом) в правой части так, что уравнение будет правильным.
    Например, запись обозначает, что для любой функции , существует некоторая функция такая, что выражение  — верно для всех .
  • Несколько таких уравнений могут быть объединены в цепочки. Каждое из уравнений в таком случае следует интерпретировать в соответствии с предыдущим правилом.
    Например: . Отметим, что такая интерпретация подразумевает выполнение соотношения .

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

, где A, B, C — выражения, которые могут содержать асимптотические обозначения.

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

  • при .
  • при (следует из формулы Стирлинга)
  • при .
При выполнено неравенство . Поэтому положим .
Отметим, что нельзя положить , так как и, следовательно, это значение при любой константе больше .
  • Функция при имеет степень роста .
Чтобы это показать, надо положить и . Можно, конечно, сказать, что имеет порядок , но это более слабое утверждение, чем то, что .
  • Докажем, что функция при не может иметь порядок .
Предположим, что существуют константы и такие, что для всех выполняется неравенство .
Тогда для всех . Но принимает любое, как угодно большое, значение при достаточно большом , поэтому не существует такой константы , которая могла бы мажорировать для всех больших некоторого .
  • .
Для проверки достаточно положить . Тогда для .

История

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

См. также

Примечания

  1. Шведов И. А. Компактный курс математического анализа. Часть 1. Функции одной переменной. — Новосибирск, 2003. — С. 43.
  2. D.E. Knuth. Big Omicron and big Omega and big Theta (англ.) : Article. — ACM Sigact News, 1976. — Т. 8, № 2. — С. 18—24.

Литература

Эта страница в последний раз была отредактирована 28 сентября 2021 в 23:51.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).