Символ "О" - асимптотический анализ
§3. Решение задач
Задача 1. Что неверно в следующих рассуждениях? Поскольку n = O(n) и 2n = O(n) и так далее, то заключаем, что ?
Решение:
Замена kn на O(n) подразумевает различные С для различных k; а нужно, чтобы все О имели общую константу. В действительности, в данном случае требуется, чтобы О обозначало множество функций двух переменных, k и n. Правильно будет записать .
Задача 2. Докажите или опровергните: О(f(n) + g(n)) = f(n) + O(g(n)), если f(n) и g(n) положительны для всех nN.
Решение:
Утверждение ложно.
Пусть 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) не принадлежит правому множеству.
Задача 3. Докажите или опровергните: cos O(x) = 1 + O(x2) для всех вещественных х.
Решение:
Если функция g(x) принадлежит левой части так, что g(x) = cos y для некоторого y, причем для некоторой константы С, то
g(x) = cos y = 1 - 2sin2 (y/2) 1 = 1 + 0 х2. Значит существует такая константа В, что g(x) 1 + В х2. Следовательно, множество из левой части содержится в правой части, и формула верна.
Задача 4. Докажите, что .
Решение:
Преобразуем левую часть следующим образом:
.
Заметим, что , тогда , где С - константа, тогда можно записать по определению символа О, что . Используя это для преобразованного равенства, получаем, что
= (по 1.2.4)
Что и требовалось доказать.
Задача 5. Вычислите при nN.
Решение:
(по 1.2.6)
(по 1.2.3)
(по 1.2.4)
(по 1.2.2)
Задача 6. Вычислите (n + 2 + O(n-1))n с относительной погрешностью
O(n-1), при n.
Решение:
(по 1.2.3 и 1.2.4)
При n k = (2n-1 + O(n-2)) 0, тогда ln (1 + k) 0. Тогда при n
ln (1 + k) = k.
(по 1.2.9)
.
Задача 7. Докажите, что , при nN, n.
Решение:
Покажем, что . (*)
По определению - функция аn такая, что . Получаем, что , значит .
Теперь докажем, что :
= (по 1.2.4 и 1.2.6) = = (по (*))
= (по 1.2.6) = (по 1.2.9)
= (по 1.2.6) =.