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

14 15 16 17 18 19 20

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

Другие

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

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

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

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

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

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

Для функций 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.

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

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

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

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

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

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

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

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

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

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