Дипломная работа: Символ "О" - асимптотический анализ

Определение 3: запись f (х ) = O (g (х )) при х ®0 означает, что существуют две константы С и e , такие, что

, если только . (1.1.4)

Теперь О представляет неопределенную функцию и одну или две неопределенные константы, зависящие от контекста.

Замечание 2 : запись корректна, но в этом равенстве нельзя менять местами правую и левую части. В противном случае мы можем прийти к нелепым выводам, наподобие n = n ² , исходя из верных тождеств n = О (n ² ) и n ² = О (n ² ).

Работая с символом «О » мы имеем дело с односторонними равенствами. Правая часть уравнения содержит не больше информации, чем левая, и фактически может содержать меньше информации; правая часть является «огрублением» левой.

Если говорить строго формально, то запись O (g (n )) обозначает не какую-то одну функцию f (n ), а сразу множество функций f (n ), таких, что для некоторой константы С . Обычная формула g (n ), не включающая символ О , обозначает множество, содержащее одну функцию f (n ) = g (n ). Если S и T суть множества функций от n , то запись S + T обозначает множество всех функций вида f (n ) + g (n ), где f (n )ÎS и g (n )ÎT ; другие обозначения вроде S – T , ST , S / T , , е ^S , ln S определяются аналогично. Тогда «равенство» между двумя такими множествами функций есть теоретико-множественное включение; знак «=» в действительности означает «Í».

Пример 3: «Уравнение» означает, что S ₁ Í S ₂ , где S ₁ есть множество всех функций вида , для которых найдется константа С ₁ , такая, что , а S ₂ есть множество всех функций , для которых найдется константа С ₂ , такая, что .

Можно строго доказать это «равенство», если взять произвольный элемент из левой части и показать, что он принадлежит правой части: пусть таково, что , следует доказать, что существует такая константа С ₂ , что . Константа решает проблему, так как для всех целых n .

Замечание 3: Если в формуле используется несколько переменных, то символ О представляет множество функций от двух или более переменных, а не только от одной. В область определения каждой функции входят все переменные, которые в данном контексте «свободны» для изменения.

Тут есть некоторая тонкость ввиду того, что переменные могут иметь смысл лишь в части выражения, если они связаны знаком S или подобным.

Пример 4: , целое n ³ 0. (1.1.5)

Выражение k ² + O (k ) в левой части отвечает множеству всех функций от двух переменных вида k ² + f (k , n ), для которых найдется константа С , такая, что для 0 £ k £ n . Сумма таких множеств функций для 0 £ k £ n есть множество всех функций g (n ) вида

,

где f удовлетворяет сформулированному условию. Поскольку

то все такие функции g (n ) принадлежат правой части (1.1.5); следовательно, (1.1.5) справедливо.

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

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

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

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

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

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

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

Любая функция из левой части имеет вид a ( n ) + b ( n ) , и существуют константы m ₀ , B , n ₀ , 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 ), такие, что существуют константы В , С , n ₀ , m ₀ , что

и

.

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

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

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

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