Нотація Big O: основні концепції

2.1 Визначення нотації Big O.

Нотація Big O — це математична нотація, яка використовується для опису верхньої межі часу виконання або споживання ресурсів алгоритмом в залежності від розміру вхідних даних. Вона допомагає визначити, як добре алгоритм масштабується і як його продуктивність змінюється при збільшенні обсягу даних.

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

Основні нотації:

O(1) — Константна складність:

• Час виконання алгоритму не залежить від розміру вхідних даних.
• Приклад: доступ до елемента масиву за індексом.

O(n) — Лінійна складність:

• Час виконання алгоритму лінійно залежить від розміру вхідних даних.
• Приклад: простий перебір всіх елементів масиву.

O(log n) — Логарифмічна складність:

• Час виконання алгоритму зростає логарифмічно з збільшенням розміру вхідних даних.
• Приклад: бінарний пошук в відсортованому масиві.

O(n^2) — Квадратична складність:

• Час виконання алгоритму квадратично залежить від розміру вхідних даних.
• Приклад: сортування бульбашкою, сортування вставками.

O(2^n) — Експоненційна складність:

• Час виконання алгоритму експоненційно залежить від розміру вхідних даних.
• Приклад: розв'язання задачі про рюкзак повним перебором.

2.2 Інтерпретація нотації Big O.

Як інтерпретувати і використовувати нотацію Big O?

Ігнорування констант і менш значущих членів:

Big O описує порядок зростання функції, ігноруючи константи і менш значущі члени. Наприклад, O(2n) і O(3n) інтерпретуються як O(n).

Порівняння алгоритмів:

Big O дозволяє порівнювати алгоритми за їх асимптотичною ефективністю. Наприклад, алгоритм з O(n log n) ефективніший, ніж алгоритм з O(n^2) для дуже великих обсягів даних.

Аналіз найгіршого випадку:

Big O зазвичай використовується для аналізу найгіршого випадку часу виконання алгоритму, що дозволяє оцінити його максимальну складність.

Ігнорування констант.

Ігнорування констант і менш значущих членів

Приклад 1:

Розгляньмо дві функції:

• f(n) = 3n + 2
• g(n) = 5n + 1

Обидві функції мають лінійну складність, так як домінуючий член в кожній функції — це n. Тому обидві функції інтерпретуються як O(n), незважаючи на відмінності в коефіцієнтах і додаткових членах.

Приклад 2:

Розгляньмо дві функції:

• f(n) = n^2 + 3n + 4
• g(n) = 2n^2 + n

Обидві функції мають квадратичну складність, так як домінуючий член — це n^2. Обидва вирази інтерпретуються як O(n^2), незважаючи на відмінності в решті членів і коефіцієнтах.

2.3. Порівняння алгоритмів

1. Порівняння алгоритмів на дуже великих обсягах даних

Приклад 1:

• Алгоритм A має часову складність O(n^2).
• Алгоритм B має часову складність O(n log n).

Для малих значень n, алгоритм A може працювати швидше через менші константи, але для великих значень n, алгоритм B буде значно швидше, так як його зростання логарифмічне, а не квадратичне.

Приклад 2:

• Алгоритм X має часову складність O(n).
• Алгоритм Y має часову складність O(1).

Алгоритм Y буде завжди швидше, незалежно від розміру n, так як O(1) означає, що час виконання алгоритму не залежить від розміру вхідних даних.

2. Аналіз найгіршого випадку

Приклад 1:

Алгоритм сортування бульбашкою має часову складність O(n^2) в найгіршому випадку, коли масив відсортований у зворотному порядку. Це означає, що для кожного елемента в масиві потрібно порівняння і, можливо, обмін з кожним іншим елементом.

Приклад 2:

Бінарний пошук має часову складність O(log n) в найгіршому випадку. Це означає, що навіть в найгіршому випадку, кількість кроків, необхідних для знаходження елемента, буде логарифмічно залежати від розміру масиву, що дуже ефективно.

3. Вплив на продуктивність і масштабованість

Приклад 1:

Якщо у нас є два алгоритми для обробки даних, один з часовою складністю O(n^2), а інший з O(n log n), і ми збільшуємо розмір даних з 1000 елементів до 10,000 елементів, різниця в продуктивності буде значно помітна.

• Алгоритм з O(n^2) буде виконувати приблизно 100,000,000 операцій для 10,000 елементів.
• Алгоритм з O(n log n) буде виконувати близько 40,000 операцій для 10,000 елементів.

Приклад 2:

Розглянемо алгоритм, який працює за O(2^n). Якщо ми збільшуємо розмір вхідних даних з 10 до 20 елементів, кількість операцій зростає експоненційно.

• Для n = 10: 2^10 = 1024 операцій.
• Для n = 20: 2^20 = 1,048,576 операцій.

Це показує, як швидко експоненційна складність стає непрактичною для великих значень n.