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

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

Другие

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

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

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

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

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

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

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

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

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

·

· f(n) = Θ(f(n))

· f(n) = O(f(n))

· f(n) = Ω(f(n))

·

 

· 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);

· O(-f) = O(f)

· Если в правой части уравнения находится только асимптотическое обозначение (например n = O(n²)), то знак равенства обозначает принадлежность множеству (n ∈ O(n²)).

· Если в уравнении асимптотические обозначения встречается в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при x → 0 формула e^x − 1 = x + o(x) обозначает, что e^x − 1 = x + f(x), где f(x) — функция, о которой известно только то, что она принадлежит множеству o(x). Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например, — содержит только одну функцию из класса O(n²).

· Если асимптотические обозначения встречаются в левой части уравнения, используют следующее правило:
какие бы мы функции не выбрали (в соответствии с предыдущим правилом) взамен асимптотических обозначений в левой части уравнения, можно выбрать функции вместо асимптотических обозначений (в соответствии с предыдущим правилом) в правой части так, что уравнение будет правильным.
Например, запись x + o(x) = O(x) обозначает, что для любой функции f(x) ∈ o(x), существует некоторая функция g(x), такая что выражение x + f(x) = g(x) — верно для всех x.

· Несколько таких уравнений могут быть объединены в цепочки. Каждое из уравнений в таком случае следует интерпретировать в соответствии с предыдущим правилом.
Например: 4n⁴ + 4n² + 1 = 4n⁴ + Θ(n²) = Θ(n⁴). Отметим, что такая интерпретация подразумевает выполнение соотношения 4n⁴ + 4n² + 1 = Θ(n⁴).

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

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

· e^x = 1 + x + x²/2 + O(x³) при x → 0.

· n! = O((n/e)^n+1/2) при n → ∞.

· T(n) = (n + 1)² = O(n²) при n → ∞.

Доказательство:

Если положить n₀ = 1 и c = 4, то для n≥1 будет выполняться неравенство (n + 1)² < 4n². Отметим, что нельзя положить n₀ = 0, так как T(0) = 1 и, следовательно, это значение при любой константе c больше c0² = 0.

· Функция T(n) = 3n³ + 2n² при n → ∞ имеет степень роста O(n³). Чтобы это показать, надо положить n₀ = 0 и c = 5. Можно, конечно, сказать, что T(n) имеет порядок O(n⁴), но это более слабое утверждение, чем то, что T(n) имеет порядок роста O(n³).

· Докажем, что функция 3ⁿ при n → ∞ не может иметь порядок O(2ⁿ). Предположим, что существуют константы c и n₀ такие, что для всех n ≥ n₀ выполняется неравенство 3ⁿ ≤ c2ⁿ. Тогда c ≥ (3/2)ⁿ для всех n ≥ n₀. Но (3/2)ⁿ принимает любое, как угодно большое, значение при достаточно большом n, поэтому не существует такой константы c, которая могла бы мажорировать (3/2)ⁿ для всех n больших некоторого n₀.

· T(n) = n³ + 2n² есть Ω(n³) при n → ∞. Для проверки достаточно положить c = 1. Тогда T(n) > cn³ для n = 0,1,....