Символ "О" - асимптотический анализ

дипломная работа

§2. Основные соотношения

Соотношение 1: если . (1.2.1)

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

Пусть , тогда по свойству степени и модуля. , где С = 1. А по определению (1.1.2) символа О это и означает, что при . Соотношение 1 доказано.

Соотношение 2: . (1.2.2)

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

Покажем строго в соответствии с теоретико-множественным определением символа О, что левая часть является подмножеством правой части.

Любая функция из левой части имеет вид a(n) + b(n), и существуют константы m0, B, n0, C, такие, что

и .

Следовательно, функция в левой части

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

Соотношение 3: f(n) = O(f(n)); (1.2.3)

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

Для любой функции f(n) верно неравенство . , где С = 1. По определению символа О (1.1.2) это и означает, что f(n) = O(f(n)). Соотношение 3 доказано.

Соотношение 4: O(f(n))O(g(n)) = O(f(n)g(n)); (1.2.4)

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

Покажем в соответствии с теоретико-множественным определением символа О, что левая часть является подмножеством правой части.

В левой части функции имеют вид a(n)  b(n), такие, что существуют константы В, С, n0, m0, что

и

.

Тогда для любого n  max(n0, m0,). Значит левая часть принадлежит правой части, а, следовательно, является подмножеством правой части по определению символа О. Соотношение 6 доказано.

Соотношение 5: O(O(f(n))) = O(f(n)); (1.2.5)

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

Покажем, что левая часть является подмножеством правой части.

Функция из левой части имеет вид a(n) такой, что существуют положительные константы С, В, n0, m0 такие, что

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

Соотношение 6: С  O(f(n)) = O(f(n)), если С - константа; (1.2.6)

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

Существует такая константа В, что , по определению (1.1.1) С = О(1). Тогда С  O(f(n)) = О(1)  O(f(n)) = (по 1.2.4) = O(f(n)).

Соотношение доказано.

Соотношение 7: O(f(n)g(n)) = f(n)O(g(n)). (1.2.7)

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

Покажем, что левая часть является подмножеством правой части.

В левой части функции имеют вид a(n), такие, что существуют константы С, n0, что

.

По определению символа О мы получаем верное равенство (1.2.7). Соотношение 7 доказано.

Соотношение 8: O(f(n)2) =  O(f(n))2. (1.2.8)

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

O(f(n)2) = O(f(n) · f(n)) = (по 1.2.7) = f(n) · O(f(n)) = (по 1.2.3) = О(f(n)) · O(f(n)) = O(f(n))2

Соотношение доказано.

Соотношение 9: еO(f(n)) =  1 + O(f(n)), если f(n) = О(1) (1.2.9)

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

еO(f(n)) = еg(n), где . Т.к. f(n) = О(1), т.е. , то.

. Значит еO(f(n)) =  1 + O(f(n)).

Соотношение доказано.

Соотношение 10: Если сумма сходится абсолютно для некоторого комплексного числа z = z0, то

.

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

Данное соотношение очевидно, поскольку

.

Соотношение доказано.

Замечание 4: В частности, S(z) = O(1) при z  0 и S(1/n) = O(1) при n   при том только условии, что S(z) сходится хотя бы для одного ненулевого значения z. Мы можем использовать этот принцип для того, чтобы, отбросив хвост степенного ряда, начиная с любого удобного места, оценить этот хвост через О. Так, например, не только S(z) = O(1), но и

S(z) = a0 + O(z), S(z) = a0 + a1z + O(z2),

и т.д., поскольку

,

а последняя сумма, как и сама S(z), абсолютно сходится при z = z0 и есть О(1).

В таблице №1 приведены самые полезные асимптотические формулы [2], половина из которых получена просто путем отбрасывания членов степенного ряда в соответствии с этим правилом.

"right">Таблица №1

Асимптотические аппроксимации, справедливые при n   и z  0

(1.2.10)

(1.2.11)

(1.2.12)

(1.2.13)

(1.2.14)

(1.2.15)

Асимптотические формулы для Hn, n! не являются начальными отрезками сходящихся рядов; если неограниченно продолжить эти формулы, то полученные ряды будут расходиться при всех n.

Говорят, что асимптотическая аппроксимация имеет абсолютную погрешность O(g(n)), если она имеет вид f(n) + O(g(n)), где f(n) не включает О. Аппроксимация вида f(n)(1 + O(g(n))) имеет относительную погрешность O(g(n)), если f(n) не включает О. Например, аппроксимация Hn в таблице №1 имеет абсолютную погрешность O(n-6); аппроксимация n! - относительную погрешность O(n-4). (Правая часть (1.2.11) не такая, как требуется, - f(n)(1 + O(n-4)), но ее можно переписать как

.

Абсолютная погрешность этой аппроксимации есть O(nn-3.5e-n). Абсолютная погрешность соотносится с числом верных десятичных цифр справа от десятичной точки, которые сохраняются после отбрасывания члена О; относительная погрешность связана с числом верных «значащих цифр».

Делись добром ;)