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

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

Таблица 1.

Где U — проколотая окрестность точки n₀.

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

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

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

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

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

Другие:

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

• · Если в правой части уравнения находится только асимптотическое обозначение (наприме рn=O (nІ)), то знак равенства обозначает принадлежность множеству (nЃёO (nІ)).
• · Если в уравнении асимптотические обозначения встречается в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при x> 0 формула обозначает, что, где — функция, о которой известно только то, что она принадлежит множеству. Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например, — содержит только одну функцию из класса .

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

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

.

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

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

• · при
• · при (следует из формулы Стирлинга)

· при .

При выполнено неравенство. Поэтому положим .

Отметим, что нельзя положить, так как и, следовательно, это значение при любой константебольше.

· Функция при имеет степень роста .

Чтобы это показать, надо положить и. Можно, конечно, сказать, что имеет порядок, но это более слабое утверждение, чем-то, что .

· Докажем, что функция при не может иметь порядок .

Предположим, что существуют константыитакие, что для всех выполняется неравенство .

Тогда для всех. Но принимает любое, как угодно большое, значение при достаточно большом, поэтому не существует такой константы, которая могла бы мажорировать для всех больших некоторого .

.

Для проверки достаточно положить. Тогда для .