Курсовая работа: Вивчення поняття "символ О"

де 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), і існують константи 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)

Доказ:

Покажемо, що ліва частина є підмножиною правої частини.

Функція з лівої частини має вигляд a(n) такий, що існують позитивні константи З, В, n₀ , m₀ такі, що