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

Содержание

• Введение
• Для любой функции f(n) верно неравенство . , где С = 1. По определению символа О (1.1.2) это и означает, что f(n) = O(f(n)). Соотношение 3 доказано.
• Таблица №1
• Утверждение ложно.
• Пусть f(n) = n2, а g(n) = 1. Найдем такую функцию (n), которая бы принадлежала левому множеству, но не принадлежала бы правому множеству, т.е. (С1) (n) [(n) C1(n2 + 1)] и (С2) (nn0) [(n) > n2 + C2].
• Возьмем (n) = 2n2.
• 1). Пусть С1 = 3, тогда (nn0) 2n2 3(n2 + 1). Значит функция (n) принадлежит левому множеству.
• 2). (С2) (n> ) 2n2 > n2 + C2. Значит функция (n) не принадлежит правому множеству.