Вивчення поняття "символ О"

курсовая работа

1.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) = .

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