§1.2. Асимптотичні позначення швидкості росту функції

2.1. -позначення

Визначення 1. Будемо казати, що функція , якщо існують константи і число такі, що

(1).

Ілюстрація визначення 1 наведена на малюнку1.

Рис. 1. Малюнок до означення

Зауваження. Знак рівності в позначці означає тільки, що для великих виконується співвідношення (1). Отже, заключати, що коли , , то − не вірно.

Якщо , то кажуть, що є асимптотично точною оцінкою для . Зауважимо, що це відношення симетрично: виконується також і .

Приклад 1. Перевіримо, що .

Згідно визначення 1 потрібно знайти та , для яких

(2)

справедливо . Для цього поділимо (2) на : .

Для виконання правої нерівності достатньо покласти . Ліва нерівність виконується, якщо ; .

Приклад 2. Покажемо, що .

Дійсно, якщо існує та такі що ,

то це означає , що з ростом очевидно не виконується.

Приклад 3. − константи.

Можна показати , причому ; ; .

Приклад 4. де , тоді .

Частковим випадком позначення є , що означає обмежену функцію, що відділена від нуля деякою додатною константою при додатньо великих значеннях аргументу, причому звичайно зрозуміло, що є аргументом функції.

2.2. −Позначення

Позначення включає дві оцінки: верхню і нижню. Їх можна розділити.

Визначення 2. Будемо казати, що , якщо існує константа та число , такі що (3)

Ілюстрація означення 2 наведена на малюнку 2.

Рис. 2. Малюнок до означення

Приклад 5. Оскільки при , то

2.3. −Позначення

Визначення 3. Будемо казати, що , якщо існує константа та число такі, що (4)

Ілюстрація означення 3 наведена на малюнку 3.

Рис. 3. Малюнок до означення

Можна показати, що виконується таке твердження.

Теорема (про співвідношення -, -, та -позначень)

Для будь-яких двох функцій та властивість виконується тоді і тільки тоді, коли

та .

Для будь-яких двох функцій та властивості та рівносильні.

Приклад 6. При , якщо покласти у визначенні 3 та . Зазначимо, що ; .

2.4. -позначення

Наявність властивості означає, що при відношення залишається обмеженим.

Розглянемо випадок, коли до того ж залишається обмеженим.

Означення 4. Будемо казати, що , якщо , таке, що (5)

Приклад 7. ; .

2.5. -позначення

Виконання умови означає, що при відношення залишається обмеженням. Розглянемо випадок, коли крім цього .

Визначення 5. Будемо казати, що , якщо , таке, що (6)

Приклад 8. ; .

2.6. Властивості асимптотичних відношень

Введені асимптотичні відношення мають певні транзитивні рефлексивні та симетричні властивості та оберненість (див. вправи 1, 5 − 7).

Теорема (про транзитивність асимптотичних відношень)

Відношення як бінарні відношення є транзитивними, тобто: − якщо та , то ;

− якщо та , то ;

− якщо та , то ;

− якщо та , то ;

− якщо та , то .

Теорема (про рефлексивність асимптотичних відношень)

Відношення як бінарні відношення рефлексивні, тобто , , .