Вивчення поняття "символ О" (стр. 2 из 4)
,де f задовольняє сформульованій умові. Оскільки
те всі такі функції g(n) належать правій частині (1.1.5); отже, (1.1.5) справедливо.
1.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: е(f(n)) = 1 + O(f(n)), якщо f(n) = О(1)(1.2.9)
Доказ:
е(f(n)) = еg(n), де
.Так як. f(n) = О(1), тобто
, те 
. 
. Значить е(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], половина з яких отримана шляхом відкидання членів статечного ряду відповідно до цього правила.
Таблиця №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). Абсолютна погрішність співвідноситься із числом вірних десяткових цифр праворуч від десяткової крапки, які зберігаються після відкидання члена О; відносна погрішність пов'язана із числом вірних "значущих цифр".
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) позитивні для всіх nÎN.
Рішення:
Твердження невірне.
Нехай f(n) = n2, а g(n) = 1. Знайдемо таку функцію j(n), яка б належала лівій множині, але не належала б правій множині, тобто ($З1) ("n) [j(n) £ C1(n2 + 1)] і ("З2) ($n³n0) [j(n) > n2 + C2].
Візьмемо j(n) = 2n2.
1). Нехай З1 = 3, тоді ("n³n0) 2n2£ 3(n2 + 1). Значить функція j(n) належить лівій множині.
2). ("З2) ($n>
) 2n2 > n2 + C2. Значить функція j(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. Доведіть, що
.Рішення:
Перетворимо ліву частину в такий спосіб:
.Помітимо, що
, тоді 
, де З – константа, тоді можна записати по визначенню символу О, що 
. Використовуючи це для перетвореної рівності, одержуємо, що